Làm cách nào để các ngôn ngữ khác nhau triển khai sắp xếp trong thư viện chuẩn của họ?

Question

Từ những gì tôi có (một thời gian ngắn), Java và Python đều giống như họ sử dụng timsort trong libaries tiêu chuẩn của họ, trong khi phương pháp sắp xếp trong stdlib của C được gọi là qsort vì nó đã từng là quicksort.

Thuật toán nào làm ngôn ngữ điển hình đã triển khai trong thư viện chuẩn của họ ngày nay và tại sao họ chọn thuật toán đó? Ngoài ra, C đã đi chệch khỏi quicksort?

Tôi biết câu hỏi này thiếu một "vấn đề thực tế mà tôi phải đối mặt" và có vẻ như đã kết thúc với một số người, nhưng biết cách thức/tại sao một số thuật toán được chọn làm tiêu chuẩn có vẻ khá hữu ích nhưng tương đối không được đáp ứng. Tôi cũng cảm thấy như là một câu trả lời sâu sắc giải quyết các mối quan tâm là ngôn ngữ cụ thể (kiểu dữ liệu?) Và máy cụ thể (bộ đếm cache?) Sẽ cung cấp thông tin chi tiết hơn về cách các ngôn ngữ và thuật toán khác nhau hoạt động hơn uni quan tâm.

Answer 1

thư viện C máy của tôi cung cấp qsort, heapsort, và mergesort, nói trong man page:

Các qsort() và qsort_r() chức năng là một thực hiện C.A.R. Thuật toán "quicksort" của Hoare, một biến thể của phân loại trao đổi phân vùng; đặc biệt, xem D.E. Thuật toán của Knuth Q. Quicksort mất O (n lg n) thời gian trung bình. Triển khai này sử dụng lựa chọn trung bình để tránh O (n) hành vi xấu nhất.

Chức năng heapsort() là triển khai thực hiện J.W.J. Thuật toán "heapsort" của William, một biến thể của phân loại lựa chọn; đặc biệt, xem D.E. Knuth's Thuật toán H. Heapsort mất O (n lg n) thời gian xấu nhất. Lợi thế duy nhất của nó trên qsort() là nó sử dụng hầu như không có bộ nhớ bổ sung; trong khi qsort() không cấp phát bộ nhớ, nó là được triển khai bằng cách sử dụng đệ quy.

Chức năng mergesort() đòi hỏi bộ nhớ bổ sung kích thước nel * width byte; nó chỉ nên được sử dụng khi không gian không phải là phí bảo hiểm. Chức năng mergesort() được tối ưu hóa cho dữ liệu có thứ tự đã có từ trước; thời gian xấu nhất của nó là O (n lg n); trường hợp tốt nhất là O (n).

Thông thường, qsort() nhanh hơn mergesort() đó là nhanh hơn so với heapsort(). Tính khả dụng của bộ nhớ và thứ tự có sẵn trong dữ liệu có thể làm cho điều này không đúng sự thật.

Có rất nhiều thư viện C nguồn mở để bạn xem liệu bạn có muốn xem chi tiết cụ thể về triển khai hay không.Theo như 'lý do tại sao hệ thống X chọn thuật toán Y', đó là một câu hỏi khá khó để trả lời một cách có ý nghĩa - nếu bạn không đủ may mắn tìm được lý do trong tài liệu, bạn sẽ phải trực tiếp hỏi trực tiếp nhà thiết kế .

Answer 2

Tôi đã quét nhanh tiêu chuẩn C11 về qsort() và tôi không thể tìm thấy bất kỳ tham chiếu nào về cách qsort() cần được triển khai và độ phức tạp về thời gian/không gian của thuật toán. Tất cả những gì cần nói là về một số điều kiện nhất định về hàm so sánh .

Điều đó có nghĩa là việc triển khai có thể chọn mọi thuật toán dựa trên so sánh phù hợp với qsort(). Ví dụ: triển khai có thể chọn sử dụng thuật toán ngây thơ như bubble sort để triển khai qsort() không hiệu quả như quick sort thực sự. Tóm lại là nó tối đa việc thực hiện để quyết định về thuật toán thực tế.

Answer 3

C không cụ thể hóa thuật toán sẽ được sử dụng bởi qsort.

Trên glibc hiện tại (2.17) qsort cấp phát bộ nhớ (sử dụng malloc hoặc alloca nếu yêu cầu bộ nhớ thực sự nhỏ) và sử dụng thuật toán sắp xếp hợp nhất. Nếu yêu cầu bộ nhớ quá cao hoặc nếu malloc không thành công thì sử dụng thuật toán quicksort.

Answer 4

Trong musl, chúng tôi sử dụng Smooth Sort. Về mặt khái niệm, nó là một biến thể của heap (và tương tự như vậy tại chỗ và O (n log n) thời gian), nhưng nó có đặc tính tốt đẹp mà hiệu suất trường hợp xấu nhất tiếp cận O (n) cho đầu vào đã sắp xếp hoặc sắp xếp gần. Tôi không tin nó là lựa chọn tốt nhất có thể, nhưng nó xuất hiện rất khó để làm tốt hơn với một thuật toán tại chỗ với trường hợp xấu nhất O (n log n).

Là một phát minh ít được biết đến của Dijkstra cũng khiến nó trở nên tuyệt vời. :-)