Cách lập trình QuickSort trong Python

Cách lập trình QuickSort trong Python

QuickSort Python chọn phần tử chốt (pivot) và tách các phần tử của mảng (array) thành hai mảng mới. Số lớn hơn chốt vào mảng một; số nhỏ hơn chốt vào mảng kia. Mỗi mảng được sắp xếp rồi tất cả mảng được gộp thành một.

Cách lập trình QuickSort trong Python

Có nhiều thuật toán sắp xếp bạn có thể dùng sắp xếp list trong lập trình. Có insertion sort, bubble sort, và hơn thế nữa. QuickSort là một trong những loại sắp xếp phổ biến nhất.

Trong hướng dẫn này, ta nói về QuickSort là gì và cách hoạt động. Ta đi qua ví dụ QuickSort Python để bạn học cách triển khai.

Không nói thêm, hãy bắt đầu!

QuickSort Python là gì?

Thuật toán QuickSort Python chia mảng thành các mảng con (sub arrays). Thuật toán gọi đệ quy các mảng con này để sắp xếp từng phần tử trong list. Nội dung mảng con được quyết định bởi phần tử chốt (pivot) không được di chuyển vào mảng con mới.

Thuật toán QuickSort dùng chiến lược chia để trị (divide-and-conquer). Nghĩa là nhiệm vụ sắp xếp list được chia thành nhiều nhiệm vụ con. Cuối sắp xếp, kết quả các nhiệm vụ con kết hợp lại trả về list đã sắp xếp.

Trong QuickSort, nhiệm vụ con là đặt chốt cho mỗi danh sách con và sắp xếp phần tử dựa trên giá trị tương đối với chốt.

Khi nào nên dùng QuickSort Python?

QuickSort hữu ích khi độ phức tạp thời gian quan trọng. Vì QuickSort dùng ít không gian bộ nhớ hơn các thuật toán khác, cho hiệu suất tốt hơn.

Bạn chỉ nên dùng QuickSort nếu bạn quen với đệ quy Python. Vì thuật toán QuickSort phụ thuộc vào hàm đệ quy.

QuickSort hiệu quả hơn merge sort trên mảng nhỏ. Tuy nhiên, trên tập dữ liệu lớn, insertion sort hoặc merge sort có thể nhanh hơn.

QuickSort hoạt động như thế nào?

QuickSort chọn một phần tử làm chốt (pivot). Có thể là bất kỳ phần tử nào trong list. Với hướng dẫn này, ta chọn mục cuối cùng trong list (3).

QuickSort so sánh giá trị chốt với mọi số khi lặp qua các mục trong list. Nếu mục lớn hơn số chốt, ta di chuyển số sau chốt; ngược lại, di chuyển số trước chốt:

Giá trị 3 đã di chuyển xuống list. Tất cả mục nhỏ hơn 3 di chuyển sang trái; tất cả giá trị lớn hơn 3 di chuyển sang phải.

Mảng Python được chia thành hai nửa: mục lớn hơn chốt và mục nhỏ hơn chốt.

Khi quá trình bắt đầu, chốt mới bắt đầu trên mỗi nửa. Chốt mới bắt đầu riêng biệt và dùng cùng thuật toán. Đầu tiên, ta đặt giá trị chốt bằng giá trị cuối trong mỗi list:

Tiếp theo, ta di chuyển tất cả giá trị lớn hơn chốt sang phải chốt. Di chuyển tất cả giá trị nhỏ hơn chốt sang trái.

Quá trình này tiếp tục cho đến khi sắp xếp xong list:

Mảng cuối cùng trông như sau:

Ví dụ QuickSort Python

QuickSort cần hai hàm: hàm phân vùng (partition) và hàm QuickSort.

Hãy bắt đầu với hàm partition. Hàm này sẽ phân vùng, hoặc chuẩn bị, mảng dựa trên giá trị phần tử chốt.

Hàm partition sẽ:

1. Chọn phần tử chốt
2. Di chuyển tất cả mục lớn hơn chốt sang phải chốt
3. Di chuyển tất cả mục nhỏ hơn chốt sang trái chốt

Chương trình QuickSort Python

Hãy viết chương trình triển khai thuật toán này:

def prepare(numbers, low, high):
    pivot = numbers[high]
    item = low - 1
    for i in range(low, high):
        if numbers[i] <= pivot:
            item = item + 1
            (numbers[item], numbers[i]) = (numbers[i], numbers[item])
    (numbers[item + 1], numbers[high]) = (numbers[high], numbers[item + 1])
    return item + 1

Đầu tiên, ta chọn phần tử chốt. Nó bằng số cao nhất trong list.

Tiếp theo, ta lặp qua tất cả mục trong list dùng vòng lặp for Python. Nếu số nhỏ hơn hoặc bằng chốt, nó được di chuyển sang trái chốt. Ngược lại, nó đi sang phải chốt.

Hàm Python trả về giá trị high mới. Giá trị high mới bằng item + 1.

Tiếp theo, ta chạy thuật toán. Ta làm bằng cách viết hàm riêng:

def quick_sort(numbers, low, high):
    if low < high:
        pivot = prepare(numbers, low, high)
        quick_sort(numbers, low, pivot - 1)
        quick_sort(numbers, pivot + 1, high)

Hàm kiểm tra xem giá trị "low" có nhỏ hơn "high" không. Nếu có, sắp xếp tiếp tục. Ngược lại, sắp xếp dừng. Nếu dừng, nghĩa là list đã sắp xếp.

Tiếp theo, hàm gọi phương thức prepare(). Điều này xác định con trỏ cho chốt và di chuyển mục đến vị trí đúng.

Hàm sau đó gọi quick_sort() hai lần. Lần đầu, chạy QuickSort trên phần tử bên trái chốt. Lần hai, chạy QuickSort trên phần tử bên phải chốt. Do đó, hàm là đệ quy vì tự gọi chính nó.

Điều này tiếp tục cho đến khi mọi mục trong list được sắp xếp.

Viết phương thức Main

Hãy viết chương trình chính định nghĩa list cần sắp xếp:

values = [8, 4, 5, 2, 1, 3]
total_values = len(values)
quick_sort(values, 0, total_values - 1)
print(values)

Đầu tiên, ta chỉ định list giá trị cần sắp xếp. Ta dùng len() Python tính độ dài list giá trị. Tiếp theo, ta gọi quick_sort().

Ta truyền "values" là số cần sắp xếp. Sau đó truyền 0 là số low. Độ dài "values" trừ 1 là giá trị high. Giá trị high là độ dài values trừ 1 vì mục đầu tiên trong list có chỉ số 0.

Thử chạy chương trình:

[1, 2, 3, 4, 5, 8]

Mã trả về list đã sắp xếp! Ta đã làm được. Thả ga cho bản thân. QuickSort không dễ hiểu hoặc triển khai.

Tổng quan độ phức tạp

Trung bình, thuật toán này hoạt động ở O(n* log n). Điều này xảy ra khi phần tử chốt không phải lớn nhất hoặc nhỏ nhất và không gần phần tử giữa.

QuickSort có độ phức tạp xấu nhất O(n²). Điều này xảy ra khi phần tử chọn làm chốt là lớn nhất hoặc nhỏ nhất. Nếu vậy, chốt luôn ở cuối mảng đã sắp xếp. Tạo ra số mảng con không cần thiết.

Độ phức tạp tốt nhất cho thuật toán này là O(n* log n). Xảy ra khi chốt bằng hoặc gần phần tử giữa.

Để tìm hiểu thêm về độ phức tạp thuật toán, xem hướng dẫn Ký hiệu Big O của chúng tôi.

Kết luận

Python QuickSort dùng đệ quy chia list thành list nhỏ hơn sau đó sắp xếp. Mỗi list được sắp xếp quanh phần tử chốt. Phần tử lớn hơn chốt di chuyển sang phải; phần tử nhỏ hơn di chuyển sang trái chốt.

Để có hướng dẫn tài nguyên học Python hàng đầu, khóa học trực tuyến, và sách, đọc hướng dẫn toàn diện "Cách học Python" của chúng tôi.