Thuật toán sắp xếp đổi chổ trực tiếp (Interchange Sort)

1. Ý tưởng

Như đã biết, để sắp xếp một dãy số, ta có thể xét các nghịch thế có trong dãy và triệt tiêu dần chúng đi.

Ý tưởng chính của giải thuật là xuất phát từ đầu dãy, tìm tất cả nghịch thế chứa phần tử này, triệt tiêu chúng bằng cách đổi chổ phần tử này với phần tử tương ứng trong cặp nghịch thế. Lặp lại xử lý trên với các phần tử kế tiếp theo trong dãy.

2. Giải thuật
Các bước tiến hành cài đặt:
Bước 1: i=1;/ Bắt đầu từ đầu dãy
Bước 2: j = i+1; // Tìm tất cả 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]; //xét cặp phần tử 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.

3.Mã ngôn ngữ C

void InterchangeSort(int iArray[],int iSize)
{

    for(int i=0;i<iSize-1;i++)

       for(int j=i+1;j<iSize;j++)

             if(iArray[i] > iArray[j])

                       Swap(iArray[i],iArray[j]);

}

4. Đánh giá giải thuật
Đối với giải thuật đổi chổ trực tiếp, số lượng các phép so sánh xảy ra không phụ thuộc vào tình trạng của dãy ban đầu, nhưng số lượng phép hoán vị tùy thuộc vào kết quả so sánh, có thể ước lượng trong từng trường hợp như sau:
Tốt nhất: So sánh: n(n-1)/2 ;Hoán vị: 0
Xấu nhất: So sánh: n(n-1)/2; Hoán vị: n(n-1)/2


Các thuật toán sắp xếp khác:

   [Thuật toán sắp xếp] Selection Sort

   [Thuật toán sắp xếp] Insertion Sort + Binary Insertion Sort

   [Thuật toán đang xem] Interchange Sort

   [Thuật toán sắp xếp] Bubble Sort

   [Thuật toán sắp xếp] Quick Sort