Thứ Tư, 30 Tháng Mười Một 2022
Trang chủLập trìnhCTDL & Thuật toánThuật toán sắp xếp chèn (Insertion sort)

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.

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

Mình họa thuật toán sắp xếp chèn (wikipedia.org)
Mình họa thuật toán sắp xếp chèn (wikipedia.org)

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ử a0, a1, …,an-1
– Xem dãy gồm 1 phần tử là a0 dãy có thứ tự.
– Thêm a1 vào dãy có thứ tự a0 sao cho dãy mới a0, a1 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ự a0, a1, …,an-1 có thứ tự.

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

Mình họa thuật toán sắp xếp chèn (wikipedia.org)
Mình họa thuật toán sắp xếp chèn (wikipedia.org)

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é.

0 0 Phiếu bình chọn
Xếp hạng bài viết
BÀI VIẾT LIÊN QUAN
Đăng ký nhận thông báo
Thông báo email khi
guest
0 Bình luận
Không thể gửi email
Phản hồi nội tuyến

NÊN ĐỌC THÊM

Bạn muốn tìm kiếm gì?


0
Giáo sư! có thể ném gạch bên dưới nhé!x
()
x