Bài 49. Thuật toán sắp xếp chèn (Insertion sort)

Chào mừng các bạn quay trở lại với blog của tôi. Hôm nay, tôi xin giới thiệu tới các bạn thuật toán sắp xếp chèn. Thuật toán này sẽ giúp bạn sắp xếp dãy số một cách hiệu quả, và tôi sẽ hướng dẫn bằng ngôn ngữ lập trình C++.

Ý tưởng thuật toán sắp xếp chèn

Thuật toán sắp xếp chèn hoạt động bằng cách duyệt qua từng phần tử trong mảng và chèn từng phần tử đó vào vị trí thích hợp trong mảng con (dãy số từ đầu đến phần tử trước nó) đã được sắp xếp trước đó. Việc này đảm bảo tính chất dãy số tăng dần của mảng đã sắp xếp.

Cụ thể, thuật toán thực hiện như sau:

1. Khởi tạo mảng với một dãy con đã sắp xếp có 1 phần tử (phần tử đầu tiên, có chỉ số 0).
2. Duyệt qua từng phần tử từ phần tử thứ 2, tại mỗi lần duyệt, chèn phần tử đó vào vị trí thích hợp trong đoạn từ [0...i] sao cho dãy số từ [0...i] vẫn đảm bảo tính chất dãy số tăng dần. Sau mỗi lần duyệt, số phần tử đã sắp xếp k trong mảng tăng thêm 1 phần tử.
3. Lặp lại quá trình duyệt cho tới khi duyệt hết tất cả các phần tử của mảng.

Ví dụ minh họa

Dưới đây là một ví dụ minh họa cho thuật toán sắp xếp chèn:

Minh họa thuật toán sắp xếp chèn

Hàng đầu tiên trong hình mô phỏng trạng thái ban đầu của mảng (dãy số chưa sắp xếp). Từ hàng thứ 2 trở đi, chúng ta tìm vị trí thích hợp để chèn số đang xét vào để đảm bảo tính chất dãy số vẫn tăng dần. Và khi lặp qua tất cả các số trong mảng, ta có trạng thái đã sắp xếp ở hàng cuối cùng.

Minh họa thuật toán sử dụng ngôn ngữ C++

#include 
#include 

// Hàm sắp xếp sử dụng thuật toán sắp xếp chèn
void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i-1;

        // Di chuyển các phần tử có giá trị lớn hơn giá trị key về sau một vị trí so với vị trí ban đầu của nó
        while (j >= 0 && arr[j] > key) {
            arr[j+1] = arr[j];
            j = j-1;
        }
        arr[j+1] = key;
    }
}

// Hàm xuất mảng
void printArray(int arr[], int n) {
    int i;
    for (i=0; i < n; i++)
        printf("%d ", arr[i]);
    printf("n");
}

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr)/sizeof(arr[0]);

    insertionSort(arr, n);

    printf("Sorted array: n");
    printArray(arr, n);

    return 0;
}

Kết quả chạy thử chương trình:

Sorted array: 5 6 11 12 13

Đánh giá thuật toán sắp xếp chèn

• Độ phức tạp thuật toán:
  • Trường hợp tốt: O(n)
  • Trung bình: O(n^2)
  • Trường hợp xấu: O(n^2)
• Không gian bộ nhớ sử dụng: O(1)

Nếu bạn thấy bài viết này hữu ích, hãy like và theo dõi fanpage "Học lập trình cùng tôi" để cập nhật những bài viết mới nhất nhé.