Sắp xếp nhanh chóng ( Quicksort)

Sắp xếp nhanh (tiếng Anh: Quicksort), còn được gọi là sắp xếp trao đổi phân vùng (phân vùng trao đổi), chia dữ liệu được sắp xếp thành hai phần độc lập thông qua một cách sắp xếp, tất cả dữ liệu ở một phần nhỏ hơn tất cả dữ liệu ở phần kia Và sau đó theo phương pháp này để nhanh chóng sắp xếp hai phần của dữ liệu, toàn bộ quá trình sắp xếp có thể đệ quy, để đạt được toàn bộ dữ liệu thành một chuỗi có thứ tự.

Các bước là:

1. Chọn một phần tử từ trình tự và gọi nó là "pivot",

2. Sắp xếp lại trình tự, tất cả các phần tử nhỏ hơn giá trị điểm chuẩn được đặt ở phía trước điểm chuẩn và tất cả các phần tử lớn hơn giá trị điểm chuẩn được đặt phía sau điểm chuẩn (cùng một số có thể nằm ở hai bên). Sau khi phân vùng kết thúc, điểm chuẩn nằm ở giữa chuỗi. Đây được gọi là hoạt động phân vùng.

3. Sắp xếp đệ quy các dãy con của phần tử nhỏ hơn giá trị tham chiếu và dãy con của các phần tử lớn hơn giá trị tham chiếu.

Trường hợp cuối cùng của đệ quy là kích thước của dãy bằng 0 hoặc bằng một, nghĩa là nó luôn được sắp xếp. Mặc dù nó đã được đệ quy, nhưng thuật toán này sẽ luôn kết thúc, bởi vì trong mỗi lần lặp, nó sẽ đặt ít nhất một phần tử đến vị trí cuối cùng của nó.

Phân tích nhanh chóng

def quick_sort(alist, start, end):

    if start >= end:
        return

    mid = alist[start]

    low = start

    high = end

    while low < high:
        while low < high and alist[high] >= mid:
            high -= 1
        alist[low] = alist[high]

        while low < high and alist[low] < mid:
            low += 1
        alist[high] = alist[low]

    alist[low] = mid

    quick_sort(alist, start, low-1)

    quick_sort(alist, low+1, end)


alist = [54,26,93,17,77,31,44,55,20]
quick_sort(alist,0,len(alist)-1)
print(alist)

thời gian phức tạp

• Độ phức tạp thời gian tối ưu: O (nlogn)

• Độ phức tạp thời gian tồi tệ nhất: O (n 2 )

• Ổn định: không ổn định

Không rõ ràng ngay từ đầu rằng quicksort mất trung bình O (n log n) thời gian. Nhưng không khó để nhận thấy rằng thao tác phân vùng, các phần tử của mảng sẽ được truy cập một lần trong mỗi vòng lặp, sử dụng thời gian O (n). Trong phiên bản sử dụng phép nối, phép toán này cũng là O (n).

Trong trường hợp tốt nhất, mỗi khi chúng ta chạy một phân vùng, chúng ta sẽ chia một chuỗi thành hai đoạn gần bằng nhau. Điều này có nghĩa là mỗi cuộc gọi đệ quy xử lý một nửa kích thước của chuỗi. Do đó, chúng ta chỉ cần thực hiện log n lệnh gọi lồng nhau trước khi đạt đến chuỗi kích thước một. Điều này có nghĩa là độ sâu của cây gọi là O (log n). Tuy nhiên, trong hai lệnh gọi chương trình có cùng cấu trúc phân cấp, phần giống nhau của trình tự ban đầu sẽ không được xử lý; do đó, mỗi cấu trúc phân cấp của lệnh gọi chương trình chỉ cần O (n) thời gian (mỗi lệnh gọi có một số điểm chung Thêm chi phí, nhưng vì chỉ có O (n) lệnh gọi trong mỗi hệ thống phân cấp, chúng được tóm tắt trong hệ số O (n)). Kết quả là thuật toán này chỉ cần O (n log n) thời gian.

Bản demo sắp xếp nhanh

sắp xếp nhanh chóng