Thuật toán sắp xếp: INTERCHANGE SORT

Ý tưởng

Khái niệm nghịch thế: Xét một mảng các số a0, a1,…, an. Nếu có i < jai>aj thì ta gọi đó là một nghịch thế.

Thuật toán Interchange sort:

Gọi x là phần tử đầu dãy, tìm tất cả các nghịch thế (x, y) và triệt tiêu chúng bằng cách đảo vị trí xy.

Lặp lại xử lí trên cho các phần tử tiếp theo trong dãy.

 

Giải thuật

            Bước 1i = 1;          

            Bước 2j = i + 1;     // tìm các phần tử a[j] < a[i], j > i

            Bước 3:  Trong khi jn thực hiện

                                    Nếu a[j] < a[i]: a[i] ↔ a[j];           

                                    j = j + 1;

            Bước 4i = i + 1

                            Nếu  i < n: 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: INTERCHANGE SORT

Cùng chuyên mục

Xem nhiều hôm nay