Cấu trúc dữ liệu và giải thuật: Giải thuật sắp xếp đổi chỗ (Interchange sort)

[Quoc_Khanh_Tran (Quốc Khánh Trần)]

Giải thuật sắp xếp chèn (Insertion sort)

1. Ý tưởng thuật toán

• Xuất phát từ đầu dãy, tìm tất cả các nghịch thế chứa phần tử này, triệt tiêu chúng bằng cách đổi chỗ 2 phần tử trong cặp nghịch thế.
• Lặp lại xử lý trên với phần tử kế trong dãy.

Mình đã đề cập khái niệm nghịch thế trong topic Giải thuật sắp xếp Selection Sort.

2. Cơ chế hoạt động (sơ đồ dò vết)

Cho dãy số: | 5 | 2 | 3 | 1 | 4 |. Sắp xếp dãy số tăng dần.

• Bước 1:
  i = 0, a[0] = 5;
  j = i + 1 = 1, a[1] = 2; //nghịch thế
  Đổi chỗ a[1] với a[0]:
  | 2 | 5 | 3 | 1 | 4 |

• Bước 2:
  i = 0, a[0] = 2;
  j = 2, a[2] = 3; //không phải nghịch thế
  j = 3, a[3] = 1; //nghịch thế
  Đổi chỗ a[3] với a[0]:
  | 1 | 5 | 3 | 2 | 4 |

• Bước 3:
  i = 0, a[0] = 1;
  j = 4, a[4] = 4; //không phải nghịch thế

• Bước 4:
  i = 1, a[1] = 5;
  j = i + 1 = 2, a[2] = 3; //nghịch thế
  Đổi chỗ a[2] với a[1]:
  | 1 | 3 | 5 | 2 | 4 |

• Bước 5:
  i = 1, a[1] = 3;
  j = 3, a[3] = 2; //nghịch thế
  Đổi chỗ a[3] với a[1]:
  | 1 | 2 | 5 | 3 | 4 |

• Bước 5:
  i = 1, a[1] = 2;
  j = 4, a[4] = 4; //không phải nghịch thế

Làm tương tự các bước, ta thu được 1 dãy đã sắp xếp theo trật tự tăng: | 1 | 2 | 3 | 4 | 5 |

3. Các bước của thuật toán

Bước 1: i = 0; // bắt đầu từ đầu dãy
Bước 2: j = i + 1; //tìm các nghịch thế với a[i]
Bước 3: Trong khi j < n thì thực hiện:

• Bước 3.1: Nếu a[j] < a[i] thì gọi hàm doiCho(a[i], a[j]) để đổi chỗ 2 phần tử
• Bước 3.2: j = j + 1;

Bước 4: i = i + 1;

• Bước 4.1: Nếu i < n -1: Lặp lại Bước 2;
• Bước 4.2: Ngược lại: Dừng.

4. Cài đặt (C++)

void doiCho(int& a, int& b) {
    int temp = a;
    a = b;
    b = temp;
}
void interchangeSort(int a[], int n) {
    for(int i = 0; i < n - 1; i++)
        for(int j = i + 1; j < n; j++)
            if(a[j] < a[i]) doiCho(a[i], a[j]);
}

5. Độ phức tạp của thuật toán