Thuật toán Flash sort, Shear Sort cụ thể như thế nào?

[tun_tun]

Các anh chị có thể giảng cho em về 2 thuật toán Flash sort , Shear Sort được không ạ ?

[Ada]

Flash sort là một thuật toán sắp xếp tại chỗ (in-situ, không dùng mảng phụ) có độ phức tạp O(n), không đệ qui, gồm có 3 bước: (1) Phân lớp dữ liệu, tức là dựa trên giả thiết dữ liệu tuân theo 1 phân bố nào đó, chẳng hạn phân bố đều, để tìm 1 công thức ước tính vị trí (lớp) của phần tử sau khi sắp xếp. (2) Hoán vị toàn cục, tức là dời chuyển các phần tử trong mảng về lớp của mình. (3) Sắp xếp cục bộ, tức là để sắp xếp lại các phần tử trong phạm vi của từng lớp.

Quá trình này cũng tương tự như việc xếp lớp và xếp chỗ cho học sinh lớp 1 trong một trường học, theo tên học sinh. (Giả sử tên học sinh được phân bố đều; thực tế điều này không đúng, chẳng hạn, số tên vần H, T thường nhiều hơn vần A, B, C.)

Lúc đầu các học sinh đang ngồi trong các phòng học của trường, nhưng không theo thứ tự nào cả.

(1) Phân lớp: 26 phòng học mỗi phòng sẽ là 1 lớp: A, B, C,...

(2) Hoán vị toàn cục: dời từng học sinh về đúng lớp của mình; khi một học sinh vào lớp, một học sinh (ngồi chưa đúng lớp) sẽ phải nhường chỗ.

(3) Sắp xếp cục bộ: cô giáo chủ nhiệm từng lớp sẽ sắp xếp chỗ ngồi cho các em trong lớp của mình.

Mô tả chi tiết và mã nguồn: trên http://www.neubert.net/Flapaper/9802n.htm