Cấu trúc dữ liệu và giải thuật: Giải thuật sắp xếp rung lắc (Shaker sort)

Quoc_Khanh_Tran · June 14, 2022, 10:13am

Giải thuật sắp xếp rung lắc (Shaker sort)

1. Ý tưởng thuật toán

Là cải tiến của Bubble Sort theo mục tiêu: không chỉ những phần tử nhẹ nhất “nổi lên” đầu dãy mà cả phần tử nặng nhất cũng “chìm” xuống cuối dãy. Muốn vậy, ta phải ghi nhớ lần đổi chỗ cuối cùng khi duyệt ngược từ cuối lên và khi duyệt xuôi dãy từ đầu xuống cuối để quyết định xem ở bước tiếp theo sẽ duyệt từ đó (chỗ ghi nhớ) đến đâu.

2. Các bước của thuật toán

Bước 1: Khởi trị
left = 0, right = n - 1, k = n - 1;
//left, right, k lần lượt là vị trí đầu, cuối và vị trí trung gian ghi nhớ các lần đổi chỗ.

Bước 2 : Trong khi left < right thì lặp lại các bước sau:
+Bước 2.1. Duyệt ngược từ cuối lên đầu dãy:

Nếu a[j] < a[j - 1] thì:
Bước 2.1.1. Gọi hàm doiCho(a[j], a[j - 1]);
Bước 2.1.2. Ghi nhớ vị trí j vào biến k;

+Bước 2.2. Ghi nhớ k vào biến left (tức là ở bước tiếp, k là vị trí đầu dãy hiện hành);
+Bước 2.3. Duyệt xuôi từ vị trí left (có được từ Bước 2.1.2):

Nếu a[j] > a[j + 1] thì:
Bước 2.3.1. Gọi hàm doiCho(a[j], a[j + 1]);
Bước 2.3.2. Lưu j vào k;

+Bước 2.4. Ghi nhớ k vào right (tức là ở bước tiếp, k là vị trí cuối dãy hiện hành);

Bước 3 : Vòng lặp ngoài kết thúc khi left > right.

Lưu ý: ta có thể khởi tạo k = 0 khi muốn duyệt xuôi trước.

3. Cơ chế hoạt động (sơ đồ dò vết)

Cho dãy số: | 5 | 2 | 3 | 1 | 4 |. Sắp xếp dãy số tăng dần.

Bước 1: left = 0, right = 4, k = 4;
+Bước 1.1. Vòng lặp 1 (duyệt ngược)

i = 4, a[4] > a[3]; //không phải nghịch thế
i = 3, a[3] < a[2]; //nghịch thế
–> Đổi chỗ a[3] với a[2], ta có: | 5 | 2 | 1 | 3 | 4 |
–> k = i; // k = 3
i = 2, a[2] < a[1]; //nghịch thế
–> Đổi chỗ a[2] với a[1], ta có: | 5 | 1 | 2 | 3 | 4 |
–> k = i; // k = 2
i = 1, a[1] < a[0]; //nghịch thế
–> Đổi chỗ a[1] với a[0], ta có: | 1 | 5 | 2 | 3 | 4 |
–> k = i; // k = 1

+Bước 1.2. left = k; //left = 1
+Bước 1.3. Vòng lặp 2 (duyệt xuôi)

i = 1, a[1] > a[2]; //nghịch thế
–> Đổi chỗ a[1] với a[2], ta có: | 1 | 2 | 5 | 3 | 4 |
–> k = i; // k = 1
i = 2, a[2] > a[3]; //nghịch thế
–> Đổi chỗ a[2] với a[3], ta có: | 1 | 2 | 3 | 5 | 4 |
–> k = i; // k = 2
i = 3, a[3] > a[4]; //nghịch thế
–> Đổi chỗ a[3] với a[4], ta có: | 1 | 2 | 3 | 4 | 5 |
–> k = i; // k = 3

+Bước 1.4. right = k; //right = 3

Bước 2: left = 1, right = 3, k = 3;
+Bước 2.1. Vòng lặp 1 (duyệt ngược)

i = 3, a[3] > a[2]; //không phải nghịch thế
i = 2, a[2] > a[1]; //không phải nghịch thế

+Bước 2.2. left = k; //left = 3
+Bước 2.3. Bỏ qua vòng lặp 2 (duyệt xuôi) vì không thỏa điều kiện;
+Bước 2.4. right = k; //right = 3
Kết thúc chương trình do left = right.

Ta thu được 1 dãy đã sắp xếp theo trật tự tăng: | 1 | 2 | 3 | 4 | 5 |

4. Cài đặt (C++)

Duyệt ngược trước:

void shakerSort(int a[], int n) {
    int left, right, k, i;
    left = 0;
    right = n - 1;
    k = n - 1;
    while(left < right) {
        for(i = right; i > left; i--)
            if(a[i] < a[i - 1]) {
                swap(a[i], a[i - 1]);
                k = i;
            }
        left = k;

        for(i = left; i < right; i++)
            if(a[i] > a[i + 1]) {
                swap(a[i], a[i + 1]);
                k = i;
            }
        right = k;
    }
}

hoặc duyệt xuôi trước:

void shakerSort(int a[], int n) {
    int left, right, k, i;
    left = 0;
    right = n - 1;
    k = 0;
    while(left < right) {
        for( int i = left; i < right; i++)
            if(a[i] > a[i + 1]) {
                swap(a[i], a[i + 1]);
                k = i;
            }
        right = k;

        for( int i = right; i > left; i--)
            if(a[i] < a[i - 1]) {
                swap(a[i], a[i - 1]);
                k = i;
            }
        left = k;
    }
}