Tema 2
Métodos de ordenamiento
Patrón de examen
En competencia siempre usa std::sort. Implementa merge sort solo si necesitas contar inversiones u operaciones durante el merge.
Explicación
Algoritmos de ordenamiento
| Algoritmo | Complejidad | Estable | Uso |
|---|---|---|---|
| Burbuja | O(n²) | Sí | Solo para entender conceptos |
| Selección | O(n²) | No | Solo para entender conceptos |
| Inserción | O(n²) | Sí | Bueno para n pequeño o casi ordenado |
| Merge Sort | O(n log n) | Sí | Cuando se necesita estabilidad |
| Quick Sort | O(n log n) avg | No | Rápido en práctica |
| std::sort | O(n log n) | No | Usar siempre en competencia |
Regla en olimpiadas: usa std::sort
Nunca implementes tu propio sort en competencia. std::sort es optimizado y O(n log n) garantizado en la STL de C++.
Ordenamiento parcial: nth_element
Para encontrar el k-ésimo elemento sin ordenar todo: O(n) en promedio.
nth_element(v.begin(), v.begin()+k, v.end());
cout << v[k]; // k-ésimo más pequeño