métodos de ordenamiento

Un algoritmo de ordenamiento es un algoritmo que pone elementos de una lista o un vector en una secuencia dada por una relación de orden, es decir, el resultado de salida ha de ser una permutación —o reordenamiento— de la entrada que satisfaga la relación de orden dada.

Los algoritmos de ordenamiento se pueden clasificar de las siguientes maneras:  La más común es clasificar según el lugar donde se realice la ordenación

·         Algoritmos de ordenamiento interno: en la memoria del ordenador.

·         Algoritmos de ordenamiento externo: en un lugar externo como un disco duro.

Por el tiempo que tardan en realizar la ordenación, dadas entradas ya ordenadas o inversamente ordenadas:

·         Algoritmos de ordenación natural: Tarda lo mínimo posible cuando la entrada está ordenada.

·         Algoritmos de ordenación no natural: Tarda lo mínimo posible cuando la entrada está inversamente ordenada.

Por estabilidad: un ordenamiento estable mantiene el orden relativo que tenían originalmente los elementos con claves iguales. Por ejemplo, si una lista ordenada por fecha se reordena en orden alfabético con un algoritmo estable, todos los elementos cuya clave alfabética sea la misma quedarán en orden de fecha.

Ordenación por intercambio (burbuja)

Es uno de los métodos relativamente más sencillo e intuitivo, pero también resulta ser muy ineficiente. Se basa en la ordenación por cambio, y recibe su nombre de la semejanza con las burbujas de un depósito de agua donde cada burbuja busca su propio nivel.

Los pasos a efectuar en el caso de una ordenación ascendente (en el caso de la ordenación descenderte solo habría que cambiar el signo de comparación) son:

1. Comparar el primer y segundo elemento, intercambiarlos si el primero es mayor que el segundo; luego se compara el primero con el tercero, intercambiándose en caso necesario, y el proceso se repite hasta llegar al último elemento.

2. Se repite el paso anterior, pero ahora con el segundo y tercero, en caso de ser necesario se intercambian, y así hasta llegar a comparar el segundo con el ultimo.

Consideremos el siguiente ejemplo. Se cuenta con un vector de 6 posiciones donde se inicia una lista de números { 7, 2, 8, 3, 5, 1 }, la cual será ordenada en forma ascendente { 1, 2, 3, 5, 7, 8 }, observe como se declara una variable constante entera llamada n la cual tiene un valor de 6, enseguida se declara un vector de tipo entero que contendrá una cantidad n de casillas, en este caso 6, declaramos también las variables i y j que nos ayudaran a desplazarnos entre casilla y  casilla para hacer las comparaciones. Y finalmente la variable tem, almacenara temporalmente el valor a intercambiar entre las casillas que lo necesiten.

For (int i = 0; i < n-1; i++)

For (int j = i + 1; j < n; j++) {

if ( v[i] > v[j] ) { //realiza la comparación

int tem = v[i]; //si es cierta intercambia los datos

v[i] = v[j];

v[j] = tem;

}

}

Método de selección

La idea básica es encontrar el elemento más pequeño (grande), en orden ascendente de la lista, e  intercambiarlo con el elemento que ocupa la primera posición en la lista, a continuación se busca el siguiente elemento más pequeño y se transfiere a la segunda posición. Se repite el proceso hasta que el último elemento ha sido transferido a su posición correcta.

El algoritmo de ordenación depende a su vez del algoritmo necesario para localizar el componente mayor (menor) de un array. Es un proceso muy similar al método de la burbuja pero haciendo más eficiente la búsqueda y evitando intercambios innecesarios.

for (int i = 0, j = 0, k = 0; i < n-1; i++) {

k = i;

for (j = i+1; j < n; j++)

if ( v[k] > v[j] )

k = j;

int tem = v[i];

v[i] = v[k];

v[k] = tem;

}

}

Método de Inserción

Este método también se denomina “método del jugador de cartas”, por la semejanza con la forma de clasificar las cartas de una baraja, insertando cada carta en el lugar adecuado.

El algoritmo ordena los dos primeros elementos de la lista, a continuación el tercer elemento se inserta en la posición que corresponda, el cuarto se inserta en la lista de tres elementos, y así sucesivamente. Este proceso continua hasta que la lista este totalmente ordenada.

for (int i = 1, j = 0; i < n; i++) {

int tem = v[i];

j = i - 1;

while ( j >= 0 && tem < v[j]) {

v[j+1] = v[j];

j--;

}

v[j+1] = tem;

}

}

Ordenación basada en comparaciones (Heap Sort)

Es una variante del algoritmo de selección, El ordenamiento por montículos (Heap sort) es un algoritmo de ordenación no recursivo, no estable, con complejidad computacional O(n log n).

Este algoritmo consiste en almacenar todos los elementos del vector a ordenar en un montículo

(heap), y luego extraer el nodo que queda como nodo raíz del montículo (cima) en sucesivas iteraciones obteniendo el conjunto ordenado. Basa su funcionamiento en una propiedad de los montículos, por la cual, la cima contiene siempre el menor elemento (o el mayor, según se haya definido el montículo) de todos los almacenados en él.

Ordenamiento Por Enumeración

En este tipo de algoritmos cada elemento es comparado contra los demás. En la comparación se cuenta cuántos elementos son más pequeños que el elemento que se está analizando, generando así una ENUMERACION. El número generado para cada elemento indicará su posición.

No basado en comparación.