×

Cài đặt thuật toán Quick Sort trong lập trình

Avatar of admin
admin 2 Views

Thuật toán sắp xếp nhanh, hay còn gọi là Quick Sort, là một trong những thuật toán sắp xếp hiệu quả và phổ biến nhất trong lĩnh vực lập trình. Phương pháp này sử dụng chiến lược "chia để trị" (divide-and-conquer) để chia nhỏ vấn đề thành các phần nhỏ hơn và giải quyết chúng một cách đệ quy.

Nguyên lý hoạt động của Quick Sort

Thuật toán Quick Sort hoạt động dựa trên các bước cơ bản sau đây:

  1. Chọn phần tử chốt (pivot): Một phần tử trong mảng được chọn làm chốt. Phần tử này có thể được chọn ngẫu nhiên, hoặc theo một số phương pháp như chọn phần tử ở giữa mảng.

  2. Phân hoạch mảng (partitioning): Mảng được chia thành hai phần sao cho tất cả các phần tử nhỏ hơn chốt nằm ở bên trái chốt, và tất cả các phần tử lớn hơn chốt nằm ở bên phải chốt.

  3. Đệ quy: Quick Sort được áp dụng đệ quy lên hai mảng con, mảng bên trái và mảng bên phải, cho đến khi toàn bộ mảng được sắp xếp.

Cài đặt thuật toán Quick Sort

Dưới đây là cài đặt thuật toán Quick Sort bằng ngôn ngữ lập trình Python:

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[len(arr) // 2]
        left = [x for x in arr if x < pivot]
        middle = [x for x in arr if x == pivot]
        right = [x for x in arr if x > pivot]
        return quicksort(left) + middle + quicksort(right)

# Ví dụ sử dụng
arr = [3, 6, 8, 10, 1, 2, 1]
print("Mảng gốc:", arr)
sorted_arr = quicksort(arr)
print("Mảng đã sắp xếp:", sorted_arr)

Trong cài đặt trên:

  • Chốt được chọn là phần tử ở giữa mảng.
  • Phân hoạch mảng thành ba phần: các phần tử nhỏ hơn chốt, bằng chốt và lớn hơn chốt.
  • Đệ quy gọi chức năng Quick Sort đến khi các mảng con chỉ còn một phần tử hoặc không có phần tử nào.

Tối ưu hóa Quick Sort

Có một số cách để tối ưu hóa thuật toán Quick Sort nhằm tăng hiệu suất:

  1. Chọn chốt thông minh: Thay vì chọn chốt ngẫu nhiên hoặc cố định, chọn chốt theo một số phương pháp như "Median of Three" (trung vị của ba số), giúp giảm thiểu khả năng rơi vào trường hợp xấu nhất.

  2. Sử dụng phân hoạch Hoare's partitioning scheme: Phân hoạch của Hoare thường nhanh hơn phân hoạch của Lomuto vì thực hiện ít phép so sánh hơn.

  3. Giảm độ sâu của đệ quy: Khi mảng con nhỏ hơn một kích thước nào đó (ví dụ: 10 phần tử), sử dụng một thuật toán sắp xếp khác như sắp xếp chèn (Insertion Sort) để tăng hiệu suất.

Áp dụng Hoare's Partitioning Scheme trong Quick Sort

Dưới đây là một ví dụ sử dụng phương pháp phân hoạch Hoare trong Quick Sort:

def hoare_partition(arr, low, high):
    pivot = arr[low]
    left = low - 1
    right = high + 1

    while True:
        left += 1
        while arr[left] < pivot:
            left += 1

        right -= 1
        while arr[right] > pivot:
            right -= 1

        if left >= right:
            return right

        arr[left], arr[right] = arr[right], arr[left]

def quicksort(arr, low, high):
    if low < high:
        pivot_index = hoare_partition(arr, low, high)
        quicksort(arr, low, pivot_index)
        quicksort(arr, pivot_index + 1, high)

# Ví dụ sử dụng
arr = [3, 6, 8, 10, 1, 2, 1]
print("Mảng gốc:", arr)
quicksort(arr, 0, len(arr) - 1)
print("Mảng đã sắp xếp:", arr)

Thuật toán sắp xếp nhanh được đánh giá là một trong những phương pháp sắp xếp tốt nhất trong nhiều trường hợp, nhờ vào tốc độ và sự linh hoạt trong việc xử lý các phần tử của mảng. Khi đã hiểu rõ nguyên lý hoạt động và cách cài đặt, bạn có thể dễ dàng áp dụng nó trong các dự án lập trình.

Comments

Bài viết liên quan