Objetivos
Una vez que se haya leído y estudiado este capítulo, usted podrá:
• Conocer los algoritmos basados en el intercambio de elementos.
• Conocer el algoritmo de ordenación por inserción.
• Conocer el algoritmo de selección.
• Distinguir entre los algoritmos de ordenación basados en el intercambio
y en la inserción.
• Saber la eficiencia de los métodos básicos de ordenación.
• Conocer los métodos más eficientes de ordenación.
• Aplicar métodos mas eficientes de ordenación de arrays.
• Ordenar vectores de objetos.
• Diferenciar entre búsqueda secuencial y búsqueda binaria.
Introducción
Muchas actividades humanas requieren que diferentes colecciones de elementos utilizados se pongan en un orden específico. Las oficinas de correo y las empresas de mensajería ordenan el correo y los paquetes por códigos postales con el objeto de conseguir una entrega eficiente; las facturas telefónicas se ordenan por la fecha de las llamadas; los anuarios o listines telefónicos se ordenan por orden alfabético de apellidos con el fin último de encontrar fácilmente el número de teléfono deseado; los estudiantes de una clase en la universidad se ordenan por sus apellidos o por los números de expediente.
Por estas circunstancias una de las tareas que realizan más frecuentemente las computadoras en el procesamiento de datos es la ordenación.
El estudio de diferentes métodos de ordenación es una tarea intrínsecamente interesante desde un punto de vista teórico y, naturalmente, práctico. Este capítulo estudia los algoritmos y las técnicas de ordenación más usuales y su implementación en Java; también la manera de ordenar objetos con la funcionalidad que proporcionan las clases en Java. De igual modo, se estudiará el análisis de los diferentes métodos de ordenación con el objetivo de conseguir la máxima eficiencia en su uso real.
En el capítulo se analizarán los métodos básicos y los más avanzados empleados en programas profesionales.
ORDENACIÓN
La ordenación o clasificación de datos (sort, en inglés) es una operación consistente en disponer un conjunto —estructura— de datos en algún determinado orden con respecto a uno de los campos de los elementos del conjunto. Por ejemplo, cada elemento del conjunto de datos de una
guía telefónica tiene un campo nombre, un campo dirección y un campo número de teléfono; la guía telefónica está dispuesta en orden alfabético de nombres. Los elementos numéricos se pueden ordenar en orden creciente o decreciente de acuerdo al valor numérico del elemento. En terminología de ordenación, el elemento por el cual está ordenado un conjunto de datos (o se está buscando) se denomina clave.
Una colección de datos (estructura) puede ser almacenada en memoria central o en archivos de datos externos guardados en unidades de almacenamiento magnético (discos, cintas, CD-ROM, DVD, etc.). Cuando los datos se guardan en un array, en una lista enlazada o en un árbol, se denomina ordenación interna; estos datos se almacenan exclusivamente para tratamientos internos que se utilizan para gestión masiva de datos, se guardan en arrays de una o varias dimensiones. Si los datos están almacenados en un archivo, el proceso de ordenación se llama ordenación externa
Este capítulo estudia los métodos de ordenación de datos que están en la memoria principal, ordenación interna.
Una lista está ordenada por la clave k si la lista está en orden ascendente o descendente con respecto a esa clave. La lista está en orden ascendente si:
i < j implica que k[i] <= k[j]
y está en orden descendente si:
i > j implica que k[i] <= k[j]
para todos los elementos de la lista. Por ejemplo, para una guía telefónica, la lista está clasificada en
orden ascendente por el campo clave k, donde k[i] es el nombre del abonado (apellidos, nombre).
4 5 14 21 32 45 orden ascendente
75 70 35 16 14 12 orden descendente
Zacarias Rodriguez Martinez Lopez Garcia orden descendente
Los métodos de ordenación se suelen dividir en dos grandes grupos:
• directos burbuja, selección, inserción
• indirectos (avanzados) shell, ordenación rápida, ordenación por mezcla, radixsort
En el caso de listas pequeñas, los métodos directos se muestran eficientes, sobre todo, porque
los algoritmos son sencillos, por lo que su uso es muy frecuente. Sin embargo, en listas grandes,
estos métodos se muestran ineficaces y es preciso recurrir a los métodos avanzados.
ALGORITMOS DE ORDENACIÓN BÁSICOS
Existen diferentes algoritmos de ordenación elementales o básicos cuyos detalles de implementación se pueden encontrar en diferentes libros de algoritmos. La enciclopedia de referencia es [Knuth 1973] y, sobre todo, la 2ª edición publicada en el año 1998 [Knuth 1998] . Los
algoritmos presentan diferencias entre ellos que los convierten en más o menos eficientes y prácticos según sea la rapidez y eficiencia demostrada por cada uno de ellos. Los algoritmos básicos de ordenación más simples y clásicos son:
• Ordenación por selección.
• Ordenación por inserción.
• Ordenación por burbuja.
Los métodos más recomendados son el de selección y el de inserción, aunque se estudiará el método de burbuja por ser el más sencillo, pero también es el más ineficiente; por esta causa no se recomienda su uso, pero si conocer su técnica
Las técnicas que se estudian a continuación considerarán, esencialmente, la ordenación de elementos de una lista (array) en orden ascendente. En cada caso se analiza la eficiencia computacional del algoritmo.
ORDENACIÓN POR INTERCAMBIO
El algoritmo de ordenación tal vez más sencillo sea el denominado de intercambio, que ordena los elementos de una lista en orden ascendente. El algoritmo se basa en la lectura sucesiva de la lista a ordenar, comparando el elemento inferior de la lista con los restantes y efectuando un
intercambio de posiciones cuando el orden resultante de la comparación no sea el correcto.
El algoritmo se ilustra con la lista original 8, 4, 6, 2 que ha de convertirse en la lista ordenada 2, 4, 6, 8. El algoritmo efectúa n-1 pasadas (3 en el ejemplo), siendo n el número de elementos, realizando las comparaciones indicadas en las figuras
Pasada 1
El elemento de índice 0 (a[0]) se compara con cada elemento posterior de la lista de índices 1, 2
y 3. En cada comparación se comprueba si el elemento siguiente es más pequeño que el elemento de
índice 0 y en ese caso, se intercambian. Después de terminar todas las comparaciones, el elemento
más pequeño se sitúa en el índice 0.
Pasada 2
El elemento más pequeño ya está en la posición de índice 0, y se considera la sublista restante 8, 6, 4. El algoritmo continúa comparando el elemento de índice 1 con los elementos posteriores de índices 2 y 3. Por cada comparación, si el elemento mayor está en el índice 1 se intercambian los elementos. Después de hacer todas las comparaciones, el segundo elemento más pequeño de la lista se almacena en el índice 1.
Pasada 3
La sublista a considerar ahora es 8, 6, ya que 2, 4 está ordenada. Se produce entre los dos elementos de la sublista una comparación única
Codificación del algoritmo de ordenación por intercambio
El método ordIntercambio() implementa el algoritmo descrito utilizando dos bucles anidados.
El tipo de los elementos de la lista es entero, es válido cualquier otro tipo ordinal (double,char...). Suponiendo que la lista es de tamaño n, el rango del bucle externo va desde el índice 0 hasta n-2. Por cada índice i, se comparan los elementos posteriores de índices j = i +1, i +2,..., n-
1. El intercambio (swap) de los elementos a[i],a[j] se realiza en el método intercambiar():
public static void intercambiar(int []a, int i, int j)
{
int aux = a[i];
a[i] = a[j];
a[j]= aux ;
}
El array (arreglo) dispone de tantos elementos como posiciones creadas. Por ello el método
ordIntercambio() tiene un único argumento (int [] a); el atributo a.length es el valor
del número de elementos (n).
public static void ordIntercambio (int a[])
{
int i, j;
for (i = 0 ; i < a.length-1; i++)
// sitúa mínimo de a[i+1]...a[n-1] en a[i]
for (j = i+1 ; j < a.length; j++)
if (a[i] > a[j])
{
intercambiar(a, i, j);
}
}
ORDENACIÓN POR SELECCIÓN
Considérese el algoritmo para ordenar un array a[] de enteros en orden ascendente, es decir, si el array a[] tiene n elementos, se trata de ordenar los valores del array de modo que a[0] sea el valor más pequeño, el valor almacenado en a[1] sea el siguiente más pequeño, y así
hasta a[n-1] que ha de contener el elemento de mayor valor. El algoritmo se apoya en las pasadas que intercambian el elemento más pequeño, sucesivamente con el elemento de la lista, a[], que ocupa la posición igual al orden de pasada (hay que considerar el índice 0). La
pasada inicial busca el elemento más pequeño de la lista y se intercambia con a[0], primer elemento de la lista.
Después de terminar esta primera pasada, el frente de la lista está ordenado y el resto de la lista a[1], a[2]...a[n-1] permanece desordenado. La siguiente pasada busca en esta lista desordenada y selecciona el elemento más pequeño, que se almacena entonces en la posición
a[1]. De este modo, los elementos a[0] y a[1] están ordenados y la sublista a[2], a[3]... a[n-1] desordenado; entonces, se selecciona el elemento más pequeño y se intercambia con a[2].
El proceso continúa hasta realizar n-1 pasadas, en ese momento la lista desordenada se reduce a un elemento (el mayor de la lista) y el array completo queda ordenado. Un ejemplo práctico ayudará a la comprensión del algoritmo. Consideremos un array a[] con 5 valores enteros 51, 21, 39, 80, 36:
Codificación del algoritmo de selección
El método ordSeleccion() ordena un array de números reales de n elementos, n coincide con
el atributo length del array. En la pasada i, el proceso de selección explora la sublista a[i] a
a[n-1] y fija el índice del elemento más pequeño. Después de terminar la exploración, los elementos
a[i] y a[indiceMenor] se intercambian; operación que se realiza llamando al método
intercambiar() escrito en el apartado 6.3 (es necesario cambiar tipo int por tipo double).
/*
ordenar un array de n elementos de tipo double
utilizando el algoritmo de ordenación por selección
*/
public static void ordSeleccion (double a[])
{
int indiceMenor, i, j, n;
n = a.length;
for (i = 0; i < n-1; i++)
{
// comienzo de la exploración en índice i
indiceMenor = i;
// j explora la sublista a[i+1]..a[n-1]
for (j = i+1; j < n; j++)
if (a[j] < a[indiceMenor])
indiceMenor = j;
// sitúa el elemento mas pequeño en a[i]
if (i != indiceMenor)
intercambiar(a, i, indiceMenor);
}
}
ORDENACIÓN POR INSERCIÓN
El método de ordenación por inserción es similar al proceso típico de ordenar tarjetas de nombres (cartas de una baraja) por orden alfabético consistente en insertar un nombre en su posición correcta dentro de una lista que ya está ordenada. El proceso en el caso de la lista de enteros
es:
Algoritmo de ordenación por inserción
El algoritmo correspondiente a la ordenación por inserción contempla los siguientes pasos:
1. El primer elemento a[0] se considera ordenado; es decir, la lista inicial consta de un
elemento.
2. Se inserta a[1] en la posición correcta; delante o detrás de a[0], dependiendo de si es
menor o mayor.
3. Por cada bucle o iteración i (desde i=1 hasta n-1) se explora la sublista a[i-1] ...
a[0] buscando la posición correcta de inserción de a[i]; a la vez, se mueven hacia abajo
(a la derecha en la sublista) una posición todos los elementos mayores que el elemento a
insertar a[i], para dejar vacía esa posición.
4. Insertar el elemento a[i] a la posición correcta.
Codificación del algoritmo de ordenación por inserción
La codificación del algoritmo se realiza en el método ordInsercion(). Se pasa como argumento
el array, a[], que se va a ordenar de modo creciente; el número de elementos a ordenar coincide
con el atributo del array length. Los elementos del array son de tipo entero; en realidad, pueden
ser de cualquier tipo básico y ordinal de Java.
public static void ordInsercion (int [] a)
{
int i, j;
int aux;
for (i = 1; i < a.length; i++)
{
/* indice j es para explorar la sublista a[i-1]..a[0] buscando la
posicion correcta del elemento destino*/
j = i;
aux = a[i];
// se localiza el punto de inserción explorando hacia abajo
while (j > 0 && aux < a[j-1])
{
// desplazar elementos hacia arriba para hacer espacio
a[j] = a[j-1];
j--;
}
a[j] = aux;
}
}
ALGORITMO DE BURBUJA
El algoritmo de la burbuja es uno de los métodos de ordenación más conocidos y uno de los primeros que aprenden los programadores.
Consiste en comparar pares de elementos adyacentes en un array y si están desordenanos intercambiarlos hasta que estén todos ordenados.
Si A es el array a ordenar, se realizan A.length-1 pasadas. Si la variable i es la que cuenta el número de pasadas, en cada pasada i se comprueban los elementos adyacentes desde el primero hasta A.length-i-1 ya que el resto hasta el final del array están ya ordenados. Si los elementos adyacentes están desordenados se intercambian.
El método de ordenación de la burbuja en java para ordenar un array A es el siguiente:
public static void burbuja(int [] A){
int i, j, aux;
for(i=0;i<A.length-1;i++)
for(j=0;j<A.length-i-1;j++)
if(A[j+1]<A[j]){
aux=A[j+1];
A[j+1]=A[j];
A[j]=aux;
}
}
Ejemplo de ejecución:
Ya están ordenados, pero los dos bucles for seguirán ejecutándose hasta el final.
El tiempo de ejecución del algoritmo de la burbuja es del orden O(n2)
Es uno de los peores algoritmos de ordenación en cuanto a tiempo de ejecución, solamente es recomendable su uso para ordenar listas con un número pequeño de elementos.
ORDENACIÓN SHELL
La ordenación Shell debe el nombre a su inventor, D. L. Shell. Se suele denominar también ordenación por inserción con incrementos decrecientes. Se considera que el método Shell es una mejora del método de inserción directa
En el algoritmo de inserción, cada elemento se compara con los elementos contiguos de su izquierda, uno tras otro. Si el elemento a insertar es el mas pequeño, hay que realizar muchas comparaciones antes de colocarlo en su lugar definitivo.
El algoritmo de Shell modifica los saltos contiguos resultantes de las comparaciones por saltos de mayor tamaño, y con ello se consigue que la ordenación sea más rápida. Generalmente, se toma como salto inicial n/2 (siendo n el número de elementos), y luego se reduce el salto a la
mitad en cada repetición hasta que sea de tamaño 1. El Ejemplo 6.1 ordena una lista de elementos siguiendo paso a paso el método de Shell.
Ejemplo
Obtener las secuencias parciales del vector al aplicar el método Shell para ordenar de modo
creciente la lista:
6 5 2 3 4 0
El número de elementos que tiene la lista es 6, por lo que el salto inicial es 6/2 = 3. La siguiente
tabla muestra el número de recorridos realizados en la lista con los saltos correspondiente.
Recorrido Salto Intercambios Lista
Algoritmo de ordenación Shell
Los pasos a seguir por el algoritmo para una lista de n elementos son:
1. Se divide la lista original en n/2 grupos de dos, considerando un incremento o salto entre
los elementos de n/2.
2. Se clasifica cada grupo por separado, comparando las parejas de elementos, y si no están
ordenados se intercambian.
3. Se divide ahora la lista en la mitad de grupos (n/4), con un incremento o salto entre los
elementos también mitad (n/4), y nuevamente se clasifica cada grupo por separado.
4. Así sucesivamente, se sigue dividiendo la lista en la mitad de grupos que en el recorrido
anterior con un incremento o salto decreciente en la mitad que el salto anterior, y luego
clasificando cada grupo por separado.
5. El algoritmo termina cuando se llega a que el tamaño del salto es 1.
Por consiguiente, los recorridos por la lista están condicionados por el bucle,
intervalo ← n / 2
mientras (intervalo > 0) hacer
Para dividir la lista en grupos y clasificar cada grupo se anida este código,
desde i ← (intervalo + 1) hasta n hacer
j ← i - intervalo
mientras (j > 0) hacer
k ← j + intervalo
si (a[j] <= a[k]) entonces
j ← 0
sino
Intercambio (a[j], a[k]);
j ← j - intervalo
fin _ si
fin _ mientras
fin _ desde
donde se observa que se comparan pares de elementos de índice j y k, a[j], a[k]), separados
por un salto de intervalo. Así, si n = 8, el primer valor de intervalo = 4, y los índices i = 5,
j = 1, k = 6. Los siguiente valores que toman i = 6, j = 2, k = 7 y así hasta recorrer la lista.
Para realizar un nuevo recorrido de la lista con la mitad de grupos, el intervalo se reduce a la mitad.
intervalo ← intervalo / 2
Y así se repiten los recorridos por la lista, mientras intervalo > 0.
Codificación del algoritmo de ordenación Shell
Al codificar el algoritmo es preciso considerar que Java toma como base en la indexación de
arrays índice 0 y, por consiguiente, se han de desplazar una posición a la izquierda las variables
índice respecto a lo expuesto en el algoritmo.
public static void ordenacionShell(double a[])
{
int intervalo, i, j, k;
int n= a.length;
intervalo = n / 2;
while (intervalo > 0)
{
for (i = intervalo; i < n; i++)
{
j = i - intervalo;
while (j >= 0)
{
k = j + intervalo;
if (a[j] <= a[k])
j = -1; // par de elementos ordenado
else
{
intercambiar(a, j, j+1);
j -= intervalo;
}
}
}
intervalo = intervalo / 2;
}
}
ORDENACIÓN RÁPIDA (QuickSort)
El algoritmo conocido como quicksort (ordenación rápida) recibe su nombre de su autor, Tony Hoare. La idea del algoritmo es simple, se basa en la división en particiones de la lista a ordenar, por ello se puede considerar que aplica la técnica "divide y vencerás". El método es, posiblemente, el más pequeño de código, más rápido, más elegante y más interesante y eficiente de los algoritmos conocidos de ordenación.
Este método se basa en dividir los n elementos de la lista a ordenar en dos partes o particiones separadas por un elemento: una partición izquierda, un elemento central denominado pivote o elemento de partición y una partición derecha. La partición o división se hace de tal forma que todos los elementos de la primera sublista (partición izquierda) sean menores que todos los elementos de la segunda sublista (partición derecha). Las dos sublistas se ordenan entonces independientemente.
Para dividir la lista en particiones (sublistas) se elige uno de los elementos de la lista y se utiliza como pivote o elemento de partición. Si se elige una lista cualquiera con los elementos en orden aleatorio, se puede elegir cualquier elemento de la lista como pivote, por ejemplo, el primer elemento de la lista. Si la lista tiene algún orden parcial que se conoce, se puede tomar otra decisión para escogerlo. Idealmente, el pivote se debe elegir de modo que se divida la lista
exactamente por la mitad de acuerdo al tamaño relativo de las claves. Por ejemplo, si se tiene una lista de enteros de 1 a 10, 5 o 6 serían pivotes ideales, mientras que 1 o 10 serían elecciones “pobres” de pivotes.
Una vez que el pivote ha sido elegido, se utiliza para ordenar el resto de la lista en dos sublistas: una tiene todas las claves menores que el pivote y la otra, todos los elementos (claves) mayores o iguales que el pivote (o al revés). Estas dos listas parciales se ordenan recursivamente
utilizando el mismo algoritmo; es decir, se llama sucesivamente al propio algoritmo quicksort.
La lista final ordenada se consigue concatenando la primera sublista, el pivote y la segunda lista, en ese orden, en una única lista. La primera etapa de quicksort es la división o “particionado” recursivo de la lista hasta que todas las sublistas constan de sólo un elemento
Ejemplo
Se ordena una lista de números enteros aplicando el algoritmo quicksort, como pivote se elige el
primer elemento de la lista.
Algoritmo Quicksort
La primera etapa en el algoritmo de partición es obtener el elemento pivote; una vez que se ha seleccionado, se ha de buscar el sistema para situar en la sublista izquierda todos los elementos menores que el pivote y en la sublista derecha todos los elementos mayores que él. Supongamos que todos los elementos de la lista son distintos, aunque será preciso tener en cuenta los casos en
que existan elementos idénticos. En el Ejemplo 6.3 se elige como pivote el elemento central de la lista actual.
Ejemplo 6.3
Se ordena una lista de números enteros aplicando el algoritmo quicksort, como pivote se elige el
elemento central de la lista.
Lista original: 8 1 4 9 6 3 5 2 7 0
Pivote (elemento central) 6
La etapa 2 requiere mover todos los elementos menores que el pivote a la parte izquierda del array y los elementos mayores a la parte derecha. Para ello, se recorre la lista de izquierda a derecha utilizando un índice i que se inicializa a la posición más baja (inferior) buscando un elemento mayor al pivote. También se recorre la lista de derecha a izquierda buscando un
elemento menor. Para hacer esto se utilizará un índice j inicializado a la posición más alta (superior).
El índice i se detiene en el elemento 8 (mayor que el pivote) y el índice j se detiene en el elemento 0 (menor que el pivote)
El primer problema a resolver en el diseño del algoritmo de quicksort es seleccionar el pivote.
Aunque su posición, en principio, puede ser cualquiera, una de las decisiones más ponderadas es aquella que considera el pivote como el elemento central o próximo al central de la lista. La Figura 6.2 muestra las operaciones del algoritmo para ordenar la lista a[] de n elementos enteros.
Los pasos que sigue el algoritmo quicksort son:
Seleccionar el elemento central de a[] como pivote.
Dividir los elementos restantes en particiones izquierda y derecha, de modo que ningún elemento de la izquierda tenga una clave (valor) mayor que el pivote y que ningún elemento a la derecha tenga una clave menor que la del pivote.
Ordenar la partición izquierda utilizando quicksort recursivamente.
Ordenar la partición derecha utilizando quicksort recursivamente.
La solución es partición izquierda seguida por el pivote y, a continuación, partición derecha.
Figura
Codificación del algoritmo Quicksort
La implementación del algoritmo se realiza de manera recursiva; el método quicksort() con
el argumento array a[] es, simplemente, la interfaz del algoritmo, su única misión es llamar al
método privado del mismo nombre (sobrecargado) quicksort() con los argumentos array a[]
y los índices que la delimitan 0 y a.length-1 (índice inferior y superior).
public static void quicksort(double a[])
{
quicksort(a, 0, a.length-1);
}
Y la codificación del método recursivo:
private static void quicksort(double a[], int primero, int ultimo)
{
int i, j, central;
double pivote;
central = (primero + ultimo)/2;
pivote = a[central];
i = primero;
j = ultimo;
do {
while (a[i] < pivote) i++;
while (a[j] > pivote) j--;
if (i <= j)
{
intercambiar(a, i, j);
i++;
j--;
}
}while (i <= j);
if (primero < j)
quicksort(a, primero, j); // mismo proceso con sublista izqda
if (i < ultimo)
quicksort(a, i, ultimo); // mismo proceso con sublista drcha
REFERENCIAS:
http://puntocomnoesunlenguaje.blogspot.com/2012/07/metodo-de-ordenacion-burbuja.html
Libro Estructuras de Datos -Joyanes Aguilar