Sắp xếp chèn: Thuật toán với C, C++, Java, Python Các ví dụ

Sắp xếp chèn là gì?

Sắp xếp chèn là một trong những thuật toán sắp xếp so sánh được sử dụng để sắp xếp các phần tử bằng cách lặp lại từng phần tử một và đặt phần tử vào đúng vị trí của nó.

Mỗi phần tử được chèn tuần tự vào danh sách đã được sắp xếp. Kích thước của danh sách đã được sắp xếp ban đầu là một. Thuật toán sắp xếp chèn đảm bảo rằng k phần tử đầu tiên được sắp xếp sau lần lặp thứ k.

Đặc điểm của thuật toán sắp xếp chèn

Thuật toán sắp xếp chèn có những đặc điểm quan trọng sau:

• Đây là một kỹ thuật sắp xếp ổn định nên không làm thay đổi thứ tự tương đối của các phần tử bằng nhau.
• Nó hiệu quả đối với các tập dữ liệu nhỏ hơn nhưng không hiệu quả đối với các danh sách lớn hơn.
• Sắp xếp chèn có tính thích ứng, giúp giảm tổng số bước nếu nó được sắp xếp một phần. Mảng được cung cấp làm đầu vào để làm cho nó hiệu quả.

Chèn như thế nào Operacông việc à?

Trong thuật toán Sắp xếp chèn, thao tác chèn được sử dụng để sắp xếp các phần tử chưa được sắp xếp. Nó giúp chèn một phần tử mới vào danh sách đã được sắp xếp.

Mã giả của thao tác chèn:

Xét danh sách A gồm N phần tử.

A[N-1] is the element to be inserted in the sorted sublist A[0..N-2].
For i = N-1 to 1:
if A[i] < A[i-1], then swap A[i] and A[i-1]
else Stop   

Trong ví dụ trên, phần tử 6 mới sẽ được chèn vào danh sách đã được sắp xếp.

Bước 1) So với phần tử liền kề bên trái của A[5], 9 > 6, chúng ta hoán đổi vị trí của 9 và 6. Bây giờ phần tử 6 được chuyển sang A[4].

Bước 2) Bây giờ, chúng ta so sánh A[4] và A[3], và thấy rằng A[3] > A[4], chúng ta lại hoán đổi vị trí của 6 và 8.

Bước 3) Bây giờ hãy so sánh A[3] và A[2], vì A[2] > A[3] hoán đổi vị trí của 7 và 6.

Bước 4) Chúng ta so sánh A[1] và A[2], và khi A[1] < A[2], tức là phần tử liền kề bên trái không còn lớn hơn. Bây giờ chúng ta kết luận rằng 6 đã được chèn đúng và chúng ta dừng thuật toán ở đây.

Cách sắp xếp chèn hoạt động

Thao tác chèn được thảo luận ở trên là xương sống của sắp xếp chèn. Quy trình chèn được thực thi trên mọi phần tử và cuối cùng, chúng ta nhận được danh sách đã sắp xếp.

Hình ví dụ trên thể hiện hoạt động của sắp xếp chèn trong cấu trúc dữ liệu. Ban đầu, chỉ có một phần tử trong danh sách con được sắp xếp, tức là 4. Sau khi chèn A[1] tức là 3, kích thước của danh sách con đã sắp xếp tăng lên 2.

C++ Chương trình sắp xếp chèn

#include <iostream>
using namespace std;

int main(){
    //unsorted list
    int unsorted[] = {9,8,7,6,5,4,3,3,2,1};
    
    //size of list
    int size_unsorted = sizeof(unsorted) / sizeof(unsorted[0]); 

    //printing unsorted list
    cout << "\nUnsorted: ";
    for(int i = 0 ; i < size_unsorted ; i++){
        cout << unsorted[i] << " ";
    } 

    int current_element,temp;

    for(int i = 1; i < size_unsorted; i++){        
        current_element = unsorted[i];
        for(int j = i-1; j >= 0 && unsorted[j] > current_element; j--){
            //swapping if current element is lesser
            temp = unsorted[j+1];
            unsorted[j+1] = unsorted[j];
            unsorted[j] = temp;
        }
    }

    //printing sorted list
    cout << "\nSorted: ";
    for(int i = 0 ; i < size_unsorted ; i++){
        cout << unsorted[i] << " ";
    } 

    return 0;
}

Đầu ra:

Unsorted: 9 8 7 6 5 4 3 3 2 1 
Sorted: 1 2 3 3 4 5 6 7 8 9

Mã C để sắp xếp chèn

#include <stdio.h>
int main() {
    //unsorted list
    int unsorted[] = {9,8,7,6,5,4,3,3,2,1};

    //size of list
    int size_unsorted = sizeof(unsorted) / sizeof(unsorted[0]);

    //printing unsorted list
    printf("\nUnsorted: ");
    for(int i = 0 ; i < size_unsorted ; i++){
        printf("%d ", unsorted[i]);
    }

    int current_element, temp;

    for(int i = 1; i < size_unsorted; i++){
        current_element = unsorted[i];
        for(int j = i-1; j >= 0 && unsorted[j] > current_element; j--){
            //swapping if current element is lesser
            temp = unsorted[j+1];
            unsorted[j+1] = unsorted[j];
            unsorted[j] = temp;
        }
    }

    //printing sorted list
    printf("\nSorted: ");
    for(int i = 0 ; i < size_unsorted ; i++){
        printf("%d ", unsorted[i]);
    }

    return 0;
}

Đầu ra:

Output:
Unsorted: 9 8 7 6 5 4 3 3 2 1 
Sorted: 1 2 3 3 4 5 6 7 8 9

Python Chương trình sắp xếp chèn

#unsorted list
unsorted = [9,8,7,6,5,4,3,3,2,1]

#size of list
size_unsorted = len(unsorted)

#printing unsorted list
print("\nUnsorted: ", end="")
for i in range(size_unsorted):
    print(unsorted[i], end=" ")

for i in range(1, size_unsorted):
    current_element = unsorted[i]
    j = i - 1
    while j >= 0 and unsorted[j] > current_element:
        #swapping if current element is lesser
        unsorted[j+1], unsorted[j] = unsorted[j], unsorted[j+1]
        j -= 1

#printing sorted list
print("\nSorted: ", end="")
for i in range(size_unsorted):
    print(unsorted[i], end=" ")

Đầu ra:

Unsorted: 9 8 7 6 5 4 3 3 2 1 
Sorted: 1 2 3 3 4 5 6 7 8 9

Thuộc tính của sắp xếp chèn

Dưới đây là các thuộc tính quan trọng của Sắp xếp chèn:

• Trực tuyến: Sắp xếp chèn có thể sắp xếp các phần tử khi nó nhận được. Nghĩa là, nếu chúng ta đã sắp xếp một danh sách các phần tử và nối thêm một số phần tử vào danh sách thì chúng ta không cần phải chạy lại toàn bộ quy trình sắp xếp. Thay vào đó, chúng ta chỉ cần lặp lại các phần tử mới được thêm vào.
• Tại chỗ: Độ phức tạp về không gian của thuật toán sắp xếp chèn là hằng số và không yêu cầu thêm không gian. Thuật toán này sắp xếp các phần tử tại chỗ.
• Ổn định: Trong sắp xếp chèn, chúng ta không hoán đổi các phần tử nếu giá trị của chúng bằng nhau. Ví dụ: hai phần tử x và y bằng nhau và x xuất hiện trước y trong danh sách chưa sắp xếp, khi đó trong danh sách đã sắp xếp, x sẽ xuất hiện trước y. Điều này làm cho việc sắp xếp chèn ổn định.
• Thích ứng: A thuật toán sắp xếp có tính thích ứng nếu mất ít thời gian hơn nếu các phần tử đầu vào hoặc tập hợp con của các phần tử đã được sắp xếp. Như chúng ta đã thảo luận ở trên, thời gian chạy tốt nhất của sắp xếp chèn là O(N) và thời gian chạy tệ nhất là O(N^2). Sắp xếp chèn là một trong những thuật toán sắp xếp thích ứng.

Độ phức tạp của sắp xếp chèn

Không gian phức tạp

Thuật toán sắp xếp chèn không yêu cầu thêm không gian để sắp xếp các phần tử, độ phức tạp về không gian là hằng số, tức là O(1).

Thời gian phức tạp

Vì sắp xếp chèn lặp lại từng phần tử cùng lúc, nên cần N-1 lần để sắp xếp N phần tử. Với mỗi lần, có thể thực hiện hoán đổi bằng không nếu các phần tử đã được sắp xếp hoặc hoán đổi nếu các phần tử được sắp xếp theo thứ tự giảm dần.

• Đối với lượt 1, số lần hoán đổi tối thiểu được yêu cầu là 1 và số lần hoán đổi tối đa được yêu cầu là XNUMX.
• Đối với lượt 2, số lần hoán đổi tối thiểu được yêu cầu là 2 và số lần hoán đổi tối đa được yêu cầu là XNUMX.
• Đối với pass N, số lần hoán đổi tối thiểu được yêu cầu là 0 và số lần hoán đổi tối đa được yêu cầu là N.
• Giá trị hoán đổi tối thiểu là 0, do đó độ phức tạp thời gian tốt nhất là O(N) khi lặp N lần.
• Tổng số lần hoán đổi tối đa là (1+2+3+4+..+N) i. N(N+1)/2, độ phức tạp thời gian tệ nhất là O(N^2).

Sau đây là độ phức tạp thời gian quan trọng của thuật toán sắp xếp chèn:

• Độ phức tạp trường hợp xấu nhất: O(n2): Sắp xếp một mảng theo thứ tự giảm dần khi nó theo thứ tự tăng dần là trường hợp xấu nhất.
• Độ phức tạp trường hợp tốt nhất: O(n): Độ phức tạp trường hợp tốt nhất xảy ra khi mảng đã được sắp xếp, vòng lặp bên ngoài chạy n lần trong khi vòng lặp bên trong không chạy lần nào. Chỉ có n lần so sánh. Vì vậy, trong trường hợp này, độ phức tạp là tuyến tính.
• Độ phức tạp trường hợp trung bình: O(n2): Xảy ra khi các phần tử của mảng xuất hiện theo thứ tự lộn xộn, không tăng dần cũng không giảm dần.

Tổng kết

• Sắp xếp chèn là một phương pháp thuật toán sắp xếp dựa trên sự so sánh.
• Đây là một kỹ thuật sắp xếp ổn định nên không làm thay đổi thứ tự tương đối của các phần tử bằng nhau.
• Trên mọi phần tử, thao tác chèn được sử dụng để chèn phần tử vào danh sách con đã sắp xếp.
• Sắp xếp chèn là một thuật toán sắp xếp tại chỗ.
• Độ phức tạp thời gian tệ nhất và trung bình của thuật toán sắp xếp chèn là bậc hai, tức là O(N^2).
• Sắp xếp chèn không yêu cầu bất kỳ không gian phụ trợ nào.