BUBBLE SORT
Ý tưởng
Xét dãy gồm N phần tử
Xuất phát từ cuối dãy, đổi chỗ các cặp phần tử kế cận để đưa phần tử nhỏ hơn trong cặp phần tử đó về vị trí đầu dãy hiện hành.
Ta không quan tâm đến phần tử đầu dãy nữa, xem dãy bây giờ chỉ còn N-1 phần tử, bắt đầu từ vị trí thứ 2.
Lặp lại xử lí trên cho đến khi không còn cặp phần tử nào để xét.
Giải thuật
Bước 1: i = 1;
Bước 2: j = N; // Duyệt từ cuối dãy ngược về vị trí i
Trong khi j < i thực hiện
Nếu a[j] < a[j-1]: a[j] ↔ a[j-1]; // xét cặp phần tử kế cận
j = j - 1;
Bước 3: i = i + 1
Nếu i ≤ N – 1 : Lặp lại bước 2.
Ngược lại: Hết dãy. Dừng.
SHAKER SORT
Shaker Sort cũng dựa trên nguyên tắc đổi chỗ trực tiếp nhưng tìm các khắc phục nhược điểm của Bubble Sort. Trong mỗi lần sắp xếp, duyệt mảng theo 2 lượt từ 2 phía khác nhau.
+ Lượt đi: đẩy phần tử nhỏ về đầu mảng
+ Lượt về: đẩy phần tử lớn về cuối mảng
Ghi nhận lại những đoạn đã sắp xếp nhằm tiết kiệm các phép so sánh thừa.
Bước 1: l = 1; r = n; // từ l đến r là đoạn cần sắp xếp
k = n; // ghi nhận vị trí k xảy ra hoán vị sau cùng
// để làm cơ sở thu hẹp đoạn l đến r.
Bước 2:
Bước 2a: j = r; // đẩy phần tử nhỏ về đầu mảng
Trong khi (j > l) thực hiện
Nếu a[j] < a[j-1]: a[j] ↔ a[j-1];
k = j; // lưu lại nơi xảy ra hoán vị.
j = j – 1;
l = k; // loại các phần tử đã có thứ tự ở đầu dãy
Bước 2b: j = l; // đẩy phần tử lớn về cuối mảng
Trong khi (j < r) thực hiện
Nếu a[j] > a[j-1]: a[j] ↔ a[j+1];
j = j + 1;
r = k; // loại các phần tử đã có thứ tự ở cuối dãy
Bước 3: Nếu l < r : Lặp lại bước 2.
Ngược lại: Dừng.