Khi tôi sắp xếp một mảng bằng cách sử dụng phương thức sort gốc, thuật toán nào Ruby sử dụng?Thuật toán sắp xếp của Ruby sử dụng thuật toán nào?
Có phụ thuộc vào dữ liệu hay không, tức là nếu dữ liệu nhỏ, nó sử dụng thuật toán X khác thì nó sử dụng thuật toán Y?
Đây có phải là loại ổn định không? Độ phức tạp trung bình của thời gian là bao nhiêu?
Nhìn đây: http://www.igvita.com/2009/03/26/ruby-algorithms-sorting-trie-heaps/
Nó natively sử dụng quicksort tuy nhiên, đó là n log n phức tạp trên trung bình.
Điều này cũng có nghĩa là nó rất có thể không phải là một loại ổn định. Xem giải thích về điều này tại http://en.wikipedia.org/wiki/Quick_sort –
Đúng, đặc biệt nếu mảng gần như được sắp xếp, thì độ phức tạp của sắp xếp nhanh trở thành n^2. Tuy nhiên, nó rất nhanh trong hầu hết các trường hợp. – AlbertoPL
Nếu mảng gần như sắp xếp, chỉ có một quicksort ngu ngốc đi đến n^2. Trung bình của ba lựa chọn trục là trong tất cả các triển khai tôi đã sử dụng –
Tính ổn định của sắp xếp của Ruby được giải quyết trong [câu hỏi này] (https://stackoverflow.com/questions/15442298/is-sort-in-ruby-stable). –