30
Duplicar posible:
which type of sorting is used in the function sort()?¿std :: sort implementa Quicksort?
¿Se std :: sort poner en práctica la ordenación rápida?
A
Respuesta
-3
Creo que sí. std :: list tiene un método de ordenación, o puede llamar sort del cual toma 2 iteradores, begin y end.
3
Depende de la implementación de la biblioteca. Las implementaciones de mergesort son las más comunes, ya que es el caso más desfavorable O (N * logN), mientras que el quicksort podría degradarse a O (N^2).
This lo confirma.
Además, que yo sepa, se utiliza algún tipo de heurística en la entrada para decidir qué algoritmo sería mejor usar internamente, por lo que varias llamadas a std::sort() podrían usar algoritmos diferentes.
+1
Podría ser la versión aleatorizada de quicksort, por lo que el argumento O (N^2) del peor caso no sería válido para este caso. – LunaticSoul
0
De Wikipedia -
El algoritmo de ordenación específica no es obligatoria y puede variar a través de implementaciones. Sort Wiki Link
+0
Si bien en este caso es probable que sea cierto, tendría mucho cuidado con lo que leo en Wikipedia. Cuando se trata de tener una referencia, cite el estándar en su lugar. – ereOn
0
Utiliza quicksort o introsort.
-3
debido a la alta complejidad de la peor clasificación rápida (N^2) y relativamente difícil de aplicar en la lista de enlaces. I thinkort no se hará usando el quicksort
+4
'std :: sort' no funciona en las listas de enlaces, por lo que no es un problema. –
32
Hay dos algoritmos que se usan tradicionalmente.
std::sort es más probable que utilice QuickSort, o al menos una variación sobre QuickSort llamados IntroSort, que "degenerados" a HeapSort cuando la recursividad va demasiado profundo.
de la norma:
Complejidad: comparaciones O (log N (N)).
std::stable_sort es más probable que use MergeSort, debido al requisito de estabilidad. Sin embargo, tenga en cuenta que MergeSort requiere espacio adicional para ser eficiente.
de la norma:
Complejidad: lo hace en la mayoría N log comparaciones (N); si hay suficiente memoria extra disponible, es N log (N).
todavía tengo que ver a un std::sort implementar TimSort que es prometedor y ha sido adoptado en Python (hecho a mano por ella, de hecho), Java y Android (hasta la fecha).
+0
@ maxim-yegorushkin: el artículo de Wikipedia también parece afirmar que introsort cambia a ordenación de inserción en lugar de heapsort:/ http://en.wikipedia.org/wiki/Sort_(C%2B%2B) "El estándar GNU C++ La biblioteca, por ejemplo, utiliza un algoritmo de ordenación híbrido: introsort se realiza primero, a una profundidad máxima dada por 2 × log2 n, donde n es el número de elementos, seguido de una clasificación de inserción en el resultado. " –
Cuestiones relacionadas
- 1. clasificación std :: listas usando std :: sort
- 2. boost zip_iterator y std :: sort
- 3. ¿Por qué el quicksort es más popular que radix-sort?
- 4. ¿Está std :: list <> :: sort stable?
- 5. Rendimiento de qsort vs std :: sort?
- 6. ¿Cómo se implementa std :: tuple?
- 7. Encadenamiento de predicados de ordenamiento (por ejemplo, para std :: sort)
- 8. ¿std :: sort cambia el orden relativo de elementos iguales?
- 9. ¿Cuán grande es la brecha de rendimiento entre std :: sort y std :: stable_sort en la práctica?
- 10. ¿Cuál es la diferencia práctica entre std :: nth_element y std :: sort?
- 11. implementación de quicksort
- 12. Quicksort pivote
- 13. C# merge sort performance
- 14. Aprendiendo LINQ: QuickSort
- 15. Algoritmo de partición QuickSort
- 16. Quicksort multiproceso o mergesort
- 17. Lazy Quicksort en Scala
- 18. Quicksort ordena números más grandes más rápido?
- 19. Sort lexicographically?
- 20. C++ lambdas para std :: sort y std :: LOWER_BOUND/equal_range en un elemento de estructura en un vector ordenado de estructuras
- 21. ¿Es esta una implementación correcta de quicksort?
- 22. Quicksort más lento que Mergesort?
- 23. ¿Qué es un Quicksort determinístico?
- 24. Comparación entre timsort y quicksort
- 25. Ordenando por el placer - Quicksort
- 26. C# quicksort funcional está fallando
- 27. Construcción de quicksort con php
- 28. ¿Debería std :: sort funcionar con la función lambda en C++ 0x/C++ 11?
- 29. ¿Por qué falla este predicado std :: sort cuando la clase está dentro de main()?
- 30. Cómo usar std :: sort con un vector de estructuras y función de comparación?
Wikipedia indica que el algoritmo específico no está especificado. – Sapph