Sắp xếp nhanh DSA

Sắp xếp nhanh chóng

Đúng như tên gọi, Quicksort là một trong những thuật toán sắp xếp nhanh nhất.

Thuật toán Quicksort lấy một mảng các giá trị, chọn một trong các giá trị làm phần tử 'trục' và di chuyển các giá trị khác sao cho các giá trị thấp hơn nằm ở bên trái của phần tử trục và các giá trị cao hơn nằm ở bên phải của phần tử đó.

Trong hướng dẫn này, phần tử cuối cùng của mảng được chọn làm phần tử trụ, nhưng chúng ta cũng có thể chọn phần tử đầu tiên của mảng hoặc bất kỳ phần tử nào trong mảng.

Sau đó, thuật toán Quicksort thực hiện thao tác đệ quy tương tự trên các mảng con ở bên trái và bên phải của phần tử trụ. Điều này tiếp tục cho đến khi mảng được sắp xếp.

Thuật toán có thể được mô tả như thế này:

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

Chạy qua thủ công

Trước khi triển khai thuật toán Quicksort bằng 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 để tìm ý 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 chọn giá trị cuối cùng là 3 làm phần tử trụ.

Bước 3: Các giá trị còn lại trong mảng đều nhỏ hơn 3, an phải ở bên phải của 3. Đổi chỗ 3 bằng 11.

Bước 4: Giá trị 3 hiện ở đúng vị trí. Chúng ta cần sắp xếp các giá trị ở bên phải của 3. Chúng ta chọn giá trị cuối cùng 11 làm phần tử trục mới.

Bước 5: Giá trị 7 phải ở bên trái giá trị trục 11 và 12 phải ở bên phải giá trị trục đó. Di chuyển 7 và 12.

Bước 6: Hoán đổi 11 với 12 sao cho các giá trị thấp hơn 9 và 7 ở bên trái của 11 và 12 ở bên phải.

Bước 7: 11 và 12 vào đúng vị trí. Chúng tôi chọn 7 làm phần tử trụ trong mảng con [ 9, 7], ở bên trái 11.

Bước 8: Chúng ta phải hoán đổi 9 bằng 7.

Và bây giờ, 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?

Trước khi triển khai thuật toán bằng ngôn ngữ lập trình, chúng ta cần xem xét chi tiết hơn những gì đã xảy ra ở trên.

Chúng ta đã thấy rằng giá trị cuối cùng của mảng được chọn làm phần tử trụ và các giá trị còn lại được sắp xếp sao cho các giá trị thấp hơn giá trị trục nằm ở bên trái và các giá trị cao hơn ở bên phải.

Sau đó, phần tử trụ được hoán đổi với phần tử đầu tiên có giá trị cao hơn. Điều này chia mảng ban đầu thành hai, với phần tử trục ở giữa giá trị thấp hơn và giá trị cao hơn.

Bây giờ chúng ta cần thực hiện tương tự như trên với các mảng con ở bên trái và bên phải của phần tử trục cũ. Và nếu một mảng con có độ dài 0 hoặc 1, chúng tôi coi như nó đã được sắp xếp xong.

Tóm lại, thuật toán Quicksort làm cho các mảng con ngày càng ngắn hơn cho đến khi mảng được sắp xếp.

Triển khai Quicksort

Để viết phương thức 'quickSort' chia mảng thành các mảng con ngày càng ngắn hơn, chúng ta sử dụng đệ quy. Điều này có nghĩa là phương thức 'quickSort' phải tự gọi chính nó với các mảng con mới ở bên trái và bên phải của phần tử trụ. Đọc thêm về đệ quy ở đây .

Để triển khai thuật toán Quicksort bằng 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. Phương thức quickSort tự gọi chính nó (đệ quy) nếu mảng con có kích thước lớn hơn 1.
3. Một phương thức phân vùng nhận một mảng con, di chuyển các giá trị xung quanh, hoán đổi phần tử trục vào mảng con và trả về chỉ mục nơi xảy ra sự phân chia tiếp theo trong các mảng con.

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

 def partition(array, low, high):
    pivot = array[high]
    i = low - 1

    for j in range(low, high):
        if array[j] <= pivot:
            i += 1
            array[i], array[j] = array[j], array[i]

    array[i+1], array[high] = array[high], array[i+1]
    return i+1

def quicksort(array, low=0, high=None):
    if high is None:
        high = len(array) - 1

    if low < high:
        pivot_index = partition(array, low, high)
        quicksort(array, low, pivot_index-1)
        quicksort(array, pivot_index+1, high)

my_array = [64, 34, 25, 12, 22, 11, 90, 5]
quicksort(my_array)
print("Sorted array:", my_array)

Độ phức tạp của thời gian Quicksort

Để 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 của thời gian Quicksort, hãy truy cập trang này .

Trường hợp xấu nhất đối với Quicksort là \(O(n^2) \). Đây là khi phần tử trục có giá trị cao nhất hoặc thấp nhất trong mỗi mảng con, dẫn đến nhiều lệnh gọi đệ quy. Với cách triển khai ở trên của chúng tôi, điều này xảy ra khi mảng đã được sắp xếp.

Nhưng trung bình, độ phức tạp về thời gian của Quicksort thực ra chỉ là \(O(n \log n) \), tốt hơn rất nhiều so với các thuật toán sắp xếp trước đây mà chúng ta đã xem xét. Đó là lý do tại sao Quicksort rất phổ biến.

Dưới đây, bạn có thể thấy sự cải thiện đáng kể về độ phức tạp về thời gian của Quicksort trong kịch bản trung bình \(O(n \log n) \), so với các thuật toán sắp xếp trước đó Sắp xếp bong bóng, lựa chọn và chèn với độ phức tạp thời gian \(O(n^2) ) \):

Phần đệ quy của thuật toán Quicksort thực sự là lý do tại sao kịch bản sắp xếp trung bình lại nhanh như vậy, bởi vì để chọn tốt phần tử trục, mảng sẽ được chia đôi một cách đồng đều mỗi khi thuật toán gọi chính nó. Vì vậy số lượng lệnh gọi đệ quy không tăng gấp đôi, ngay cả khi số lượng giá trị \(n \) tăng gấp đôi.

Chạy Quicksort trên các loại mảng khác nhau với số lượng giá trị khác nhau trong mô phỏng bên dưới:

phân vùng def (mảng, thấp, cao):
    trục = mảng [cao]
    tôi = thấp - 1

    cho j trong phạm vi (thấp, cao):
        nếu mảng[j] <= trục:
            tôi += 1
            mảng[i], mảng[j] = mảng[j], mảng[i]

    mảng[i+1], mảng[cao] = mảng[cao], mảng[i+1]
    trả về i+1

def quicksort(array, low=0, high=None):
    nếu cao là Không có:
        cao = len(mảng) - 1

    nếu thấp < cao:
        Pivot_index = phân vùng (mảng, thấp, cao)
        (mảng, thấp, Pivot_index-1)
        (mảng, Pivot_index+1, cao)

my_array = [64, 34, 25, 12, 22, 11, 90, 5]
sắp xếp nhanh (my_array)
print("Sắp xếp mảng:", my_array)