Algoritmosc++ordenamientosortalgoritmos

Algoritmos de Ordenamiento

Entiende qué es ordenar datos y por qué es fundamental en programación

OOI Oaxaca9 de febrero de 20264 min read

¿Por qué ordenar?

Imagina que tienes una biblioteca con 10,000 libros tirados en el suelo sin orden. Si alguien te pide un libro, ¿cuánto tardarías en encontrarlo? Podrías tardar horas revisando uno por uno. Pero si los libros están ordenados alfabéticamente en estantes, lo encuentras en segundos.

Ordenar datos es una de las operaciones más fundamentales en ciencias de la computación. Muchísimos problemas se simplifican enormemente si primero ordenas los datos.

Ordenar en C++ con `sort()`

La buena noticia: en competencias, casi nunca necesitas programar un algoritmo de ordenamiento desde cero. C++ tiene una función sort() increíblemente eficiente (usa IntroSort, una combinación de QuickSort, HeapSort y InsertionSort):

#include <algorithm>  // O #include <bits/stdc++.h>
#include <vector>

vector<int> v = {5, 2, 8, 1, 9, 3};

sort(v.begin(), v.end());
// v = {1, 2, 3, 5, 8, 9}

Ordenar arreglos

int arr[] = {5, 2, 8, 1, 9, 3};
int n = 6;

sort(arr, arr + n);
// arr = {1, 2, 3, 5, 8, 9}

Orden descendente

// Forma 1: reverse iterators
sort(v.rbegin(), v.rend());

// Forma 2: función de comparación
sort(v.begin(), v.end(), greater<int>());

// Forma 3: lambda
sort(v.begin(), v.end(), [](int a, int b) { return a > b; });

Ordenar con criterio personalizado

// Ordenar strings por longitud
vector<string> palabras = {"hola", "a", "mundo", "si"};
sort(palabras.begin(), palabras.end(), [](string &a, string &b) {
    return a.size() < b.size();
});
// {"a", "si", "hola", "mundo"}

¿Por qué aprender algoritmos de ordenamiento?

Si sort() ya existe, ¿para qué aprender cómo funcionan los algoritmos? Varias razones:

Aparecen en exámenes de olimpiada y entrevistas técnicas.
Entiendes la complejidad y puedes elegir la herramienta correcta.
Aprendes técnicas (dividir y conquistar, etc.) que aplican a otros problemas.
Algunos problemas requieren variaciones que sort() no hace directamente.

Complejidad de los algoritmos de ordenamiento

Algoritmo	Mejor caso	Caso promedio	Peor caso	¿Estable?
Burbuja	$O(n)$	$O(n^2)$	$O(n^2)$	Sí
Selección	$O(n^2)$	$O(n^2)$	$O(n^2)$	No
Inserción	$O(n)$	$O(n^2)$	$O(n^2)$	Sí
Merge Sort	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	Sí
Quick Sort	$O(n \log n)$	$O(n \log n)$	$O(n^2)$	No
`sort()` de C++	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	No
`stable_sort()`	$O(n \log n)$	$O(n \log n)$	$O(n \log^2 n)$	Sí
Cubeta (Counting)	$O(n + k)$	$O(n + k)$	$O(n + k)$	Sí

¿Qué significa "estable"? Un ordenamiento es estable si los elementos iguales mantienen su orden relativo original. Ejemplo: si María y Pedro tienen la misma calificación y María estaba antes, un sort estable garantiza que María siga antes.

Aplicaciones de ordenar en competencias

1. Encontrar duplicados

sort(v.begin(), v.end());
for (int i = 1; i < n; i++) {
    if (v[i] == v[i-1]) {
        cout << "Duplicado: " << v[i] << endl;
    }
}

2. Encontrar la mediana

sort(v.begin(), v.end());
cout << v[n / 2] << endl;  // Mediana (para n impar)

3. Búsqueda binaria (requiere datos ordenados)

sort(v.begin(), v.end());
bool encontrado = binary_search(v.begin(), v.end(), objetivo);

4. Problemas de scheduling (greedy)

Ordenar actividades por tiempo de fin y seleccionar la mayor cantidad posible sin solapamiento.

Ejercicio de práctica

Lee N números. Ordénalos y muestra la diferencia entre el mayor y el menor (el rango).

Entrada:

5
3 1 4 1 5

Salida: 4 (máximo 5 - mínimo 1 = 4)

Ver solución

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> v(n);
    for (int i = 0; i < n; i++) cin >> v[i];

    sort(v.begin(), v.end());
    cout << v[n-1] - v[0] << endl;

    return 0;
}

Siguiente paso

Aprende el Ordenamiento Burbuja, el algoritmo más simple de entender.