Ý tưởng:
Thuật toán Shaker Sort là cải tiến của Bubble Sort bằng cách thực hiện 2 lượt đi và về cùng lúc. Lượt đi sẽ đẩy các phần tử nhỏ về đầu dãy, lượt về sẽ đẩy các phần tử lớn về cuối dãy.
Thuật toán:
Bước 1:
Khởi tạo: l=0; r = N-1;//từ l đến r là đoạn cần được sắp xếp
K=N-1; //ghi nhận lại vị trí l 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ỏ nhất về đầu mảng
Trong khi (j>l)
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 bớt phần tử đã có thứ tự ở đầu dãy
Bước 2:
b: j=l; // đẩy phần tử lớn về cuối mảng
Trong khi (j<r)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;
r=k;//loại bớt phần tử đã có thứ tự ở cuối dãy
Bước 3:
Nếu l < r : lặp lại bước 2.
Ví dụ:
Cài đặt:
void ShakerSort(int a[], int N)
{
int i, k, left, right;
k = 0;
left = 0;
right = N - 1;
while (left < right) {
for (i = right; i > left; i--)
if (a[i] < a[i - 1]) {
Swap(a[i], a[i - 1]); // Hoan vi a[i], a[i - 1]
k = i; // Dung bien k danh dau de bo qua doan da co thu tu.
}
left = k;
for (i = left; i < right; i++)
if (a[i] > a[i + 1]) {
Swap(a[i], a[i + 1]);
k = i;
}
right = k;
}
}
