Thắc mắc về thuật toán sắp xếp

nguyenducloi · June 24, 2018, 11:42am

Trên lớp hiện tại em đang học thuật toán sắp xếp chèn (insertion sort), sắp xếp chọn (selection sort), sắp xếp nhanh (quick sort). Do ngành của em ko phải CNTT, mà môn này là tự chọn. Mà môn này lại ko có sách nữa.
Thầy cho bài kiểu sắp xếp tên của mình theo bảng chữ cái. Như A là số thứ tự là 1, B là 2, C là 3 … Y là 24

NGUYEN DUC LOI
–> C D E G I L N N O U U Y
Em ko hiểu mấy thuật toán đó sử dụng ntn. Dẫn đến ko biểu bài. Ai có thể lấy ví dụ minh họa thực tế dễ hiểu được ko ạ. Em cảm ơn.

tntxtnt · March 30, 2016, 3:26am

đây nè bạn: http://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html

còn nhiều minh họa của các thuật toán khác nữa: http://www.cs.usfca.edu/~galles/visualization/Algorithms.html

trang khác: http://visualgo.net/
các hàm sắp xếp: http://visualgo.net/sorting.html

Tulip · March 30, 2016, 3:36am

There is a cool clip about sorting algorithms:

htwap · March 30, 2016, 4:07am

mình thấy cái này người biết các thuật toán đấy rồi còn thấy khó hiểu ấy chứ.

AI_Android · March 30, 2016, 9:38am

Tưởng tượng trong lớp có 10 hotgirl bây h sắp xếp theo điểm vòng 1 để cho học bổng. Có 1 tin vui và 1 tin buồn :)) cho bạn nghe cả 2
Tin buồn: số lượng học bổng còn là bí mật nên cứ phải sắp xếp từ nhỏ đến to trước đã rồi tính sau.
Tin vui: không có 2 hotgirl nào bằng điểm nhau cả (Cho dễ hiểu đã )

Sắp sếp chọn: đi từ đầu đến cuối thấy em nào nhỏ nhất đuổi ra ngoài,(ai bảo trời sinh ra nhỏ) vậy là còn 9 em, lại lặp lại như vậy đi từ đầu đến cuối em nào nhỏ nhất đuổi ra ngoài, vậy là còn 8 em, tương tự thế là sẽ tìm ra em to nhất và có đuổi ra ngoài hay ko thì còn tùy bạn

Sắp xếp chèn: Do các em bị ngẻo cổ nên chỉ nhìn được về bên phải của hàng, mà lại ganh gét nhau, nếu nhìn thấy con nào nhỏ hơn của mình là đập chết. ( xu hướng bây h đang thích nhỏ) .

Rồi bây h bạn stun cả 10 cô rồi đi từ trái qua phải
cứ thấy cô nào mà vòng 1 nhỏ hơn cô kề bên trái là phải dừng lại chỉnh ko thì tí nữa hết stun cô đó chắc chắn ăn dép. xếp ra sao => tìm cô gần nhất bên trái mà có vòng 1 nhỏ hơn thì để cô ấy vào đó. Ví dụ điểm đang là : 1 3 2. đang yên đang lành đi đến cô 2. à mày nhỏ à, ở đây thì chết. thế là nhìn lại xem :3 ồ có cô 1 này con nhỏ hơn => xếp lại nào. 1 2 3

Đấy cứ thế là xong

nguyenducloi · March 30, 2016, 2:13pm

Cái chèn và chọn mình hiểu rồi. Còn cái Nhanh hơi khó hiểu. Bạn có tài liệu lý thuyết về cái QuickSort này ko ?

Bui_Trung_Thong · June 24, 2018, 11:45am

chắc bạn này người nước ngoài

tntxtnt · March 30, 2016, 3:10pm

cái quicksort còn dễ hiểu hơn insertion sort nữa đó. Nó chỉ có 2 bước là partition và recursive call
bước cơ bản là partition (dịch nôm na là cắt mảng A thành 2 mảng con)

chọn 1 số x trong mảng A
chia mảng A thành 2 mảng: mảng bên trái chứa các phần tử nhỏ hơn x, mảng bên phải chứa các phần tử lớn hơn hoặc bằng x.
bước tiếp theo là gọi partition mảng bên trái và partition mảng bên phải. Vậy là xong.

gọi đệ quy tất cả các mảng con tức là sau khi hoàn thành thì mảng A sẽ có tính chất số A[i] luôn bé hơn (hoặc bằng) số liền kề bên phải A[i+1], tức là mảng A đã được sắp xếp.

bước partition thì bạn code cách nào cũng được, miễn là từ mảng ban đầu tạo ra 2 mảng, mảng bên trái chứa các phần tử bé hơn x, mảng bên phải chứa các phần tử lớn hơn x là được. Để tiết kiệm bộ nhớ thì 2 mảng con có thể nằm trong mảng A luôn, ko cần tạo 2 mảng mới. Với cách tiết kiệm bộ nhớ này thì cần biết vị trí p nào tách mảng A thành 2 mảng A[0]-A[p-1] là mảng bên trái, A[p]-A[n-1] là mảng bên phải.