Rate this post

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:

Tóm tắt nội dung

Giới thiệu về Insertion Sort

Insertion Sort là một thuật toán sắp xếp đơn giản và phổ biến trong lĩnh vực khoa học máy tính. Nó hoạt động bằng cách chia mảng thành hai phần, một phần đã sắp xếp và một phần chưa sắp xếp. Thuật toán sẽ lần lượt chọn các phần tử từ phần chưa sắp xếp và chèn chúng vào đúng vị trí trong phần đã sắp xếp.

Cách thức hoạt động của Insertion Sort như sau:

Đầu tiên, phần tử đầu tiên của mảng được coi là một mảng đã sắp xếp ban đầu.
Tiếp theo, thuật toán duyệt qua các phần tử còn lại của mảng chưa sắp xếp.
Với mỗi phần tử chưa sắp xếp, thuật toán so sánh nó với các phần tử trong mảng đã sắp xếp, từ phải qua trái.
Khi tìm thấy vị trí phù hợp, thuật toán chèn phần tử vào vị trí đó và dồn các phần tử phía sau sang phải một vị trí để tạo chỗ trống cho phần tử mới.
Quá trình này tiếp tục cho đến khi tất cả các phần tử trong mảng chưa sắp xếp được chèn vào đúng vị trí của mình trong mảng đã sắp xếp.

Insertion Sort là một thuật toán đơn giản và dễ hiểu, phù hợp với việc sắp xếp mảng có kích thước nhỏ hoặc đã gần sắp xếp. Tuy nhiên, độ phức tạp thời gian của thuật toán là O(n^2), nên không hiệu quả với các mảng lớn.

Mặc dù Insertion Sort không phải là thuật toán sắp xếp nhanh nhất, nhưng nó có một số ưu điểm, bao gồm:

Dễ hiểu và dễ cài đặt.
Không yêu cầu bộ nhớ phụ.
Tốt đối với các tình huống mảng gần sắp xếp hoặc mảng có kích thước nhỏ.

Tuy nhiên, khi xử lý các tập dữ liệu lớn, nên xem xét sử dụng các thuật toán sắp xếp hiệu quả hơn như Quick Sort hoặc Merge Sort.

Xem thêm Thuật toán Shell Sort là gì ?

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

Xem thêm bubble sort trong c++

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.

Độ phức tạp thời gian và không gian

Độ phức tạp thời gian của thuật toán Insertion Sort là O(n^2), trong đó n là số phần tử trong mảng cần sắp xếp. Cụ thể, thuật toán sẽ thực hiện n-1 vòng lặp để sắp xếp mảng. Trong mỗi vòng lặp, thuật toán sẽ so sánh phần tử hiện tại với các phần tử đã sắp xếp và chèn phần tử đó vào đúng vị trí. Với mỗi vòng lặp, số lần so sánh tăng lên 1 đơn vị, và với mỗi lần so sánh, số lần dịch chuyển các phần tử phía sau tăng lên tối đa n-1 lần. Tổng số phép so sánh và dịch chuyển trong Insertion Sort là khoảng (n^2)/2, do đó độ phức tạp thời gian là O(n^2).

Độ phức tạp không gian của thuật toán Insertion Sort là O(1), tức là không yêu cầu bộ nhớ phụ phụ thuộc vào kích thước của dữ liệu đầu vào. Thuật toán chỉ sử dụng một số biến cục bộ để lưu trữ các phần tử tạm thời và chỉnh sửa mảng ban đầu mà không tạo thêm bất kỳ mảng hoặc cấu trúc dữ liệu nào khác.

Tuy nhiên, độ phức tạp không gian cũng có thể được đánh giá theo khía cạnh sử dụng bộ nhớ của các biến tạm thời và mảng đầu vào. Nếu mảng đầu vào là một mảng mới được tạo ra để lưu trữ dữ liệu sắp xếp, thì độ phức tạp không gian là O(n), với n là kích thước của mảng.

Tóm lại, Insertion Sort có độ phức tạp thời gian O(n^2) và độ phức tạp không gian O(1) (hoặc O(n) nếu sử dụng một mảng tạm thời).

So sánh Insertion Sort với các thuật toán sắp xếp khác

Insertion Sort là một thuật toán sắp xếp đơn giản và dễ hiểu, nhưng có độ phức tạp thời gian tương đối cao trong trường hợp số phần tử lớn. Dưới đây là một so sánh giữa Insertion Sort và một số thuật toán sắp xếp khác:

Bubble Sort: Bubble Sort và Insertion Sort có độ phức tạp thời gian tương tự là O(n^2). Tuy nhiên, Bubble Sort thực hiện các hoán đổi liên tiếp trong quá trình sắp xếp, trong khi Insertion Sort chèn các phần tử vào vị trí đúng. Vì vậy, Insertion Sort có thể nhanh hơn trong một số trường hợp khi dữ liệu đã gần sắp xếp.
Selection Sort: Selection Sort cũng có độ phức tạp thời gian O(n^2). So với Insertion Sort, Selection Sort tìm kiếm phần tử nhỏ nhất và hoán đổi nó với vị trí hiện tại trong mỗi vòng lặp. Insertion Sort chèn phần tử vào vị trí đúng trong mỗi vòng lặp. Tuy nhiên, cả hai thuật toán đều có độ phức tạp tương tự và không có sự khác biệt đáng kể trong hiệu suất.
Quick Sort: Quick Sort là một thuật toán sắp xếp nhanh hơn với độ phức tạp trung bình là O(n log n). Quick Sort sử dụng phương pháp chia để trị và đệ quy để sắp xếp các phần tử. So với Insertion Sort, Quick Sort thường nhanh hơn với số lượng lớn các phần tử. Tuy nhiên, Quick Sort yêu cầu nhiều bước phân chia và hoán đổi dữ liệu, trong khi Insertion Sort chỉ chèn phần tử vào vị trí đúng.
Merge Sort: Merge Sort là một thuật toán sắp xếp ổn định với độ phức tạp trung bình là O(n log n). Merge Sort sắp xếp dữ liệu bằng cách chia mảng thành các phần nhỏ hơn, sắp xếp từng phần nhỏ và sau đó trộn chúng lại. Merge Sort thường hiệu quả hơn Insertion Sort với số lượng lớn các phần tử và có thể sắp xếp mảng theo thứ tự tăng dần hoặc giảm dần mà không ảnh hưởng đến hiệu suất.

Tóm lại, Insertion Sort là một thuật toán sắp xếp đơn giản và hiệu quả trong trường hợp số lượng phần tử nhỏ hoặc gần sắp xếp. Tuy nhiên, với số lượng phần tử lớn và yêu cầu hiệu suất cao, các thuật toán sắp xếp như Quick Sort và Merge Sort thường được ưu tiên sử dụng.

Xem thêm Gnome Sort là gì ?

Ứng dụng và tối ưu hóa

Insertion Sort thường được sử dụng trong các trường hợp sau:

Dữ liệu gần như đã sắp xếp: Khi dữ liệu đã gần sắp xếp, Insertion Sort hoạt động rất hiệu quả với độ phức tạp thời gian gần như tuyến tính O(n). Do đó, nó thích hợp để sử dụng khi dữ liệu có thể được xếp sắp trước khi áp dụng thuật toán sắp xếp.
Dữ liệu nhỏ: Với một lượng nhỏ các phần tử, Insertion Sort có thể là một lựa chọn tốt. Vì nó không yêu cầu quá nhiều bộ nhớ và đơn giản để triển khai, nó có thể hoạt động tốt với các tập dữ liệu nhỏ.
Sắp xếp các danh sách liên kết: Insertion Sort cũng có thể được sử dụng để sắp xếp các danh sách liên kết. Với danh sách liên kết, Insertion Sort không cần phải thực hiện các hoán đổi dữ liệu, mà chỉ cần điều chỉnh các liên kết giữa các nút.

Tuy nhiên, đối với các tập dữ liệu lớn và yêu cầu hiệu suất cao, Insertion Sort có thể không phải là lựa chọn tối ưu. Những thuật toán sắp xếp khác như Quick Sort, Merge Sort, hoặc Heap Sort thường được sử dụng vì có độ phức tạp thời gian tốt hơn.

Để tối ưu hóa Insertion Sort, có thể áp dụng một số cải tiến như:

Sử dụng Binary Insertion Sort: Thay vì tìm kiếm tuyến tính để tìm vị trí chèn, Binary Insertion Sort sử dụng tìm kiếm nhị phân để tìm vị trí chèn. Điều này giúp giảm đáng kể số lần so sánh trong quá trình chèn, cải thiện hiệu suất.
Sử dụng Shell Sort: Shell Sort là một biến thể của Insertion Sort, trong đó các phần tử được chia thành các nhóm con dựa trên khoảng cách và sau đó sắp xếp các nhóm con bằng Insertion Sort. Shell Sort có độ phức tạp thời gian tốt hơn Insertion Sort đối với các tập dữ liệu lớn.
Sử dụng các thuật toán sắp xếp khác: Đối với các tập dữ liệu lớn, các thuật toán sắp xếp như Quick Sort, Merge Sort hoặc Heap Sort thường được ưu tiên hơn Insertion Sort vì độ phức tạp thời gian tốt hơn.

Algorithm, C/C++

Insertion Sort trong c++