Ý 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 < j và ai>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í x và y.
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 1: i = 1;
Bước 2: j = i + 1; // tìm các phần tử a[j] < a[i], j > i
Bước 3: Trong khi j ≤ n thực hiện
Nếu a[j] < a[i]: a[i] ↔ a[j];
j = j + 1;
Bước 4: i = i + 1
Nếu i < n: Lặp lại bước 2.
Ngược lại: Dừng.