ESTRUCTURA DE DATOS: MÉTODOS DE ORDENAMIENTO EN C++

Los métodos de ordenamiento en el contexto de programación, son algoritmos que permiten ordenar datos de acuerdo a la necesidad en la que se quiera mostrar dichos datos, sea de manera ascendente o descendente. En cada caso se pueden aplicar diferentes algoritmos como los de bubble sort, selection sort, insertion sort, shell sort, shake sort y qick sort; claro que pueden existir otro más, sin embargo, en este post veremos cada uno de los mencionados, de forma breve.

[ESTRUCTURA DE DATOS] ESTRUCTURA DE DATOS: MÉTODOS DE ORDENAMIENTO EN C++

Los métodos de ordenamiento son algoritmos necesarios para tener información organizada, de tal manera que sirvan para ciertos propósitos, como por ejemplo: tener la data de manera legible para los usuarios, aplicar algoritmos de búsqueda eficientes como la búsqueda binaria frente a una comparativa de la búsqueda lineal (revisa un ejemplo de esto último en el siguiente enlace: https://github.com/kaaf030191/appconsed20251/tree/master/08-05-2025) y así para muchas otras situaciones que podrían presentarse; mencionado lo anterior, veamos un poco de estos algoritmos de ordenamiento, y claro, al menos tratemos los más conocidos.

Bubble Sort (Ordenamiento de Burbuja)

Bubble Sort es uno de los métodos de ordenamiento más sencillos y fáciles de entender. La idea básica es recorrer la lista una y otra vez, comparando elementos que están uno al lado del otro. Si alguno está fuera de lugar, se intercambian. Este proceso se repite varias veces, como si las burbujas más grandes fueran subiendo hasta el final, hasta que todo queda ordenado y ya no hay nada más que mover.

Procedimiento:

1. Comparación e intercambio: Se recorre el arreglo comparando cada par de elementos consecutivos.
2. Pasadas múltiples: El proceso se repite n-1 veces (en el peor caso).
3. Condición de término: Si en una pasada completa no se realizan intercambios, el arreglo está ordenado.

Representación visual:

[5, 3, 8, 4] → [3, 5, 4, 8] → [3, 4, 5, 8]

Selection Sort (Ordenamiento por Selección)

Selection Sort trabaja como si estuvieras organizando una fila de objetos uno por uno. Comienza separando mentalmente el arreglo en dos partes: una ya ordenada y otra que aún está desordenada. En cada paso, busca el elemento más pequeño dentro de la parte desordenada y lo coloca en su lugar correcto, justo al final de la sección ordenada. Así, poco a poco, todo el arreglo va tomando orden.

Procedimiento:

1. Selección del mínimo: Busca el elemento más pequeño en el subarreglo desordenado.
2. Intercambio: Lo intercambia con el primer elemento del subarreglo desordenado.
3. Expansión del subarreglo ordenado: Repite el proceso hasta que todo el arreglo esté ordenado.

Representación visual:

[5, 3, 8, 4] → [3, 5, 8, 4] → [3, 4, 8, 5] → [3, 4, 5, 8]

Insertion Sort (Ordenamiento por Inserción)

Insertion Sort ordena poco a poco, como cuando organizas cartas en tu mano. Toma un elemento a la vez y lo coloca justo donde debe ir dentro de los que ya están ordenados. Así, con cada paso, la parte ordenada crece y el arreglo va tomando forma de manera natural.

Procedimiento:

1. Subarreglo ordenado inicial: Comienza con el primer elemento como subarreglo ordenado.
2. Inserción ordenada: Toma el siguiente elemento y lo inserta en la posición correcta dentro del subarreglo ordenado.
3. Repetición: Continúa hasta que todos los elementos estén en su lugar.

Representación visual:

[5, 3, 8, 4] → [3, 5, 8, 4] → [3, 5, 8, 4] → [3, 4, 5, 8]

Shell Sort (Ordenamiento de Shell)

Shell Sort es una versión mejorada de Insertion Sort que empieza ordenando elementos que están lejos entre sí. En lugar de comparar uno por uno, agrupa los elementos usando saltos o "brechas" y los va organizando. A medida que avanza, esas brechas se hacen más pequeñas, hasta que todo queda ordenado con comparaciones más cercanas.

Procedimiento:

1. Elección de brechas: Se define una secuencia de brechas (ej: n/2, n/4, ..., 1).
2. Aplicar insertion sort por grupos: Para cada brecha, se ordenan subarreglos formados por elementos separados por esa distancia.
3. Reducción de brecha: Se repite hasta que la brecha sea 1 (equivalente a Insertion Sort clásico).

Representación visual:

Arreglo: [9, 4, 2, 7, 5]
Gap = 2 → Subgrupos: [9, 2, 5] y [4, 7] → Ordenados: [2, 4, 5, 7, 9]
Gap = 1 → Ajuste final con Insertion Sort

Shake Sort (Ordenamiento por Sacudida)

Shake Sort, también conocido como Cocktail Sort, es una versión más dinámica del Bubble Sort. En lugar de recorrer la lista solo en una dirección, este algoritmo va y viene, primero de izquierda a derecha y luego de derecha a izquierda, moviendo los elementos a su lugar desde ambos extremos, como si agitara los datos hasta que queden bien ordenados.

Procedimiento:

1. Pasada ascendente: Igual que Bubble Sort (mueve el mayor al final).
2. Pasada descendente: Recorre el arreglo en reversa, moviendo el menor al inicio.
3. Repetición: Hasta que no haya intercambios en ambas pasadas.

Representación visual:

[5, 1, 4, 2] → [1, 4, 2, 5] (ida) → [1, 2, 4, 5] (vuelta)

Quick Sort (Ordenamiento Rápido)

Quick Sort se basa en la estrategia de “divide y vencerás”, lo que significa que resuelve el problema dividiéndolo en partes más pequeñas. Primero, elige un elemento del arreglo llamado pivote. Luego, organiza el resto de los elementos colocando los que son menores al pivote a la izquierda y los mayores a la derecha. Una vez hecho eso, repite el mismo proceso con cada una de las dos partes, hasta que todo esté en orden.

Procedimiento:

1. Pivote: Se elige un elemento como punto de referencia.
2. Reordenar: Se separan los menores a la izquierda y los mayores a la derecha.
3. Dividir: Se parte el arreglo en dos para seguir ordenando.

Representación visual:

Arreglo: [3, 6, 8, 2, 5]
Pivote = 5 → Partición: [3, 2] 5 [6, 8]
Luego se ordenan recursivamente [3, 2] y [6, 8]

¿Qué hay respeto al rendimiento y en qué casos podría ser mejor usar uno u otro algoritmo?

CONCLUSIÓN

Cada algoritmo tiene sus ventajas y desventajas en términos de eficiencia y uso de memoria. Mientras que Bubble Sort e Insertion Sort son simples pero ineficientes para grandes conjuntos de datos, Quick Sort y Shell Sort ofrecen mejor rendimiento en la práctica.

Autor: Kevin Arias