Cách viết thuật toán Sắp xếp chèn (Insertion Sort) trong Python

Thuật toán sắp xếp chèn (insertion sort) trong Python hoạt động giống như sắp xếp bài chơi. Để dùng insertion sort, bạn tạo hai danh sách: một đã sắp xếp và một chưa sắp xếp. Bạn so sánh từng mục trong danh sách chưa sắp xếp cho đến khi mục đó được sắp xếp. Insertion sort là thuật toán tiêu chuẩn phổ biến trong Python.

Bạn có bao giờ sắp xếp bài bài trong tay chưa? Đó là một cách để hình dung khái niệm insertion sort trong Python. Khi bạn cần sắp xếp danh sách chỉ có vài phần tử, insertion sort là lựa chọn phù hợp.

Sắp xếp chèn đặt một phần tử chưa sắp xếp vào vị trí đúng của nó sau mỗi lần lặp trong mảng.

Trong hướng dẫn này, chúng ta sẽ nói về insertion sort là gì và cách nó hoạt động. Chúng ta sẽ thảo luận cách triển khai insertion sort trong Python, kèm ví dụ, để bạn có thể bắt đầu với thuật toán sắp xếp này.

Sắp xếp chèn (Insertion Sort) trong Python là gì?

Insertion sort chia một danh sách thành hai danh sách con: đã sắp xếp (sorted) và chưa sắp xếp (unsorted). Sau đó so sánh từng phần tử trong danh sách chưa sắp xếp và tiếp tục cho đến khi mọi mục trong danh sách đều được sắp xếp.

Thuật toán insertion sort di chuyển mục đã sắp xếp vào danh sách con đã sắp xếp và loại bỏ nó khỏi danh sách con chưa sắp xếp. Cả hai danh sách con đều là một phần của cùng một mảng, nhưng chúng phân biệt mục nào đã sắp xếp.

Bạn có thể nghĩ về insertion sort như cách bạn sắp xếp bộ bài trong tay khi chơi bài.

Bạn sẽ đi qua từng lá bài một và so sánh chúng với nhau. Các lá bài đã sắp xếp sẽ xuất hiện ở bên trái tay. Các lá bài chưa sắp xếp xuất hiện ở bên phải cho đến khi bạn sắp xếp hết tất cả.

Sắp xếp chèn Python hoạt động như thế nào?

Hãy bắt tay vào việc và sắp xếp một mảng dùng thuật toán insertion sort. Xét mảng chưa sắp xếp sau:

Trong insertion sort, phần tử đầu tiên được coi là đã sắp xếp. Phần tử thứ hai được lưu trong biến riêng. Ta gọi biến này là current_number.

Đã sắp xếp	current_number
9	4	3	5

Ta cần so sánh current_number với mục ở vị trí đầu tiên trong mảng. Nếu current_number lớn hơn phần tử đầu tiên, nó giữ nguyên vị trí. Ngược lại, current_number được di chuyển lên trước phần tử đầu tiên.

4 không lớn hơn 9, nên hai phần tử này đổi chỗ.

Hai phần tử đầu tiên trong danh sách đã được sắp xếp. Tiếp theo, ta thay đổi giá trị current_number thành mục thứ ba trong danh sách và so sánh nó với tất cả các mục bên trái nó.

current_number trở thành 3. Ta cần so sánh:

3 có lớn hơn 9 không? Không, nên 3 được chèn trước 9.
3 có lớn hơn 4 không? Không, nên 3 được di chuyển trước 4.

Danh sách bây giờ trông như sau:

Quá trình này lặp lại cho đến khi danh sách được sắp xếp. Danh sách của ta chỉ còn một lượt so sánh nữa vì nó chỉ chứa bốn giá trị. Ở vòng lặp tiếp theo, 5 trở thành current_number.

5 có lớn hơn 9 không? Không, nên 5 di chuyển trước 9.

Không còn so sánh nào vì 5 là số cuối cùng trong danh sách đã sắp xếp. Sau vòng lặp này, mảng đã được sắp xếp:

Rất đơn giản! Trong insertion sort của ta, ta luôn giữ các giá trị đã sắp xếp ở bên trái danh sách. Các giá trị chưa sắp xếp xuất hiện ở bên phải.

Đối với mỗi lần lặp trong danh sách, ta so sánh current_number với tất cả các mục chưa sắp xếp. Quá trình này lặp lại cho đến khi danh sách được sắp xếp.

Cách viết Insertion Sort trong Python

Việc đi qua insertion sort trên giấy là ổn. Bây giờ là lúc đi vào chi tiết và triển khai insertion sort trong Python.

Viết hàm sắp xếp

Ta bắt đầu bằng cách viết hàm Python thực hiện sắp xếp:

def sortNumbers(toSort):
    for number in range(1, len(toSort)):
        current_number = toSort[number]
        i = number - 1
        while i >= 0 and current_number < toSort[i]:
            toSort[i + 1] = toSort[i]
            i -= 1
        toSort[i + 1] = current_number

Hãy đi qua cách hoạt động. Trong hàm sortNumbers, ta tạo vòng lặp for Python duyệt qua mọi số trong danh sách. Sau đó, ta đặt phần tử đầu tiên làm giá trị đã sắp xếp bằng cách gán nó cho biến current_number.

Ta lặp qua mọi mục trong danh sách Python chưa sắp xếp (mọi mục sau current_number). Sau đó, ta so sánh current_number với mỗi số bên trái nó. Sau khi điều này xảy ra, ta đặt giá trị của current_number bằng phần tử tiếp theo trong danh sách.

Viết chương trình chính

Ta cần viết chương trình chính thực thi insertion sort:

numbers = [9, 4, 3, 5]
sortNumbers(numbers)
print(numbers)

Kết quả trả về:

[3, 4, 5, 9]

Danh sách đã được sắp xếp theo thứ tự tăng dần! Chúc mừng bạn đã đến đây.

Sắp xếp chèn Python: Thứ tự giảm dần

Insertion sort có thể sắp xếp số theo thứ tự giảm dần. Để làm được điều này, bạn cần đảo dấu "nhỏ hơn" (<) trong vòng lặp while thành dấu "lớn hơn":

while i >= 0 and current_number > toSort[i]:

Dòng mã này, thay thế vào ví dụ trên, sẽ sắp xếp các mục trong danh sách theo thứ tự ngược.

Khi nào nên dùng Insertion Sort?

Insertion sort phù hợp nhất khi dữ liệu trong danh sách gần như đã được sắp xếp, hoặc khi bạn sắp xếp danh sách nhỏ. Có các thuật toán hiệu quả hơn cho danh sách lớn, ví dụ: merge sort hoặc quick sort.

Insertion sort nhanh hơn bubble sort.

Insertion sort hữu ích để biết. Biết cách triển khai insertion sort cho bạn thêm một loại sắp xếp có thể dùng.

Insertion sort ít phức tạp hơn một số thuật toán sắp xếp khác. Khi bạn đã học cách viết insertion sort, bạn sẽ gần hơn với việc học các thuật toán phức tạp hơn như merge sort.

Phân tích độ phức tạp của Insertion Sort Python

Giống như mọi thuật toán, quan trọng cần xem xét độ phức tạp tốt nhất, xấu nhất, và trung bình. Điều này cho ta biết thuật toán hiệu quả như thế nào trong công việc của nó: sắp xếp danh sách.

Độ phức tạp xấu nhất và trung bình là O(n²). Điều này nghĩa là thuật toán sẽ chậm lại theo cấp số nhân khi bạn thêm nhiều giá trị hơn để sắp xếp.

Trường hợp tốt nhất là O(n). Điều này xảy ra khi chạy thuật toán trên danh sách đã sắp xếp. Thuật toán kiểm tra các mục đã sắp xếp và dừng lại.

Bạn có thể tìm hiểu thêm về cách biểu diễn độ phức tạp thuật toán trong loạt bài hai phần về Ký hiệu Big O của chúng tôi.

Kết luận

Insertion sort giống như sắp xếp bộ bài trong tay khi chơi bài. Bạn giữ hai danh sách: danh sách mục đã sắp xếp và danh sách mục cần sắp xếp. Sau đó, bạn đi qua danh sách chưa sắp xếp và điều chỉnh vị trí cho đến khi tất cả đều được sắp xếp.

Bạn đang tìm thêm tài nguyên ngôn ngữ lập trình Python? Xem hướng dẫn hoàn chỉnh "Cách học Python" của chúng tôi. Bạn sẽ tìm thấy mẹo hàng đầu về cách học Python và danh sách khóa học trực tuyến, sách, và tài nguyên khác.