Wenn ich ein Array mit der nativen Methode sort sortiere, welchen Algorithmus verwendet Ruby?Welchen Algorithmus verwendet die Sortiermethode von Ruby?
Ist es datenabhängig, d. H., Wenn die Daten klein sind, wird ein X-Algorithmus verwendet, sonst wird ein Y-Algorithmus verwendet?
Ist es eine stabile Sorte? Was ist die durchschnittliche Zeitkomplexität?
Schau mal hier: http://www.igvita.com/2009/03/26/ruby-algorithms-sorting-trie-heaps/
Es nativ quicksort jedoch zu verwenden ist, die im Durchschnitt log n Komplexität n.
Dies bedeutet auch, dass es wahrscheinlich keine stabile Sorte ist. Siehe die Erklärungen dazu unter http://en.wikipedia.org/wiki/Quick_sort –
Wahr, besonders wenn das Array fast sortiert ist, dann wird die Komplexität der schnellen Sortierung zu n^2. Trotzdem ist es in den meisten Fällen extrem schnell. – AlbertoPL
Wenn das Array fast sortiert ist, geht nur ein dummer Quicksort nach n^2. Median der drei Pivot-Auswahl ist in allen Implementierungen, die ich verwendet habe –
Die Stabilität von Rubys Sortierung wird in [dieser Frage] angesprochen (https://stackoverflow.com/questions/15442298/is-sort-in-ruby-stable). –