Thuật toán sắp xếp chèn bằng ngôn ngữ C. C++, Java, Python Các ví dụ

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

Thuật toán sắp xếp chèn (Insertion Sort) 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 qua từng phần tử một và đặt phần tử đó vào vị trí chính xác của nó trong một vùng đã được sắp xếp.

Mỗi phần tử được chèn tuần tự vào một danh sách đã được sắp xếp. Kích thước ban đầu của danh sách đã được sắp xếp 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ủa vòng lặp ngoài.

Vì thuật toán sắp xếp chèn xây dựng kết quả từng bước một, nên nó dễ dạy, dễ gỡ lỗi và là một nền tảng vững chắc cho các dữ liệu đầu vào rất nhỏ, nơi mà các thuật toán phức tạp hơn sẽ làm tăng chi phí mà không mang lại lợi ích đáng 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 giải thích cách hoạt động của nó trên các khối lượng công việc thực tế:

• Đâ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.
• Phương pháp này hiệu quả với các tập dữ liệu nhỏ nhưng không hiệu quả với các danh sách lớn hơn, nơi mà sự tăng trưởng theo cấp số nhân chiếm ưu thế.
• Thuật toán sắp xếp chèn (Insertion Sort) có khả năng thích ứng, giúp giảm tổng số bước nếu dữ liệu đầu vào đã được sắp xếp một phần. Mảng Dữ liệu đầu vào được cung cấp nhằm mục đích tối ưu hóa hiệu suất vì truy cập ngẫu nhiên cho phép dịch chuyển với thời gian không đổi trong vòng lặp bên trong.
• Đây là thuật toán thực thi tại chỗ, do đó nó không yêu cầu bộ nhớ phụ trợ có dung lượng tương ứng với kích thước dữ liệu đầu vào.

Với những đặc điểm đó, phần tiếp theo sẽ giải thích thao tác chèn cốt lõi, thao tác này cung cấp năng lượng cho mọi lượt xử lý của thuật toán.

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 một danh sách đã được sắp xếp trong khi vẫn giữ nguyên thứ tự hiện có của vùng đã đượ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ử.

// Insert A[N-1] into 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, một phần tử mới có số 6 được chèn vào một danh sách đã được sắp xếp. Các bước tiếp theo như sau: tracvòng lặp bên trong di chuyển khi phần tử mới di chuyển sang trái về phía vị trí chính xác của nó.

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à chúng ta thấy rằng A[3] > A[4], vì vậy 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], chúng ta 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ì A[1] < A[2], phần tử liền kề bên trái không còn lớn hơn nữa. Chúng ta kết luận rằng 6 được chèn đúng cách và chúng ta dừng vòng lặp bên trong ở đây.

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

Thao tác chèn được đề cập ở trên là xương sống của thuật toán Sắp xếp chèn. Quy trình chèn được thực hiện trên mọi phần tử, và cuối cùng, ta nhận được danh sách đã được sắp xếp khi vùng được sắp xếp tăng thêm một phần tử sau mỗi lần duyệt ngoài.

Hình trên minh họa hoạt động của thuật toán Sắp xếp chèn trong một 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 đã được sắp xếp tăng lên 2, và thuật toán tiếp tục mô hình này cho đến khi mọi phần tử đã được đặt vào vị trí.

Sau khi đã trình bày được luồng ý tưởng, các phần tiếp theo sẽ trình bày các ví dụ cụ thể. C++, C, và Python Nhờ đó bạn có thể so sánh cấu trúc vòng lặp giữa các ngôn ngữ lập trình khác nhau.

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

C++ Cách triển khai bên dưới sử dụng hai vòng lặp lồng nhau: vòng lặp ngoài chọn phần tử chưa được sắp xếp tiếp theo, và vòng lặp trong dịch chuyển nó sang trái cho đến khi tìm thấy vị trí chính xác.

#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

C Code cho thuật toán sắp xếp chèn

Nguyên tắc tương tự cũng áp dụng trực tiếp cho ngôn ngữ C. Tiêu chuẩn printf Các lệnh gọi thay thế đầu ra luồng, nhưng mô hình hoán đổi bên trong vòng lặp bên trong giống hệt với C++ phiên bả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

Python hỗ trợ hoán đổi bộ dữ liệuping trong một biểu thức duy nhất, do đó vòng lặp bên trong gọn hơn so với C và của nó. C++ các đối tác tương ứng trong khi vẫn giữ nguyên hành vi thuật toá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à những đặc tính quan trọng của thuật toán Sắp xếp chèn giúp bạn quyết định khi nào nên sử dụng nó:

• Trực tuyến: Thuật toán sắp xếp chèn (Insertion Sort) có thể sắp xếp các phần tử ngay khi nhận được chúng. Nếu chúng ta đã sắp xếp một danh sách các phần tử và thêm các phần tử mới 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 trên 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 lưu trữ. Thuật toán này sắp xếp các phần tử tại chỗ.
• Ổn định: Trong thuật toán 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ụ, nếu 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 được sắp xếp, thì trong danh sách đã được sắp xếp, x vẫn sẽ xuất hiện trước y. Điều này làm cho thuật toán sắp xếp chèn ổn định.
• Thích ứng: A thuật toán sắp xếp Thuật toán sắp xếp chèn được gọi là thích ứng nếu nó mất ít thời gian hơn khi các phần tử đầu vào hoặc một tập hợp con các phần tử đã được sắp xếp. Như đã thảo luận ở trên, thời gian chạy tốt nhất của thuật toán 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

Phần thảo luận về độ phức tạp bên dưới đề cập đến cả mức sử dụng bộ nhớ và thời gian chạy, giúp bạn so sánh thuật toán Sắp xếp chèn với các thuật toán thay thế khác như... Bubble Sắp xếp và Sắp xếp nhanh chóng.

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), vì chỉ sử dụng một vài biến tạm thời bất kể kích thước đầu vào.

Thời gian phức tạp

Vì thuật toán sắp xếp chèn (Insertion Sort) xử lý từng phần tử một, nên nó cần N-1 lượt để sắp xếp N phần tử. Trong mỗi lượt, nó có thể không cần hoán đổi phần tử nào nếu các phần tử đã được sắp xếp, hoặc có thể cần nhiều lần 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) tức là N(N+1)/2, do đó độ phức tạp thời gian tồi tệ nhất là O(N^2).

Dưới đâ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(n^2): Sắp xếp một mảng theo thứ tự giảm dần khi yêu cầu là 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): Trường hợp tốt nhất xảy ra khi mảng đã được sắp xếp; vòng lặp ngoài chạy n lần, trong khi vòng lặp trong không chạy lần nào. Chỉ có n phép so sánh, do đó độ phức tạp là tuyến tính.
• Độ phức tạp trường hợp trung bình: O(n^2): Điều này 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.

Câu Hỏi Thường Gặp