Algoritmos de ordenamiento: Burbuja, selección e inserción

En este episodio de Code Time continuamos con el camino de la programación profundizando en el estudio de algoritmos. En esta nota nos enfocaremos más que nada en los algoritmos de ordenamiento burbuja, inserción y selección.

Problemas de ordenamiento

A la hora de resolver problemas suele surgir la necesidad de ordenar una secuencia de elementos de algún tipo. Esta tarea que para un ser humano es relativamente simple no es nada trivial para las máquinas. Para poder hacerlo existen diversas formas o algoritmos que nos permiten dar un orden.
Listen to “Code Time (63): Algoritmos de ordenamiento” on Spreaker.
Hoy nos centraremos en los algoritmos de ordenamiento clásicos: burbuja, inserción y selección.

Antes que nada consideremos un orden

Obviamente para poder ordenar algo es necesario poder establecer un orden en los elementos. Esto en si no afecta a secuencias de elementos como números o palabras. Existe un orden por defecto para los mismos. En caso de querer permitir ordenar secuencias con elementos de un tipo arbitrario suele ser necesario incorporar una función que dado dos elementos se indique el orden de ambos.

Teniendo esto en claro hay que saber comprobar si un arreglo, en este caso, está ordenado o no. Esto es si todo elemento es menor o igual al elemento que está a la derecha. Para ejemplificar los casos en esta nota utilizaremos código en C:

1. sorted = 1;
2. for (i = 0; i < sz – 1; i++) {
3.    if (data[i] > data[i+1]) {
4.        sorted = 0;
5.    }
6. }

Donde sorted es una variable booleana, sz corresponde al tamaño de la secuencia y data es la secuencia a trabajar. Al terminar el código, sorted valdrá 1 si el arreglo está ordenado y 0 en caso contrario.

Algoritmos de ordenamiento

Bubble Sort u ordenamiento de burbuja

En caso de que un elemento tenga un elemento más chico a su derecha al hacer la comprobación, podremos intentar repararlo intercambiando los elementos. El algoritmo de la burbuja repite esta reparación hasta asegurarse que el arreglo está ordenado:

1. do {
2.    sorted = 1;
3.    for (i = 0; i < sz – 1; i++) {
4.        if (data[i] > data[i+1]) {
5.            sorted = 0;
6.            swap(&data[i], &data[i+1]);
7.        }
8.    }
9. } while (sorted != 1);

Este código recorre un arreglo comprobando el orden de los elementos. Si en algún momento se encuentran dos elementos desordenados se los ordena y se marca el arreglo como desordenado. Gracias a esta bandera (sorted) sabremos que hay que volver a recorrer el arreglo para comprobar si está ordenado nuevamente. Esto se repite hasta que efectivamente la secuencia está ordenada.

Insertion Sort u ordenamiento por inserción

El procedimiento general de este algoritmo funciona asumiendo que dividimos el arreglo en dos: la parte ordenada y la parte desordenada. Sus pasos son:

1. Tomar un elemento de la parte sin ordenar.
2. Insertarlo en la parte ordenada del arreglo, en la posición que le corresponde.
3. Volver al primer paso, hasta que no queden elementos en la parte sin ordenar.

Un pequeño ejemplo puede ayudar a entender

Selection Sort u ordenamiento por selección

En este algoritmo también asumimos el arreglo dividido en una parte ordenada y una parte desordenada. Pero esta vez en cada paso pasamos el mínimo:

1. Buscamos el mínimo elemento en la parte desordenada.
2. Intercambiamos el mínimo con el primer elemento de la parte desordenada.
3. Volvemos al primer paso, considerando que el arreglo desordenado con un elemento menos (su mínimo).

Un pequeño ejemplo puede ayudar a entender

Para finalizar…

BandaGeek no almacena ni distribuye el software aquí expuesto y la responsabilidad de su uso recae en el usuario.

   Gmail

Spreaker    iTunes    Ivoox    Canal de Telegram    Soundcloud