Quicksort bắt buộc tại chỗ (tại chỗ) hay không?

Question

Quicksort thường được mô tả là thuật toán tại chỗ (tại chỗ), mặc dù thực tế là nó yêu cầu không gian ngăn xếp O (log n). Vì vậy, tại chỗ có nghĩa là "yêu cầu ít hơn O (n) không gian bổ sung", hoặc không gian ngăn xếp thường không được tính là độ phức tạp của không gian (nhưng tại sao lại như vậy?), Hoặc là Quicksort thực sự không phải là tại chỗ thuật toán?

Answer 1

là Quicksort thực sự không phải là thuật toán tại chỗ?

Việc thực hiện tiêu chuẩn của nó là khôngtại chỗ. Đó là một quan niệm sai lầm phổ biến khủng khiếp, nhưng bạn là một lưu ý chính xác do tiêu thụ không gian ngăn xếp, mà quan niệm là sai.

Tôi nói "triển khai chuẩn" của nó vì mọi người đã sửa đổi thuật toán để biến nó thành thuật toán O(1) -space. Dưới đây là một ví dụ: Quicksort without a stack.

Tất nhiên, phù hợp với kiểu cổ điển space-time tradeoff, các phiên bản nhanh như vậy ít hoạt động hơn so với triển khai chuẩn.

Answer 2

Wikipedia cung cấp sau definition:

Trong khoa học máy tính, một thuật toán tại chỗ (hoặc trong Latin tại chỗ) là một thuật toán mà biến đổi đầu vào sử dụng một cấu trúc dữ liệu với một lượng nhỏ, liên tục không gian lưu trữ bổ sung.

Theo định nghĩa này, quicksort dựa trên stack điển hình rõ ràng không phải là thuật toán tại chỗ.

Trong thực tế, các bài viết Wikipedia một cách rõ ràng thảo luận này:

Một thuật toán được đôi khi không chính thức gọi là tại chỗ miễn là nó ghi đè đầu vào của nó với sản lượng của nó. Trong thực tế điều này là không đủ (như trường hợp của quicksort chứng minh) cũng không phải là cần thiết; không gian đầu ra có thể không đổi, hoặc thậm chí có thể không được tính, ví dụ nếu đầu ra là một luồng.

và

Sắp xếp nhanh thường được mô tả như một thuật toán tại chỗ, nhưng không phải là trong thực tế một. Hầu hết các triển khai yêu cầu không gian O (log n) để hỗ trợ phân chia và chinh phục đệ quy của nó.

Tuy nhiên, như được chỉ ra bởi @ Jason trong câu trả lời tuyệt vời của mình, dường như tồn tại các biến thể của quicksort chỉ yêu cầu không gian thêm (1). Bất kỳ alorithms như vậy sẽ được coi là tại chỗ.