Thuật toán sắp xếp: BUBBLE SORT - SHAKER SORT

BUBBLE SORT

Ý tưởng

            Xét dãy gồm N phần tử

Xuất phát từ cuối dãy, đổi chỗ các cặp phần tử kế cận để đưa phần tử nhỏ hơn trong cặp phần tử đó về vị trí đầu dãy hiện hành.

Ta không quan tâm đến phần tử đầu dãy nữa, xem dãy bây giờ chỉ còn N-1 phần tử, bắt đầu từ vị trí thứ 2.

Lặp lại xử lí trên cho đến khi không còn cặp phần tử nào để xét.

 

Giải thuật

            Bước 1i = 1;          

            Bước 2j = N;          // Duyệt từ cuối dãy ngược về vị trí i

                           Trong khi j < i thực hiện

                                    Nếu a[j] < a[j-1]: a[j] ↔ a[j-1];     // xét cặp phần tử kế cận                                  

                                                j = j - 1;

            Bước 3i = i + 1

                            Nếu  iN – 1 : Lặp lại bước 2.

                Ngược lại: Hết dãy. Dừng.         

SHAKER SORT

Ý tưởng

Shaker Sort cũng dựa trên nguyên tắc đổi chỗ trực tiếp nhưng tìm các khắc phục nhược điểm của Bubble Sort. Trong mỗi lần sắp xếp, duyệt mảng theo 2 lượt từ 2 phía khác nhau.

+          Lượt đi: đẩy phần tử nhỏ về đầu mảng

+          Lượt về: đẩy phần tử lớn về cuối mảng

            Ghi nhận lại những đoạn đã sắp xếp nhằm tiết kiệm các phép so sánh thừa.

 

Giải thuật

            Bước 1l = 1; r = n;            // từ l đến r là đoạn cần sắp xếp    

                           k = n;           // ghi nhận vị trí k 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ỏ về đầu mảng

                                    Trong khi  (j > l) thực hiện

                                                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 các phần tử đã có thứ tự ở đầu dãy

                        Bước 2b: j = l;           // đẩy phần tử lớn về cuối mảng

                                    Trong khi  (j < r) thực hiện

                                                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 các phần tử đã có thứ tự ở cuối dãy

            Bước 3:  Nếu  l < r : Lặp lại bước 2.

                Ngược lại: Dừng.             

 

Chủ đề liên quan
Thuật toán sắp xếp: BUBBLE SORT - SHAKER SORT

Cùng chuyên mục

Xem nhiều hôm nay