Thuật toán ShakerSort

Ý 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.

Cài đặt thuật toán:

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