Sắp xếp chèn DSA

Sắp xếp chèn

Thuật toán Sắp xếp chèn sử dụng một phần của mảng để giữ các giá trị đã được sắp xếp và phần còn lại của mảng để giữ các giá trị chưa được sắp xếp.

Thuật toán lấy một giá trị tại một thời điểm từ phần chưa được sắp xếp của mảng và đặt nó vào đúng vị trí trong phần đã sắp xếp của mảng, cho đến khi mảng được sắp xếp.

Tiếp tục đọc để hiểu đầy đủ về thuật toán Sắp xếp chèn và cách tự triển khai nó.

Chạy qua thủ công

Trước khi triển khai thuật toán Sắp xếp chèn trong ngôn ngữ lập trình, chúng ta hãy chạy qua một mảng ngắn theo cách thủ công để lấy ý tưởng.

Bước 1: Chúng ta bắt đầu với một mảng chưa được sắp xếp.

Bước 2: Chúng ta có thể coi giá trị đầu tiên là phần được sắp xếp ban đầu của mảng. Nếu nó chỉ là một giá trị thì nó phải được sắp xếp, phải không?

Bước 3: Giá trị tiếp theo 12 bây giờ sẽ được chuyển vào đúng vị trí trong phần được sắp xếp của mảng. Nhưng 12 cao hơn 7 nên nó đã ở đúng vị trí rồi.

Bước 4: Xét giá trị tiếp theo 9.

Bước 5: Giá trị 9 bây giờ phải được di chuyển vào đúng vị trí bên trong phần được sắp xếp của mảng, vì vậy chúng ta di chuyển 9 vào giữa 7 và 12.

Bước 6: Giá trị tiếp theo là 11.

Bước 7: Chúng tôi di chuyển nó vào giữa 9 và 12 trong phần được sắp xếp của mảng.

Bước 8: Giá trị cuối cùng cần chèn vào đúng vị trí là 3.

Bước 9: Chúng ta chèn 3 vào trước tất cả các giá trị khác vì đây là giá trị thấp nhất.

Cuối cùng, mảng được sắp xếp.

Chạy mô phỏng bên dưới để xem các bước ở trên hoạt hình:

Chạy qua thủ công: Chuyện gì đã xảy ra?

Chúng ta phải hiểu những gì đã xảy ra ở trên để hiểu đầy đủ về thuật toán, để có thể triển khai thuật toán bằng ngôn ngữ lập trình.

Giá trị đầu tiên được coi là phần được sắp xếp ban đầu của mảng.

Mọi giá trị sau giá trị đầu tiên phải được so sánh với các giá trị trong phần được sắp xếp của thuật toán để có thể chèn vào đúng vị trí.

Thuật toán sắp xếp chèn phải chạy qua mảng 4 lần, để sắp xếp mảng 5 giá trị vì chúng ta không phải sắp xếp giá trị đầu tiên.

Và mỗi khi thuật toán chạy qua mảng, phần chưa được sắp xếp còn lại của mảng sẽ trở nên ngắn hơn.

Bây giờ chúng ta sẽ sử dụng những gì đã học để triển khai thuật toán Sắp xếp chèn trong ngôn ngữ lập trình.

Triển khai sắp xếp chèn

Để triển khai thuật toán Sắp xếp chèn trong ngôn ngữ lập trình, chúng ta cần:

1. Một mảng có các giá trị cần sắp xếp.
2. Vòng lặp bên ngoài chọn giá trị cần sắp xếp. Đối với một mảng có các giá trị \(n\), vòng lặp bên ngoài này bỏ qua giá trị đầu tiên và phải chạy \(n-1\) lần.
3. Một vòng lặp bên trong đi qua phần được sắp xếp của mảng để tìm vị trí chèn giá trị. Nếu giá trị cần sắp xếp nằm ở chỉ mục \(i\), thì phần được sắp xếp của mảng bắt đầu ở chỉ mục \(0\) và kết thúc ở chỉ mục \(i-1\).

Mã kết quả trông như thế này:

 my_array = [64, 34, 25, 12, 22, 11, 90, 5]

n = len(my_array)
for i in range(1,n):
    insert_index = i
    current_value = my_array.pop(i)
    for j in range(i-1, -1, -1):
        if my_array[j] > current_value:
            insert_index = j
    my_array.insert(insert_index, current_value)

print("Sorted array:", my_array)

Cải tiến sắp xếp chèn

Sắp xếp chèn có thể được cải thiện thêm một chút.

Cách đoạn mã trên trước tiên loại bỏ một giá trị rồi chèn nó vào một nơi khác rất trực quan. Đó là cách bạn thực hiện Sắp xếp chèn một cách vật lý bằng một ván bài chẳng hạn. Nếu các thẻ có giá trị thấp được sắp xếp ở bên trái, bạn lấy một thẻ mới chưa được sắp xếp và chèn nó vào đúng vị trí giữa các thẻ đã được sắp xếp khác.

Vấn đề với cách lập trình này là khi xóa một giá trị khỏi mảng, tất cả các phần tử ở trên phải được dịch chuyển xuống một vị trí chỉ mục:

Và khi chèn lại giá trị đã bị loại bỏ vào mảng, cũng có nhiều thao tác dịch chuyển phải thực hiện: tất cả các phần tử sau phải dịch chuyển lên một vị trí để nhường chỗ cho giá trị được chèn:

Thao tác dịch chuyển này có thể mất rất nhiều thời gian, đặc biệt đối với mảng có nhiều phần tử.

Giải pháp cải tiến

Chúng ta có thể tránh hầu hết các thao tác dịch chuyển này bằng cách chỉ dịch chuyển các giá trị cần thiết:

Trong hình ảnh trên, giá trị 7 đầu tiên được sao chép, sau đó giá trị 11 và 12 được dịch chuyển lên một vị trí trong mảng và giá trị cuối cùng 7 được đặt ở vị trí trước đó là giá trị 11.

Số lượng thao tác chuyển số giảm từ 12 xuống 2 trong trường hợp này.

Cải tiến này được thực hiện trong ví dụ dưới đây:

 my_array = [64, 34, 25, 12, 22, 11, 90, 5]

n = len(my_array)
for i in range(1,n):
    insert_index = i
    current_value = my_array[i]
    for j in range(i-1, -1, -1):
        if my_array[j] > current_value:
            my_array[j+1] = my_array[j]
            insert_index = j
        else:
            break
    my_array[insert_index] = current_value

print("Sorted array:", my_array)

Điều cũng được thực hiện trong đoạn mã trên là thoát ra khỏi vòng lặp bên trong. Đó là vì không cần tiếp tục so sánh các giá trị khi chúng ta đã tìm đúng vị trí cho giá trị hiện tại.

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

Để có giải thích chung về độ phức tạp của thời gian, hãy truy cập trang này .

Để được giải thích kỹ lưỡng và chi tiết hơn về độ phức tạp về thời gian Sắp xếp chèn, hãy truy cập trang này .

Sắp xếp lựa chọn sắp xếp một mảng các giá trị \(n\).

Trung bình, mỗi giá trị phải được so sánh với khoảng \(\frac{n}{2}\) giá trị khác để tìm ra vị trí cần chèn giá trị đó.

Và Sắp xếp lựa chọn phải chạy vòng lặp để chèn một giá trị vào đúng vị trí của nó khoảng \(n\) lần.

Chúng tôi nhận được độ phức tạp về thời gian cho Sắp xếp chèn:

\[ O( \frac{n}{2} \cdot n) = \underline{\underline{O(n^2)}} \]

Độ phức tạp về thời gian của Sắp xếp chèn có thể được hiển thị như sau:

Sử dụng mô phỏng bên dưới để xem độ phức tạp về mặt lý thuyết \(O(n^2)\) (đường màu đỏ) so với số lượng thao tác của Sắp xếp chèn thực tế.

Đối với Sắp xếp chèn, có sự khác biệt lớn giữa các trường hợp tốt nhất, trung bình và trường hợp xấu nhất. Bạn có thể thấy điều đó bằng cách chạy các mô phỏng khác nhau ở trên.

Tiếp theo là Quicksort. Cuối cùng chúng ta sẽ thấy một thuật toán sắp xếp nhanh hơn!