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

đâ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

There is a cool clip about sorting algorithms:

There is a cool clip about sorting algorithms:

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ứ.

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ỏ) .

1. Rồi bây h bạn stun cả 10 cô rồi đi từ trái qua phải
2. 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

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 ?

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

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.