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.