Quicksort: vị trí trục xoay sau một phân vùng

Question

Tôi đang đọc về quicksort, xem xét các triển khai khác nhau và tôi đang cố gắng quấn đầu quanh một thứ gì đó.

Trong this thực hiện (trong đó công trình dĩ nhiên), trục được chọn làm yếu tố giữa và sau đó con trỏ di chuyển trái và phải để bên phải và trái cho phù hợp, trao đổi các yếu tố để phân vùng xung quanh trục.

Tôi đã thử mảng [4, 3, 2, 6, 8, 1, 0].

Trên phân hoạch đầu tiên, trục xoay là 6 và tất cả các phần tử bên trái đã nhỏ hơn 6, vì vậy con trỏ bên trái sẽ dừng tại trục xoay. Ở bên phải, chúng tôi sẽ hoán đổi 0 với 6, rồi 1 và 8, do đó, vào cuối lần lặp đầu tiên, mảng sẽ trông giống như:

[4, 3, 2, 0, 1, 8, 6].

Tuy nhiên, tôi đã có ấn tượng rằng sau mỗi lần lặp trong quicksort, trục kết thúc ở đúng vị trí của nó, vì vậy ở đây nó sẽ kết thúc ở vị trí 5 của mảng.

Vì vậy, có thể (và ok) rằng trục không kết thúc trong lặp lại chính xác của nó hoặc là nó một cái gì đó hiển nhiên tôi đang thiếu?

Answer 1

Có nhiều biến thể có thể có của thuật toán quicksort. Trong trường hợp này, trục xoay không được đặt đúng vị trí trong vòng lặp của nó. Tính năng xác định của mọi biến thể của thuật toán quicksort là sau bước phân vùng, chúng ta có một phần trong phần đầu của mảng, trong đó tất cả các phần tử nhỏ hơn hoặc bằng trục, và phần không chồng chéo trong cuối mảng nơi tất cả các phần tử lớn hơn hoặc bằng trục. Cũng có thể có một phần giữa chúng, trong đó mọi phần tử bằng pivot. Bố cục này đảm bảo rằng sau khi chúng tôi sắp xếp phần bên trái và phần bên phải với các cuộc gọi đệ quy, và để nguyên phần giữa, toàn bộ mảng sẽ được sắp xếp.

Lưu ý rằng, trong các yếu tố chung bằng trục có thể đi đến bất kỳ phần nào của mảng. Việc triển khai nhanh quicksort, tránh thời gian bậc hai cho trường hợp hiển nhiên nhất, tức là tất cả các phần tử bằng nhau, phải trải đều các phần tử bằng trục giữa các phần hợp lý.

biến thể có thể bao gồm:

• Phần giữa chỉ bao gồm 1 phần tử: đường trục. Trong trường hợp đó, trục xoay có vị trí cuối cùng trong mảng sau phân vùng và sẽ không được sử dụng trong các cuộc gọi đệ quy. Đó là những gì bạn có nghĩa là do trục xoay diễn ra trong vòng lặp của nó. Đối với phương pháp này, việc thực hiện tốt phải di chuyển khoảng một nửa các phần tử bằng trục xoay sang phần bên trái và nửa còn lại ở phần bên phải, nếu không chúng ta sẽ có thời gian bậc hai cho một mảng với tất cả các phần tử bằng nhau.
• Không có phần giữa. Pivot và tất cả các phần tử bằng với nó được lan truyền giữa phần bên trái và bên phải. Đó là những gì bạn thực hiện liên kết. Một lần nữa, trong phương pháp này khoảng một nửa các phần tử bằng trục nên đi đến phần bên trái, và nửa còn lại ở phần bên phải. Điều này cũng có thể được trộn lẫn với biến thể đầu tiên, tùy thuộc vào việc chúng ta sắp xếp một mảng với một số lẻ hay thậm chí là một số phần tử.
• Mọi phần tử bằng trục đi đến phần giữa. Không có yếu tố nào bằng trục xoay ở phần bên trái hoặc bên phải. Đó là khá hiệu quả và đó là ví dụ Wikipedia cho để giải quyết tất cả các yếu tố bằng nhau vấn đề. Mảng với tất cả các phần tử bằng nhau được sắp xếp theo thời gian tuyến tính trong trường hợp đó.

Do đó, việc triển khai nhanh và chính xác là khá phức tạp (cũng có vấn đề trong việc chọn một trục xoay tốt, một số cách tiếp cận với sự cân bằng khác nhau); thuật toán sắp xếp đệ quy cho các kích thước mảng nhỏ hơn).

Ngoài ra, có vẻ như việc thực hiện bạn có liên quan đến, có thể làm cuộc gọi đệ quy trên subarrays chồng chéo:

if (i <= j) { 
    exchange(i, j); 
    i++; 
    j--; 
} 

Ví dụ, khi i bằng j, những yếu tố này sẽ được hoán đổi, và i sẽ trở thành lớn hơn j bởi 2. Sau đó 3 yếu tố sẽ chồng chéo giữa các phạm vi của các cuộc gọi đệ quy sau đây. Mã này dường như vẫn hoạt động chính xác.