30
Powiel możliwe:
which type of sorting is used in the function sort()?Czy std :: sort implementuje Quicksort?
Czy std :: sort wdrożyć quicksort?
A
Odpowiedz
-3
Myślę, że tak. std :: list ma metodę sortowania lub możesz wywołać sortowanie, z którego pobiera 2 iteratory, zaczynając i kończąc.
3
To zależy od implementacji biblioteki. Wdrożenia mergesort są najczęstsze, ponieważ jest najgorszy przypadek O (N * logN), podczas gdy quicksort może pogorszyć się do O (N^2).
This potwierdza to.
Ponadto, o ile mi wiadomo, na wejściu używany jest pewien rodzaj heurystyki, aby zdecydować, który algorytm będzie najlepszy do użytku wewnętrznego, aby różne połączenia z std::sort() mogły korzystać z różnych algorytmów.
+1
Może to być losowa wersja quicksort, więc argument O najgorszego przypadku O (N^2) nie byłby dla tego przypadku. – LunaticSoul
0
Z Wikipedii -
Konkretny algorytm sortowania nie jest upoważniony i może zmieniać się w poprzek wdrożeń. Sort Wiki Link
+0
Chociaż w tym przypadku jest to prawdopodobnie prawda, byłbym bardzo ostrożny w tym, co przeczytałem na Wikipedii. Jeśli chodzi o referencję, powołuj się na standard. – ereOn
0
Używa quicksort lub introsort.
-3
powodu wysokiej najgorszym złożoności quicksort (N^2), a także stosunkowo trudny do wykonania, na linklist. Myślę, że nie zostanie to zrobione przy użyciu quicksorta
+4
'std :: sort' nie działa na listach połączonych, więc nie jest problemem. –
32
Istnieją dwa algorytmy, które są tradycyjnie używane.
std::sort najprawdopodobniej używać QuickSort, a przynajmniej wariacja na Quicksort nazywa IntroSort, które „degeneratów” do HeapSort gdy rekurencji jest zbyt głęboka.
od standardu:
Złożoność: O (log N (n)) porównania.
std::stable_sort najczęściej używa MergeSort, ze względu na wymaganie stabilności. Należy jednak pamiętać, że MergeSort wymaga dodatkowej przestrzeni, aby być wydajnym.
od standardu:
Złożoność: To jest co najwyżej N log (N) porównań; jeśli dostępna jest wystarczająca ilość dodatkowej pamięci, jest to N log (N).
muszę jeszcze zobaczyć std::sort realizacji TimSort który jest obiecujący i został przyjęty w Pythonie (spreparowany przez nią w rzeczywistości), Java i Android (do tej pory).
+0
@ maxim-yegorushkin: Artykuł w Wikipedii również wydaje się twierdzić, że introsort przełącza się na sortowanie wstawek zamiast heapsortu:/ http://en.wikipedia.org/wiki/Sort_(C%2B%2B) "Standard GNU C++ na przykład biblioteka wykorzystuje hybrydowy algorytm sortowania: introsort jest wykonywany jako pierwszy, do maksymalnej głębokości podanej przez 2 × log2 n, gdzie n jest liczbą elementów, po którym następuje sortowanie wstawiania na wynik. " –
Powiązane problemy
- 1. sortowania std :: list przy użyciu std :: sort
- 2. std :: sort nie zawsze zadzwonić std :: Swap
- 3. Jaka jest złożoność pamięci std :: sort() i std :: sort_heap()?
- 4. Łańcuchy predykatów porządkowania (np. Dla std :: sort)
- 5. Jaka jest praktyczna różnica między std :: nth_element a std :: sort?
- 6. Przestrzeń nazw "std" nie ma członka "sort"
- 7. std :: sort() na wektorze klasy wskaźników
- 8. C++ funkcja zwyczaj porównać do std :: sort()
- 9. error: 'sort' nie jest członkiem 'std'
- 10. Jawny konstruktor kopiowania i std :: sort
- 11. Lokalny QuickSort w Pythonie
- 12. Jaką magię używa `std :: sort` wewnętrznie, co sprawia, że jest o wiele szybsza?
- 13. zamieszanie na temat korzystania z std :: mniejsze i większe z std :: std :: sort
- 14. Czy to jest poprawna implementacja quicksort?
- 15. randomizowane Quicksort
- 16. Java: Arrays.sort quicksort i mergesort
- 17. Czy myBatis implementuje JPA?
- 18. Dlaczego nie std :: sort używać mojego operatora <realizacji
- 19. qsort() vs std :: sort, różnica funkcji filozoficzna różnica
- 20. Sprawdź, czy obiekt implementuje interfejs
- 21. Sprawdź, czy obiekt implementuje interfejs
- 22. Sprawdź, czy system implementuje funkcję
- 23. Jak duża jest różnica w wydajności między std :: sort i std :: stable_sort w praktyce?
- 24. Jak sortować std :: vector, ale nie zmieniaj konkretnych elementów używając std :: sort?
- 25. QuickSort stabilność algorytm
- 26. Ogólny quicksort w Scala
- 27. Porównanie timsort i quicksort
- 28. Czy std :: sort działa z funkcją lambda w C++ 0x/C++ 11?
- 29. Quicksort w F # - składnia zapytania
- 30. Quicksort - powodem jest równa weryfikacje
Wikipedia wskazuje, że określony algorytm nie został określony. – Sapph