Algoritmos de ordenamiento

Algoritmos de ordenamiento

Introducción

En la computación el ordenamiento de datos también cumple un rol muy importante, ya sea como un fin en sí o como parte de otros procedimientos más complejos. Se han desarrollado muchas técnicas en este ámbito, cada una con características específicas, y con ventajas y desventajas sobre las demás. Aquí voy a mostrarte algunas de las más comunes, tratando de hacerlo de una manera sencilla y comprensible.

Algoritmos más comunes.

Tabla comparativa de algoritmos

Nombre Complejidad Estabilidad Memoria adicional

Ordenamiento Burbuja (Bubblesort) O(n2) Estable No

Ordenamiento por Selección O(n2) No Estable No

Ordenamiento por Inserción O(n2) Estable No

Ordenamiento Rápido (Quicksort) O(n * log2(n)) No Estable No

Ordenamiento Burbuja (Bubblesort)

Este es el algoritmo más sencillo probablemente. Ideal para empezar. Consiste en ciclar repetidamente a través de la lista, comparando elementos adyacentes de dos en dos. Si un elemento es mayor que el que está en la siguiente posición se intercambian. ¿Sencillo no?

Pseudocódigo en C.

Tabla de variables

Nombre Tipo Uso

lista Cualquiera Lista a ordenar

TAM Constante entera Tamaño de la lista

i Entero Contador

j Entero Contador

temp El mismo que los elementos de la lista Para realizar los intercambios

1. for (i=1; i<TAM; i++)

2. for j=0 ; j<TAM - 1; j++)

3. if (lista[j] > lista[j+1])

4. temp = lista[j];

5. lista[j] = lista[j+1];

6. lista[j+1] = temp;

Ordenamiento por Selección.

Este algoritmo también es sencillo. Consiste en lo siguiente:

• Buscas el elemento más pequeño de la lista.

• Lo intercambias con el elemento ubicado en la primera posición de la lista.

• Buscas el segundo elemento más pequeño de la lista.

• Lo intercambias con el elemento que ocupa la segunda posición en la lista.

• Repites este proceso hasta que hayas ordenado toda la lista.

Pseudocódigo en C

Tabla de variables

Nombre Tipo Uso

lista Cualquiera Lista a ordenar

TAM Constante entera Tamaño de la lista

i Entero Contador

pos_men Entero Posición del menor elemento de la lista

temp El mismo que los elementos de la lista Para realizar los intercambios

1. for (i=0; i<TAM - 1; i++)

2. pos_men = Menor(lista, TAM, i);

3. temp = lista[i];

4. lista[i] = lista [pos_men];

5. lista [pos_men] = temp;

Ordenamiento por Inserción

Para simular esto en un programa necesitamos tener en cuenta algo: no podemos desplazar los elementos así como así o se perderá un elemento. Lo que hacemos es guardar una copia del elemento actual (que sería como la carta que tomamos) y desplazar todos los elementos mayores hacia la derecha. Luego copiamos el elemento guardado en la posición del último elemento que se desplazó

Pseudocódigo en C.

^

Tabla de variables

Nombre Tipo Uso

lista Cualquiera Lista a ordenar

TAM Constante Entera Tamaño de la lista

i Entero Contador

j Entero Contador

temp El mismo que los elementos de la lista Para realizar los intercambios

1. for (i=1; i<TAM; i++)

2. temp = lista[i];

3. j = i - 1;

4. while ( (lista[j] > temp) && (j >= 0) )

5. lista[j+1] = lista[j];

6. j--;

7. lista[j+1] = temp;

Ordenamiento Rápido (Quicksort)

Esta es probablemente la técnica más rápida conocida. Fue desarrollada por C.A.R. Hoare en 1960. El algoritmo original es recursivo, pero se utilizan versiones iterativas para mejorar su rendimiento (los algoritmos recursivos son en general más lentos que los iterativos, y consumen más recursos). El algoritmo fundamental

...