Quan sát hành vi bậc hai với quicksort - O (n^2)

Question

Thuật toán quicksort có độ phức tạp trung bình của O (n * log (n)) và độ phức tạp trường hợp xấu nhất của O (n^2).

Giả sử một số biến thể của thuật toán quicksort của Hoare, loại đầu vào nào sẽ khiến thuật toán quicksort thể hiện sự phức tạp của trường hợp xấu nhất?

Vui lòng nêu rõ bất kỳ giả định nào liên quan đến các chi tiết triển khai liên quan đến thuật toán quicksort cụ thể như lựa chọn trục xoay, v.v ... hoặc nếu nó có nguồn gốc từ thư viện thường có sẵn như libc.

Một số đọc:

1. A Killer Adversary for Quicksort
2. Quicksort Is Optimal
3. Engineering a Sort Function
4. Introspective Sorting and Selection Algorithms

Answer 1

Các Quick sort Thực hiện tồi tệ nhất ví dụ, tại O (n^2) khi tất cả các giá trị của trục được chọn là lớn nhất hoặc nhỏ nhất của t bộ aken. Hãy xem xét ví dụ này.

Trục chọn nói là 1, bạn sẽ có 4 yếu tố trên bên phải của trục và không có yếu tố ở phía bên trái. Áp dụng cùng một logic đệ quy và trục được chọn tương ứng là 2, 3, 4, 5, chúng tôi đã đạt được một tình huống mà loại này đã thực hiện vào thời điểm tồi tệ nhất có thể.

Đã được đề xuất và chứng minh rằng Quicksort hoạt động tốt nếu đầu vào được xáo trộn tốt.

Hơn nữa, việc lựa chọn sắp xếp thường phụ thuộc vào kiến ​​thức rõ ràng về miền nhập. Ví dụ, nếu đầu vào là rất lớn, sau đó có một cái gì đó gọi là loại bên ngoài có thể sử dụng bộ nhớ ngoài. Nếu kích thước đầu vào là rất nhỏ, chúng tôi có thể đi cho một loại hợp nhất nhưng không cho bộ đầu vào vừa và lớn vì nó sử dụng thêm bộ nhớ. Ưu điểm chính của Sắp xếp nhanh là ý nghĩa "tại chỗ" của nó, không có thêm bộ nhớ nào đang được sử dụng cho dữ liệu đầu vào. Thời gian trường hợp xấu nhất trên giấy là O (n^2) nhưng vẫn được ưa chuộng và sử dụng rộng rãi. Quan điểm của tôi ở đây là, các thuật toán sắp xếp có thể được thay đổi dựa trên kiến ​​thức về tập hợp đầu vào và vấn đề ưu tiên của nó.

Answer 2

Để mở rộng về những gì Bragboy nói, thay vì chỉ chạy:

quicksort(array); 

Run:

shuffle(array); 
quicksort(array); 

Trong trường hợp định nghĩa của shuffle() có thể là:

shuffle(array){ 
    for(int i = array.length; i > 0; i--){ 
     r= random number % i; 
     swap(array[i], array[r]); 
    } 
} 

Làm như vậy sẽ , có khả năng, đối phó với trường hợp nhận được đầu vào mà làm cho quicksort() chậm.

Answer 3

Thuật toán Quicksort của Hoare chọn một trục xoay ngẫu nhiên. Đối với kết quả có thể tái sản xuất, tôi đề nghị sửa đổi của Scowen, trong số những thứ khác, chọn mục giữa từ đầu vào.Đối với biến thể này, mô hình răng cưa với trục nhỏ nhất có vẻ là trường hợp xấu nhất:

starting with   { j i h g f a e d c b } 
compare 1 to 6   { (j) i h g f (a) e d c b } 
compare 6 to 10   { j i h g f (a) e d c (b) } 
compare 6 to 9   { j i h g f (a) e d (c) b } 
compare 6 to 8   { j i h g f (a) e (d) c b } 
compare 6 to 7   { j i h g f (a) (e) d c b } 
swap 1<=>6    { (a) i h g f (j) e d c b } 
compare 1 to 5   { (a) i h g (f) j e d c b } 
compare 1 to 4   { (a) i h (g) f j e d c b } 
compare 1 to 3   { (a) i (h) g f j e d c b } 
compare 1 to 2   { (a) (i) h g f j e d c b } 
compare 2 to 6   { a (i) h g f (j) e d c b } 
compare 3 to 6   { a i (h) g f (j) e d c b } 
compare 4 to 6   { a i h (g) f (j) e d c b } 
compare 5 to 6   { a i h g (f) (j) e d c b } 
compare and swap 6<=>10 { a i h g f (b) e d c (j) } 
compare 7 to 10   { a i h g f b (e) d c (j) } 
compare 8 to 10   { a i h g f b e (d) c (j) } 
compare 9 to 10   { a i h g f b e d (c) (j) } 
compare 2 to 6   { a (i) h g f (b) e d c j } 
compare 6 to 9   { a i h g f (b) e d (c) j } 
compare 6 to 8   { a i h g f (b) e (d) c j } 
compare 6 to 7   { a i h g f (b) (e) d c j } 
swap 2<=>6    { a (b) h g f (i) e d c j } 
compare 2 to 5   { a (b) h g (f) i e d c j } 
compare 2 to 4   { a (b) h (g) f i e d c j } 
compare 2 to 3   { a (b) (h) g f i e d c j } 
compare 3 to 6   { a b (h) g f (i) e d c j } 
compare 4 to 6   { a b h (g) f (i) e d c j } 
compare 5 to 6   { a b h g (f) (i) e d c j } 
compare and swap 6<=>9 { a b h g f (c) e d (i) j } 
compare 7 to 9   { a b h g f c (e) d (i) j } 
compare 8 to 9   { a b h g f c e (d) (i) j } 
compare 3 to 6   { a b (h) g f (c) e d i j } 
compare 6 to 8   { a b h g f (c) e (d) i j } 
compare 6 to 7   { a b h g f (c) (e) d i j } 
swap 3<=>6    { a b (c) g f (h) e d i j } 
compare 3 to 5   { a b (c) g (f) h e d i j } 
compare 3 to 4   { a b (c) (g) f h e d i j } 
compare 4 to 6   { a b c (g) f (h) e d i j } 
compare 5 to 6   { a b c g (f) (h) e d i j } 
compare and swap 6<=>8 { a b c g f (d) e (h) i j } 
compare 7 to 8   { a b c g f d (e) (h) i j } 
compare 4 to 6   { a b c (g) f (d) e h i j } 
compare 6 to 7   { a b c g f (d) (e) h i j } 
swap 4<=>6    { a b c (d) f (g) e h i j } 
compare 4 to 5   { a b c (d) (f) g e h i j } 
compare 5 to 6   { a b c d (f) (g) e h i j } 
compare and swap 6<=>7 { a b c d f (e) (g) h i j } 
compare and swap 5<=>6 { a b c d (e) (f) g h i j }