Thuật toán sắp xếp chèn (Insertion sort)

Trong bài viết này Blog tuicocach.com sẽ giới thiệu tới các bạn thuật toán sắp xếp chèn. Đây là một trong các thuật toán sắp xếp căn bản thường dùng.

DANH SÁCH BÀI VIẾT
Thuật toán sắp xếp nhanh (Quick Sort)
Thuật toán sắp xếp trộn (Merge Sort)
Thuật toán sắp xếp đổi chỗ trực tiếp (Interchange Sort)
Thuật toán sắp xếp nổi bọt (Bubble Sort)
Thuật toán sắp xếp chọn(Selection Sort)
Thuật toán sắp xếp chèn (Insertion sort)

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

Thuật toán sắp xếp chèn (Insertion Sort) thực hiện sắp xếp các phần tử theo cách duyệt từng phần tử. Và chèn từng phần tử đó vào đúng vị trí trong mảng con. Phần tử được chuyền vào vị trí thích hợp sao cho mảng con vẫn đảm bảo sắp xếp theo đúng thứ tự.

Xét dãy n phần tử a_0, a_{1, …,}a_n-1
– Xem dãy gồm 1 phần tử là a₀ dãy có thứ tự.
– Thêm a₁ vào dãy có thứ tự a₀ sao cho dãy mới a_0, a₁ là dãy có thứ tự.
– Tiếp tục như thế đến n-1 bước ta sẽ có dãy có thứ tự a_0, a_{1, …,}a_n-1 có thứ tự.

• Kiếm tiền Accesstrade, kiếm tiền tại nhà với Accesstrade.vn – Tiếp thị liên kết
• MegaURL – Rút gọn link kiếm tiền có giá cao tại Việt Nam
• Top 4 App kiếm tiền online trên điện thoại tốt nhất 2022

Ví dụ: Sử dụng thuật toán Insertion Sort sắp xếp dãy {3,2,6,9,1,4,7,10,8,5} theo thứ tự tăng dần ta sẽ thấy các bước thực hiện như sau

Hàng đầu tiên 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, ta tìm chèn số đang xét vào vị trí thích hợp để đảm bảo dãy số vẫn tăng dần. Và khi lặp hết 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.

Cài đặt thuật toán trên ngôn ngữ C/C++

#include <stdio.h>
#include <math.h>
 
/* 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)
{
   for (int i=0; i < n; i++)
       printf("%d ", arr[i]);
   printf("\n");
}
 
 
 
 
int main()
{
    int arr[] = {3,2,6,9,1,4,7,10,8,5};
    int n = sizeof(arr)/sizeof(arr[0]);
 
    insertionSort(arr, n);
    printf("Sorted array: \n");
    printArray(arr, n);
 
    return 0;
}

Kết quả chạy chương trình trên

1 2 3 4 5 6 7 8 9 10

Đá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) (Chỉ xảy ra khi dãy số đã là một dãy số có thứ tự sắp xếp)
• Trung bình: O(n^2)
• Trường hợp xấu: O(n^2)

Cảm ơn đã theo dõi bài viết, nếu có bất kỳ thắc mắc hay góp ý comment bên dưới nhé.