Shaker Sort

Shaker Sort hay còn được gọi là thuật toán sắp xếp Cocktail, đây là một thuật toán cải tiến của thuật toán Bubble Sort.
Shaker Sort sau khi đưa phần tử nhỏ/lớn nhất lên đầu dãy, sau đấy lại đưa phần tử lớn/nhỏ nhất về cuối dãy. Như vậy, trong một lần duyệt, Shaker sort sẽ đưa ít nhất hai số  về đúng với vị trí của nó. Giả sử ta xét mảng gồm các phần tử {6; 7; 8; 9 ;0}
Với Shaker Sort trong một lần duyệt, các phần tử đã trở về đúng vị trí của nó: {0;6;7;8;9}. Tuy nhiên, đối với Bubble sort ta cần tới 4 lần duyệt để đưa các phần tử về đúng vị trí. Vậy đối với một số mảng đã gần như có thứ tự, Shaker Sort sẽ chạy nhanh hơn so với Bubble Sort. Nếu như ta xét các mảng sinh các số ngẫu nhiên thì thời gian chạy của hai thuật toán này là tương đương nhau.


THIẾT KẾ THUẬT TOÁN 

void swap(int &a, int &b) {
int i = a;
a = b;
b = i;
return;
}


void shakersort(int a[], int n) {
int l, r, k;
r = n - 1;
l = 0;
k = 0;
while(l<r) {
for (int i = l; i < r; i++) {
if (a[i] > a[i + 1]) {
k = i;
swap(a[i], a[i + 1]); // đổi chỗ hai phần tử a[i] và a[i-1]
}
}
r = k;
for (int i = r; i > l; i--) {
if (a[i] < a[i - 1]) {
k = i;
swap(a[i], a[i - 1]);// đổi chỗ hai phần tử a[i] và a[i-1]
}
}
l = k;
}
return;
}
Kết luận: Như vậy, chỉ cần với số lần duyệt ít hơn đã có thể sắp xếp các phần tử về đúng thứ tự ta muốn. Mặc dù xét về độ phức tạp thì Bubble sort và Shaker Sort gần như tương đương nhau. Tuy nhiên, trong một số trường hợp, rõ ràng thuật toán Shaker sort có thời gian chạy nhanh hơn nhiều so với Bubble sort điển hình như ví dụ trên mình đã cho các bạn xem.