Quicksort - phần phụ nào cần được sắp xếp trước?

Question

Tôi đọc một số văn bản mà tuyên bố này liên quan đến việc đặt hàng của hai đệ quy Sắp xếp nhanh gọi:

... điều quan trọng là để gọi bài toán con nhỏ đầu tiên, điều này kết hợp với đuôi đệ quy đảm bảo rằng chồng sâu là nhật ký n.

Tôi không chắc chắn điều đó có nghĩa là gì, tại sao tôi nên gọi Quicksort trên mảng con nhỏ hơn trước?

Answer 1

Lý tưởng nhất, danh sách là phân vùng thành hai danh sách phụ có kích thước tương tự nhau. Nó không quan trọng nhiều mà danh sách phụ bạn làm việc trên đầu tiên.

Nhưng nếu vào một ngày tồi tệ, danh sách phân vùng theo cách lệch nhất có thể, danh sách con gồm hai hoặc ba mục, có thể là bốn và một danh sách con gần miễn là bản gốc. Điều này có thể là do sự lựa chọn không hợp lệ của giá trị phân vùng hoặc dữ liệu giả mạo không hợp lệ. Hãy tưởng tượng điều gì sẽ xảy ra nếu bạn làm việc trên danh sách con lớn hơn trước tiên. Lần gọi đầu tiên của Quicksort là giữ các con trỏ/chỉ mục cho danh sách ngắn trong khung ngăn xếp của nó trong khi đệ quy gọi quicksort cho danh sách dài. Điều này quá phân vùng xấu vào một danh sách rất ngắn và một dài, và chúng tôi làm danh sách con dài đầu tiên, lặp lại ...

Cuối cùng, vào ngày tồi tệ nhất của ngày xấu nhất với dữ liệu độc ác nhất, chúng tôi sẽ có ngăn xếp khung được xây dựng theo số tỷ lệ với độ dài danh sách ban đầu. Đây là hành vi trường hợp xấu nhất của quicksort, độ sâu O (n) của các cuộc gọi đệ quy. (Lưu ý chúng tôi đang nói về độ sâu đệ quy của quicksort, không phải hiệu suất.)

Làm danh sách con ngắn hơn trước hết sẽ nhanh chóng loại bỏ nó. Chúng tôi vẫn xử lý một số lượng lớn các danh sách nhỏ hơn, tương ứng với độ dài danh sách ban đầu, nhưng hiện tại, mỗi danh sách được xử lý bởi một hoặc hai cuộc gọi đệ quy. Chúng ta vẫn thực hiện các cuộc gọi O (n) (hiệu suất) nhưng mỗi chiều là O (1).

Answer 2

Một số ngôn ngữ có tính năng đệ quy đuôi. Điều này có nghĩa là nếu bạn viết f (x) {... ... .. ... .. g (x)} thì cuộc gọi cuối cùng, tới g (x), không được thực hiện với một cuộc gọi hàm nào cả , nhưng với một bước nhảy, để cuộc gọi cuối cùng không sử dụng bất kỳ không gian ngăn xếp nào.

Quicksort chia tách dữ liệu được sắp xếp thành hai phần. Nếu bạn luôn xử lý phần ngắn hơn trước, thì mỗi cuộc gọi tiêu thụ không gian ngăn xếp có một phần dữ liệu để sắp xếp tối đa bằng một nửa kích thước của cuộc gọi đệ quy gọi là nó. Vì vậy, nếu bạn bắt đầu với 10 yếu tố để sắp xếp, ngăn xếp ở mức sâu nhất sẽ có một cuộc gọi sắp xếp 10 yếu tố đó, sau đó sắp xếp một cuộc gọi ở tối đa 5 phần tử, sau đó gọi một phân loại tối đa 2 phần tử và sau đó sắp xếp cuộc gọi tối đa 1 phần tử - và sau đó, đối với 10 phần tử, ngăn xếp không thể đi sâu hơn - kích thước ngăn xếp bị giới hạn bởi nhật ký kích thước dữ liệu. Nếu bạn không lo lắng về điều này, bạn có thể kết thúc với ngăn xếp giữ một cuộc gọi sắp xếp 10 yếu tố, và sau đó một cuộc gọi sắp xếp 9 yếu tố, và sau đó một cuộc gọi sắp xếp 8 yếu tố, v.v. ngăn xếp được sâu như số lượng các yếu tố được sắp xếp. Nhưng điều này không thể xảy ra với đệ quy đuôi nếu bạn sắp xếp các đoạn ngắn trước, bởi vì mặc dù bạn có thể chia 10 phần tử thành 1 phần tử và 9 phần tử, cuộc gọi sắp xếp 9 phần tử được thực hiện cuối cùng và thực hiện như một bước nhảy t sử dụng bất kỳ không gian ngăn xếp nhiều hơn - nó tái sử dụng không gian ngăn xếp trước đó được sử dụng bởi người gọi của nó, mà chỉ là về để trở lại anyway.

Answer 3

Đáng ngạc nhiên, điều này hóa ra là quan trọng ngay cả khi quicksort không phải đối mặt với phân vùng hoang dã không cân bằng, và ngay cả khi introsort thực sự đang được sử dụng.

Sự cố phát sinh (trong C++) khi giá trị trong vùng chứa đang được sắp xếp thực sự lớn.Bằng cách này, tôi không có nghĩa là họ chỉ vào những vật thể thực sự to lớn, nhưng họ thực sự rất lớn. Trong trường hợp đó, một số (có thể nhiều) trình biên dịch sẽ làm cho khung stack đệ quy khá lớn, quá, bởi vì nó cần ít nhất một giá trị tạm thời để làm một trao đổi. Hoán đổi được gọi là bên trong phân vùng, mà không phải là đệ quy, vì vậy bạn sẽ nghĩ rằng trình điều khiển đệ quy quicksort sẽ không yêu cầu khung ngăn xếp quái vật; Thật không may, phân vùng thường kết thúc được inlined bởi vì nó đẹp và ngắn, và không được gọi từ bất cứ nơi nào khác.

Thông thường sự khác biệt giữa 20 và 40 khung ngăn xếp là không đáng kể, nhưng nếu giá trị cân nhắc tại, 8kb, thì sự khác biệt giữa 20 và 40 khung ngăn xếp có thể có nghĩa là sự khác biệt giữa công việc và ngăn xếp ngăn xếp, nếu ngăn xếp có được giảm kích thước để cho phép nhiều chủ đề.

Nếu bạn sử dụng thuật toán "luôn luôn chấp nhận vào phân vùng nhỏ hơn", ngăn xếp không được vượt quá các khung N, trong đó N là số phần tử trong vectơ. Hơn nữa, N không thể vượt quá số lượng bộ nhớ có sẵn chia cho kích thước của một phần tử. Vì vậy, trên một máy 32-bit, ở đó chỉ có thể là 2 yếu tố 8KB trong một véc tơ, và độ sâu gọi quicksort không thể vượt quá 19.

Nói tóm lại, viết quicksort làm một cách chính xác sử dụng stack của nó dự đoán (miễn là bạn có thể dự đoán kích thước của một khung ngăn xếp). Không làm phiền với việc tối ưu hóa (để lưu một so sánh đơn!) Có thể dễ dàng làm cho chiều sâu ngăn xếp tăng gấp đôi ngay cả trong trường hợp không bệnh, và trong trường hợp bệnh lý, nó có thể tồi tệ hơn nhiều.

Answer 4

Nhìn vào quicksort dưới dạng cây nhị phân ẩn. Trục xoay là gốc và các subtrees trái và phải là các phân vùng bạn tạo.

Bây giờ, hãy xem xét thực hiện tìm kiếm chiều sâu đầu tiên của cây này. Các cuộc gọi đệ quy thực sự tương ứng với thực hiện tìm kiếm chiều sâu đầu tiên trên cây ngầm được mô tả ở trên. Cũng giả sử rằng cây luôn luôn có cây con nhỏ hơn là con trái, do đó, gợi ý là trong thực tế để làm một đơn đặt hàng trước trên cây này.

Bây giờ giả sử bạn triển khai đặt hàng trước bằng cách sử dụng ngăn xếp, nơi bạn chỉ đẩy con bên trái (nhưng giữ cho cha mẹ trên ngăn xếp) và khi thời gian đến để đẩy đúng đứa trẻ (nói rằng bạn đã duy trì trạng thái một nút có con trái của nó khám phá hay không), bạn thay thế đầu stack, thay vì đẩy con phải (điều này tương ứng với phần đệ quy đuôi).

Độ sâu ngăn xếp tối đa là độ sâu tối đa 'tối đa': nghĩa là nếu bạn đánh dấu từng cạnh sẽ chuyển sang con trái là 1 và chuyển sang con phải là 0, thì bạn đang xem đường dẫn với tổng tối đa cạnh (về cơ bản bạn không tính các cạnh phải).

Vì cây con bên trái không có nhiều hơn một nửa các phần tử, mỗi khi bạn rẽ trái (tức là đi qua và cạnh được đánh dấu 1), bạn sẽ giảm số lượng nút còn lại để khám phá ít nhất một nửa.

Do đó, số cạnh tối đa được đánh dấu 1 mà bạn thấy, không lớn hơn log n.

Do đó, việc sử dụng ngăn xếp không nhiều hơn log n, nếu bạn luôn chọn phân vùng nhỏ hơn và sử dụng đệ quy đuôi.