Thuật toán Insertion Sort

Hôm nay chúng ta cùng tìm hiểu về thuật toán Insertion Sort. Thuật toán sắp xếp chèn.

1. Nguyên lý cơ bản của Insertion Sort

– Dựa trên nguyên lý sắp xếp các lá bài của người chơi bài.

– Từ một phần từ đầu tiên, nó sẽ được lấy ra để so sánh với các phần tử còn lại, để tìm ra vị trí thích hợp nhất và chèn vào vị trí đó.

– Phù hợp với mảng có kích thước nhỏ và có tỉ lệ đã được sắp xếp cao.

– Độ phức tạp thời gian trung bình và xấu nhất là: O(N²)

2 Thực hành Thuật Toán Insertion Sort

// Phattrienphanmem123az.com
#include <iostream>
#include <conio.h>
 
void InsertionSort(int arr[], int n)
{
   int j = 0;
   for (int i = 1; i < n; i++)
   {
       int key = arr[i];
       j = i-1;
 
       while (j >= 0 && arr[j] > key)
       {
           arr[j+1] = arr[j];
           j = j-1;
       }
       arr[j+1] = key;
   }
}
 
void Show(int arr[], int n)
{
   for (int i=0; i < n; i++)
     std::cout << arr[i] <<" ";
}
 
 
int main()
{
    int arr[] = {123, 113, 133, 53, 63};
    int n = sizeof(arr)/sizeof(arr[0]);
 
    InsertionSort(arr, n);
    Show(arr, n);
    _getch();
    return 0;
}

TPham