Insertion Sort là một thuật toán sắp xếp đơn giản, dựa trên việc chèn các phần tử vào một vị trí cụ thể trong một mảng hoặc danh sách đã được sắp xếp. Việc sắp xếp được thực hiện bằng cách duyệt qua mỗi phần tử trong mảng, so sánh với tất cả các phần tử đã được sắp xếp trước đó và chèn vào vị trí đúng. Insertion sort có thời gian xử lý O(n^2), nên chỉ được sử dụng cho các mảng hoặc danh sách nhỏ hoặc đã được sắp xếp gần đúng.
Các bài viết liên quan:
Ví dụ Insertion Sort trong c++
Insertion Sort trong C++ là một thuật toán sắp xếp tăng dần để sắp xếp một dãy số hoặc một mảng đối tượng. Cách hoạt động của nó là tìm kiếm vị trí phù hợp trong mảng để chèn phần tử hiện tại vào vị trí đó. Mỗi phần tử được xem xét và chèn vào một vị trí phù hợp trong mảng đã được sắp xếp trước đó.
Ví dụ mã code Insertion Sort trong C++:
#include <iostream>
using namespace std;
void insertionSort(int arr[], int n)
{
int i, key, j;
for (i = 1; i < n; i++)
{
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 printArray(int arr[], int n)
{
int i;
for (i=0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
}
int main()
{
int arr[] = {12, 11, 13, 5, 6};
int n = sizeof(arr)/sizeof(arr[0]);
insertionSort(arr, n);
printArray(arr, n);
return 0;
}Giải thích đoạn code trên
Đoạn code trên mô tả thuật toán Insertion Sort trong ngôn ngữ lập trình C++.
Trong đoạn code này, mảng arr được chứa các số, và sử dụng vòng lặp for để duyệt từng phần tử của mảng, trong khi biến j đại diện cho phần tử đang xét.
Trong mỗi lần lặp, biến key được gán bằng giá trị của phần tử đang xét. Sau đó, vòng lặp while được sử dụng để so sánh giá trị của phần tử đằng trước với key và di chuyển nó lên cho đến khi nó nằm trước key hoặc j đạt đến giá trị 0.
Cuối cùng, giá trị của key được gán vào vị trí đầu tiên của khoảng trống đó.
Đoạn code này tổng quát mô tả quá trình Insertion Sort, trong đó mỗi phần tử được xét và so sánh với các phần tử trước nó, và được chèn vào vị trí đúng trong mảng đã được sắp xếp.
Các trường hợp tốt nhất, tồi tệ nhất và trung bình của Insertion Sort
Trong Insertion Sort, trường hợp tốt nhất là khi mảng đã được sắp xếp. Khi đó, chỉ cần so sánh với một phần tử là có thể tìm ra vị trí đúng để chèn mới. Thời gian tối ưu của thuật toán này là O(n).
Trong trường hợp tồi tệ nhất, mảng đảo ngược hoàn toàn. Khi đó, mỗi phần tử sẽ phải di chuyển đến vị trí đúng trong mảng. Thời gian tồi tệ của Insertion Sort là O(n^2).
Trong trường hợp trung bình, Insertion Sort cho kết quả trung bình với thời gian phức tạp trung bình là O(n^2).
Các biến thể khác trong Insertion Sort
Có một số biến thể của thuật toán Insertion Sort, bao gồm:
- Insertion Sort với giảm dần: thứ tự các phần tử được sắp xếp từ lớn đến nhỏ.
- Insertion Sort tối ưu hoá: sử dụng các tối ưu hoá như tìm kiếm nhị phân để tìm ra vị trí phù hợp cho phần tử được chèn.
- Insertion Sort với chỉ số lớn: thay vì chỉ sử dụng một vị trí, thuật toán sẽ sử dụng một chỉ số lớn để tìm vị trí chèn phù hợp.
- Insertion Sort với Binary Insertion Sort: sử dụng tìm kiếm nhị phân để tìm vị trí phù hợp cho phần tử được chèn.
