Hướng dẫn chi tiết các giải thuật tìm kiếm
Merge sort
Nguyên tắc :
VD ta có
12 13 45 32 100 34 65 10
Ta có ở trên là 8 phần tử cần được sắp xếp :
Ý tưởng của merge sort là thay vì sắp xếp 8 phần tử (khó sắp ) thì ta chia đôi dãy đó ra làm đôi
(số phần tử nhỏ hơn > sắp dễ hơn ) và sắp xếp các dãy con rồi ghép 2 dãy con lại ( gọi là
merge 2 dãy con )
Vậy ta làm như sau:
Chia đôi > được hai dãy con mới là 12 13 45 32 và 100 34 65 10
sắp 2 dãy con lại : 12 13 45 32 gọi là dãy A
100 34 65 10 gọi là dãy B
+ Muốn sắp A ta cũng làm y như trên
Chia đôi A , được 2 dãy mới là A11 = { 12 13 } A12 = {45 32 }
Chia đôi B được 2 dãy mới là B11 = {100 34} B12 = {65 10 }
+ Sắp xếp A11, B11 , A12 , B12
+ Muốn sắp xếp A11 thì ta cũng chia đôi đến khi sắp được
ta có 2 dãy con là A21 = {12} A22 = { 13}
Sắp 2 dãy con trên được ( đơn giản vì chỉ có một phần tử ) là A21 = {12 } A22 = {13}
Sắp xong thì ta merge lại thành A11 = { 12 13 }
+ Tương tự sắp xếp cho B11 , A12 , B12 ta cũng có
B11 = {34 100} B12 = {10 65 } A12 = {32 45 }
+Sắp xếp xong , ta sẽ merge lại A11 , A12 thành A = { 12 13 32 45 }
B11 , B12 thành B = { 10 34 65 100 }
Sắp xong A , B , ta sẽ merge chúng lại thành dãy ban đầu :
{10 12 13 32 34 45 65 100 }
Phương pháp merge:
VD A = { 12 13 32 45 }
B = { 10 34 65 100}
Đầu tiên lấy phần tử đầu tiên của A và B : 12 và 10

+ Được 2 dãy con là A11 = {2 } A12 = {6}
+ Sắp A11 ( sắp sẵn rồi )
+ Sắp A12 ( sắp sẵn rồi )
+ Tạo lại mảng A = { A11 được sắp , pivot , A12 được sắp } = {2 4 6 }
+Sắp B . Trong B ta không thấy được pivot do chọn cái nào ta cũng không thấy thỏa . Nhưng
mục tiêu của quick sort là làm sao ta được dãy
<C= dãy có trị nhỏ hơn pivot > pivot < D= dãy có trị lớn hơn pivot >
Sắp 2 dãy con C , D rồi ghép lại ta được dãy sắp thứ tự .
Vì vậy áp dụng một giải thuật tìm pivot trong B( sẽ trình bày sau ) ta sẽ được C = { 13} D =
{18} và pivot là 14 .
+ Sắp dãy con C , D ( do chỉ có một phần tử nên không sắp , hoặc tìm pivot)
+ Ghép lại tạo thành mảng B được sắp B = { 13 14 18 }
+Ghép A và B để tạo thành mảng được sắp xếp ban đầu
PS : Hiệu quả của giải thuật quicksort phụ thuộc rất nhiều vào việc chọn cho được pivot tốt
( tức nếu pivot nằm gần chính giữa thì đạt gần tối ưu )
Heap Sort
Heap là một cấu trúc dữ liệu , có thể được biểu diễn thông qua 2 cách :
-Dạng thứ 1: Dạng cây nhị phân có đặc điểm là node cha thì lớn hơn 2 node con trực tiếp của
nó .
-Dạng thứ 2: nếu ta đánh số các node theo thứ tự từ trên xuống và từ trái qua . Bắt đầu là node
root = 0 , thì ta có thể định nghĩa heap thông qua mảng một chiều , có đặc điểm là phần tử thứ
k sẽ lớn hơn các phần tử thứ 2k+1 và 2k+2 . Ta có thể dễ nhận thấy là phàn tử thứ 0 sẽ tương
ứng với root trong cây ở cách biểu diễn thứ 1
Nguyên tắc sắp xếp của heap sort
Dựa vào tính chất của heap trong cách biểu diễn thứ 1 và thứ 2 , ta có thể thấy phần tử đầu tiên
trong cách biểu diễn theo mảng sẽ là phần tử lớn nhất > cách sắp xếp đơn giản là : ( Gọi
mảng ban đầu là A )
Khởi tạo : Tạo heap từ mảng ban đầu đã cho (mảng A )
1. Lấy phần tử đầu tiên trong mảng ra bỏ vào mảng kết quả
2. Tạo lại heap từ mảng A

làm như sau
A = y r p d f b k a c
Bước 1 :
Lấy y ra
Lấy c ra
Bỏ y vào chổ của c .
Bỏ c vào chỗ của y
Khi ta bỏ y vào chỗ của c thì giống như ta bỏ y vảo mảng C .
Khi này mảng A sẽ coi như gồm 2 phần A = c r p d f b k a y
Bước 2 : tạo heap cho phần đứng trước của A là c r p d f b k a
Phần sau là chứa y để nguyên
Ta sẽ có A mới là : r f p d c b k a y
Quay lại bước 1 : Lấy r , a ra và swap r và a
A sẽ thành A= a f p d c b k r y
Tạo heap cho A = p f k d c b a r y

Làm tương tự đến khi kết thúc
Qua VD ta thấy rằng phần quan trọng nhất là làm sao sinh ra heap từ một mảng cho trước
Sau đây là phần code cho phần cải tiến
Giải thuật
Post Condition : Dùng để phục hồi lại heap .
Pre Condition :
Ta sẽ có A mới là : r f p d c b k a y
Quay lại bước 1 : Lấy r , a ra và swap r và a
A sẽ thành A= a f p d c b k r y
Tạo heap cho A = p f k d c b a r y
Thì khi này current chính là a
low là 0
high là 7
Insertion Sort

Quay lại bước 1
Thuật toán sắp xếp nổi bọt (buble sort)
Trong thuật toán này, các giá trị trong mảng sẽ được duyệt từ cuối lên đầu, tại mỗi bước sẽ so
sánh giá trị của 2 phần tử kề nhau. nếu chúng bị ngược thứ tự thì đổi lại vị trí. sau 1 lần như
vậy thì phần tử có giá trị nhỏ nhất sẽ được chuyển về đầu mảng. và quá trình tiếp tục duyệt từ
cuối đến phần tử thứ 2, rồi từ cuối đến phần tử thứ 3,
sở dĩ gọi là nổi bọt vì quá trình so sánh giữa các cặp phần tử giống như "bọt" nổi trên mặt
nước
PHP Code
void bublesort(double *a){
double temp;
for (int i = 2; i <= n; i++)
for (int j = n; j >= i; j )
if (a[j] < a[j-1]) {
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
Thuật toán này có độ phức tạp là O(n^2).
Thuật toán sắp xếp đếm phân phối (distribution counting)
Thuật toán này được áp dụng trong trường hợp đặc biệt, khi mà tất cả các giá trị trong mảng
đều là số nguyên và thuộc khoảng [0 M] đã biết.
ý tưởng của thuật toán là đếm xem trong khoảng [0 M] đó có bao nhiêu giá trị 0 (giả sử là a),
bao nhiêu giá trị 1 (giả sử là B) , , bao nhiêu giá trị M (giả sử là z). sau đó xếp lại mảng bằng
cách đặt a phần tử 0 ở đầu, tiếp theo đặt b phần tử 1 tiếp theo, , và đặt z phần tử M ở cuối
cùng.
để giảm thiểu thì việc đếm trên không đếm những giá trị không có trong mảng. giả sử mảng a
có các giá trị a[1], a[2], , a[k] trong tổng số n phần tử thì chỉ đếm số lần lặp lại của k giá trị
đó.

void *radixsort(int l, int r, int b){ /* sắp xếp đoạn [l,r] dựa theo bit b
*/
int i, j;
if (l >= r) return;
i = l; j = r;
do {
while (((i < j) && ((a[i]>>b) & 1)) == 0) ++i; /* tìm phần tử có bit
b = 1 từ đầu đoạn */
while (((i < j) && ((a[j]>>b) & 1)) == 1) j; /* tìm phần tử có bit
b = 0 từ cuối đoạn */
temp = a[i]; /* đổi chỗ chúng */
a[i] = a[j];
a[j] = temp;
} while (i != j); /* đến khi phân đoạn xong */
if (((a[j] >> b) & 1) == 0) ++j; /* j là điểm bắt đầu đoạn có bit b = 1
*/
if (b > 0) { /* chưa xét tới bit cuối cùng */
radixsort(l, j-1, b-1);
radixsort(j, r, b-1);
}
và trong chương trình muốn sắp xếp chỉ cần gọi radixsort(1, n, z) với n là số phần tử và z là số
bit nhiều nhất của các phần tử.
có thể nhận thấy là code của thuật toán này có nhiều nét tương đồng với code của thuật toán
quicksort.
thuật toán trên có thể mở rộng cho sắp xếp theo cơ số r bất kỳ, chứ không chỉ riêng cơ số 2.
khi đó các phần tử sẽ được biểu diễn trong hệ cơ số r, và việc so sánh sẽ căn cứ theo các chữ
số (tình từ cao xuống thấp) trong hệ cơ số r đó. tất nhiên lúc đó chúng ta sẽ không phân ra làm
2 đoạn như trên, mà sẽ có tất cả r đoạn: đoạn đầu tiên chứa chữ số 0 ở đầu, đoạn tiếp chứa chữ
số 1 ở đầu, , đoạn cuối cùng chứa chữ số r-1.
thuật toán trên làm việc rất tốt với các hệ thống (ngôn ngữ lập trình) sử dụng các thao tác cấp

trong mảng.
điều này có nghĩa là nếu trong mảng có 2 phần tử a[i] và a[j], a[i] đứng trước a[j].
nếu 2 phần tử này có giá trị bằng nhau a[i] = a[j] thì sau khi sắp xếp, 1 thuật toán ổn định sẽ
đặt a[i] lên trước a[j] để đảm bảo thứ tự ban đầu của chúng trong mảng.
điều này là không cần thiết lắm nếu chúng ta chỉ tiến hành sắp xếp đối với mảng 1 chiều các số
thực. nhưng vấn đế sẽ nảy sinh khi sắp xếp những mảng mà mỗi phần tử của nó là 1 cấu trúc,
trong đó chúng ta cần phải sắp xếp dựa theo 1 trường khoá nào đó. ví dụ như có 1 danh sách
lớp, và cần phải sắp xếp danh sách này theo trình tự tăng dần của ngày sinh chẳng hạn. khi đó
nếu 2 người cùng ngày sinh thì sao? vấn đề này được giải quyết nhờ vào tính ổn định trong 1
thuật toán, tức là nếu 2 người cùng ngày sinh thì thứ tự trong danh sách ban đầu sẽ được bảo
toàn.
trong những thuật toán đã trình bày ở trên thì thuật toán sắp xếp nổi bọt, chọn, đếm phân phối
là những thuật toán ổn định, còn những thuật toán sắp xếp khác (nói chung là đòi hỏi phải đổi
giá trị của 2 phần tử bất kỳ trong mảng) là không ổn định.
trên nguyên tắc có thể biến bất cứ thuật toán không ổn định nào thành thuật toán ổn định bằng
phương pháp sau:
giả sử ta cần sắp xếp 1 mảng, ta sẽ thêm cho mỗi phần tử 1 khoá index là thứ tự ban đầu của
chúng trong mảng cũ. trong thuật toán sắp xếp được áp dụng, khi cần đổi chỗ 2 phần tử giống
nhau A và B thì ta sẽ so sánh khoá index của chúng, phần tử nào có khoá nhỏ hơn thì đứng
trước.
chúc các bạn áp dụng được những thuật toán này theo ý muốn.
(tham khảo tài liệu Bài giảng chuyên đề của Lê Minh Hoàng)
Cuối cùng:
Các bạn có thể dùng phần mềm mô phỏng này để xem cách nó sắp xếp sẽ dễ hình dung hơn
Chương trình mô phỏng các thuật toán sắp xếp - SortRepresent V1.1