Thuat Toan Shaker Sort

Ý 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;
   }
}