Thuật toán sắp xếp tráo đổi (Exchange sort)

·        Xác định bài toán

-         Input: Dãy A gồm N số nguyên a1, a2, …, aN.

-         Output: Dãy A được sắp xếp lại thành dãy không giảm..

·        Ý  tưởng: Với mỗi cặp số hạng đứng liền kề trong dãy, nếu số trước lớn hơn số sau ta đổi chổ chúng cho nhau. Việc đó được lặp lại, cho đế khi không cô sự tráo đổi nào xả ra nữa.

·        Thuật toán

a)     Cách liệt kê

Bước 1. Nhập N, các số hạng a1, a2, …, aN;

Bước 2. M <- N;

Bước 3. Nếu M<2 thì đưa ra dãy A đã được sắp xếp rồi kết thúc;

Bước 4. M <- M-1, i <- 0;

Bước 5. i <- i+1;

Bước 6. Nếu i>M thì quay lại bước 3;

Bước 7. Nếu ai> ai+1 thì tráo đổi ai và ai+1 cho nhau;

Bước 8. Quay lại bước 5.