4.1 CONCEPTOS GENERALES
Se
considera ordenar al proceso de reorganizar un conjunto dado de objetos en una
secuencia determinada. Cuando se analiza un método de ordenación, hay que
determinar cuántas comparaciones e intercambios se realizan para el caso más
favorable, para el caso medio y para el caso más desfavorable.
Uno
de los procedimientos más comunes y útiles en el procesamiento de datos, es la
clasificación u ordenación de los mismos.
La
colocación en orden de una lista de valores se llama Ordenación.
Por ejemplo, se podría disponer una lista de valores numéricos en orden
ascendente o descendente, o bien una lista de nombres en orden alfabético. La
localización de un elemento de una lista se llama búsqueda. Tal operación se
puede hacer de manera más eficiente después de que la lista ha sido ordenada.
Existen varios métodos para ordenamiento, clasificados
en tres formas:
·
Inserción.
·
Intercambio
·
Selección
Un método simple y directo, fácil de comprender pero
de escasa eficiencia respecto al tiempo de ejecución, y un método rápido, más
sofisticado en su ejecución por la complejidad de las operaciones a realizar,
pero mucho más eficiente en cuanto a tiempo de ejecución, para arreglos con
pocos elementos, los métodos directos son más eficientes (menor tiempo de
ejecución) mientras que para grandes cantidades de datos se deben emplear los
llamados métodos rápidos.
4.2 ORDENAMIENTO POR
INTERCAMBIO
El método de intercambio se basa en comparar los elementos del arreglo
e intercambiarlos si su posición actual o inicial es contraria inversa a la
deseada. Pertenece a este método el de la burbuja clasificada como intercambio
directo. Aunque no es muy eficiente para ordenar listas grandes, es fácil de
entender y muy adecuado para ordenar una pequeña lista de unos 100 elementos o
menos.
Ordenación
de burbujeo consiste en un recorrido completo a través del
arreglo, en el que se comparan los contenidos de las casillas adyacentes, y se
cambian si no están en orden. La ordenación por burbujeo completa consiste en
una serie de pasadas ("burbujeo") que termina con una en la que ya no
se hacen cambios porque todo está en orden.
Ejemplo:
Supóngase que están almacenados
cuatro números en un arreglo con casillas de memoria de x[1] a x[4]. Se desea
disponer esos números en orden creciente. La primera pasada de la ordenación
por burbujeo haría lo siguiente:
Comparar el contenido de x[1] con
el de x[2]; si x[1] contiene el mayor de los números, se intercambian sus
contenidos.
Comparar el contenido de x[2] con
el de x[3]; e intercambiarlos si fuera necesario.
Comparar el contenido de x[3] con
el de x[4]; e intercambiarlos si fuera necesario.
Al final de la primera pasada, el
mayor de los números estará en x[4].
4.3 ORDENAMIENTO POR SELECCIÓN
Los métodos de ordenación por selección se basan en dos principios básicos:
·
Seleccionar el
elemento más pequeño (o más grande) del arreglo.
·
Colocarlo en la
posición más baja (o más alta) del arreglo.
A diferencia del método de la burbuja, en este método
el elemento más pequeño (o más grande) es el que se coloca en la posición final
que le corresponde.
for(j=0;j<strln(frase)-1;j++)
for(int i=j+1;i<strln(frase);i++)
if frase(frase[j]>frase[i]){
char temp=frase[i];
frase[i]=frase[j];
frase[j]=temp ;
char temp=frase[i];
frase[i]=frase[j];
frase[j]=temp ;
4.4 ORDENAMIENTO POR INSERCIÓN
Este método consiste en insertar los elementos no ordenados del
arreglo en subarreglos del mismo que ya estén ordenados. Dependiendo del método
elegido para encontrar la posición de inserción tendremos distintas versiones del
método de inserción.
char temp=frase[i] ;
int i=k-1 ;
while (temp<frase[i])
int i=k-1 ;
while (temp<frase[i])
{
frase[i+1]=frase[i] ;
i-- ;
}
frase[i+1]=temp
;
4.5 ORDENAMIENTO POR QUICKSORT
Basa
su estrategia en la idea intuitiva de que es más fácil ordenar una gran estructura
de datos subdividiéndolas en otras más pequeñas introduciendo un orden relativo
entre ellas. En otras palabras, si dividimos el array a ordenar en dos
subarrays de forma que los elementos del subarray inferior sean más pequeños
que los del subarray superior, y aplicamos el método reiteradamente, al final
tendremos el array inicial totalmente ordenado. Existen además otros métodos
conocidos, el de ordenación por montículo y el de shell.
void
Quicksort(int* v, int b, int t)
{
int pivote;
if(b < t){
pivote=colocar(v, b, t);
Quicksort(v, b, pivote-1);
Quicksort(v, pivote+1, t);
}
}
4.6
ORDENAMIENTO POR HEAPSORT
El ordenamiento por montículos (heapsort) es un algoritmo de ordenamiento no recursivo, no estable,
con complejidad computacional. 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.
4.7 ALGORITMOS PARA LOS MÉTODOS
DE ORDENAMIENTO
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. Las
relaciones de orden más usadas son el orden numérico y el orden lexicográfico. Ordenamientos eficientes son importantes para optimizar
el uso de otros algoritmos (como los de búsqueda y
fusión) que requieren listas ordenadas para una ejecución rápida. También es
útil para poner datos en forma canónica y para generar resultados legibles.
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.
§
Por el tiempo que tardan en realizar la
ordenación, dadas entradas ya ordenadas o inversamente ordenadas:
§
Algoritmos
de ordenación no natural: Tarda lo mínimo
posible cuando la entrada está inversamente ordenada.
