Fundamentos de Algoritmos: Implementación y Eficiencia de Métodos de Ordenación y Búsqueda

Algoritmos Fundamentales de Ordenación y Búsqueda

Métodos de Ordenación (Sorting)

Burbuja (Bubble Sort)

Es un método clásico, sencillo y poco eficiente. Se basa en la comparación de elementos adyacentes, donde se intercambian sus valores si están desordenados. De esta forma, los valores pequeños burbujean hacia el fondo de la lista.

Burbuja Mejorado (Optimized Bubble Sort)

Se puede mejorar si se dispone de algún tipo de indicador (variable lógica o booleana) que registre si se han producido intercambios en la pasada. Cuando se recorre la lista y el indicador no refleja intercambios, la lista ya estará ordenada, deteniendo el proceso prematuramente.

Ordenación por Selección (Selection Sort)

Es un algoritmo que, dada una lista de $N$ elementos, sigue los siguientes pasos:

1. Buscar el mayor elemento de la lista.
2. Intercambiar el elemento mayor con el elemento en el subíndice $N$.
3. Se busca el elemento mayor en la sublista de subíndices $1..N-1$.
4. Se repite el proceso en la sublista, y así sucesivamente.

Inserción (Insertion Sort)

Es un método basado en la técnica utilizada por los jugadores de cartas para clasificarlas. El jugador va insertando cada carta en su posición correcta. El método se basa en considerar una parte de la lista ya ordenada y ubicar cada uno de los elementos restantes, insertándolos en el lugar que les corresponde por su valor.

Shell Sort

Es la ordenación por disminución de incremento (o por intervalos).

1. Si se tiene una lista de 16 elementos, esta se divide inicialmente en 8 grupos de 2.
2. Se clasifica cada grupo por separado: se comparan las parejas de elementos y, si no están ordenados, se intercambian de posiciones.
3. Se divide ahora la lista en 4 grupos de 4 y nuevamente se clasifica cada grupo por separado.
4. Un tercer paso clasifica 2 grupos de 8 registros, y luego un cuarto paso completa el trabajo clasificando los 16 registros.

Mezcla (Merging)

Consiste en tomar dos vectores (o listas) ordenados y obtener un nuevo vector también ordenado. Este proceso es fundamental en algoritmos como Merge Sort.

Métodos de Búsqueda

Búsqueda Binaria (Binary Search)

Es eficiente para listas grandes de datos. Se basa en el método de divide y vencerás en una lista previamente ordenada de números. Se divide la lista en 2, se busca el elemento central, se compara con el valor buscado y se sigue dividiendo la sublista correspondiente hasta encontrar el elemento o determinar su ausencia.