4.6 Ordenaciones simples
Es muy frecuente querer ordenar datos que tenemos en un array. Para conseguirlo, existen varios algoritmos sencillos, que no son especialmente eficientes, pero son fáciles de programar. La falta de eficiencia se refiere a que la mayoría de ellos se basan en dos bucles "for" anidados, de modo que en cada pasada quede ordenado un dato, y se dan tantas pasadas como datos existen, de modo que para un array con 1.000 datos, podrían llegar a tener que hacerse un millón de comparaciones.
Existen ligeras mejoras (por ejemplo, cambiar uno de los "for" por un "while", para no repasar todos los datos si ya estaban parcialmente ordenados), así como métodos claramente más efectivos, pero más difíciles de programar, alguno de los cuales veremos más adelante.
Veremos tres de estos métodos simples de ordenación, primero mirando la apariencia que tiene el algoritmo, y luego juntando los tres en un ejemplo que los pruebe:
Método de burbuja
(Intercambiar cada pareja consecutiva que no esté ordenada)
Para i=1 hasta n-1
Para j=i+1 hasta n
Si A[i] > A[j]
Intercambiar ( A[i], A[j])
(Nota: algunos autores hacen el bucle exterior creciente y otros decreciente, así:)
Para i=n descendiendo hasta 2
Para j=2 hasta i
Si A[j-1] > A[j]
Intercambiar ( A[j-1], A[j])
Selección directa
(En cada pasada busca el menor, y lo intercambia al final de la pasada)
Para i=1 hasta n-1
menor = i
Para j=i+1 hasta n
Si A[j] < A[menor]
menor = j
Si menor <> i
Intercambiar ( A[i], A[menor])
Nota: el símbolo "<>" se suele usar en pseudocódigo para indicar que un dato es distinto de otro, de modo que equivale al "!=" de C#. La penúltima línea en C# saldría a ser algo como "if (menor !=i)"
Inserción directa
(Comparar cada elemento con los anteriores -que ya están ordenados- y desplazarlo hasta su posición correcta).
Para i=2 hasta n
j=i-1
mientras (j>=1) y (A[j] > A[j+1])
Intercambiar ( A[j], A[j+1])
j = j - 1
(Es mejorable, no intercambiando el dato que se mueve con cada elemento, sino sólo al final de cada pasada, pero no entraremos en más detalles).
Un programa de prueba podría ser:
/*---------------------------*/ /* Ejemplo en C# */ /* ordenar.cs */ /* */ /* Ordenaciones simples */ /* */ /* Introduccion a C#, */ /* Nacho Cabanes */ /*---------------------------*/ using System; public class Ordenar { public static void Main() { int[] datos = {5, 3, 14, 20, 8, 9, 1}; int i,j,datoTemporal; int n=7; // Numero de datos // BURBUJA // (Intercambiar cada pareja consecutiva que no esté ordenada) // Para i=1 hasta n-1 // Para j=i+1 hasta n // Si A[i] > A[j] // Intercambiar ( A[i], A[j]) Console.WriteLine("Ordenando mediante burbuja... "); for(i=0; i < n-1; i++) { foreach (int dato in datos) // Muestro datos Console.Write("{0} ",dato); Console.WriteLine(); for(j=i+1; j < n; j++) { if (datos[i] > datos[j]) { datoTemporal = datos[i]; datos[i] = datos[j]; datos[j] = datoTemporal; } } } Console.Write("Ordenado:"); foreach (int dato in datos) // Muestro datos finales Console.Write("{0} ",dato); Console.WriteLine(); // SELECCIÓN DIRECTA: // (En cada pasada busca el menor, y lo intercambia al final de la pasada) // Para i=1 hasta n-1 // menor = i // Para j=i+1 hasta n // Si A[j] < A[menor] // menor = j // Si menor <> i // Intercambiar ( A[i], A[menor]) Console.WriteLine("\nOrdenando mediante selección directa... "); int[] datos2 = {5, 3, 14, 20, 8, 9, 1}; for(i=0; i < n-1; i++) { foreach (int dato in datos2) // Muestro datos Console.Write("{0} ",dato); Console.WriteLine(); int menor = i; for(j=i+1; j < n; j++) if (datos2[j] < datos2[menor]) menor = j; if (i != menor) { datoTemporal = datos2[i]; datos2[i] = datos2[menor]; datos2[menor] = datoTemporal; } } Console.Write("Ordenado:"); foreach (int dato in datos2) // Muestro datos finales Console.Write("{0} ",dato); Console.WriteLine(); // INSERCION DIRECTA: // (Comparar cada elemento con los anteriores -que ya están ordenados- // y desplazarlo hasta su posición correcta). // Para i=2 hasta n // j=i-1 // mientras (j>=1) y (A[j] > A[j+1]) // Intercambiar ( A[j], A[j+1]) // j = j - 1 Console.WriteLine("\nOrdenando mediante inserción directa... "); int[] datos3 = {5, 3, 14, 20, 8, 9, 1}; for(i=1; i < n; i++) { foreach (int dato in datos3) // Muestro datos Console.Write("{0} ",dato); Console.WriteLine(); j = i-1; while ((j>=0) && (datos3[j] > datos3[j+1])) { datoTemporal = datos3[j]; datos3[j] = datos3[j+1]; datos3[j+1] = datoTemporal; j--; } } Console.Write("Ordenado:"); foreach (int dato in datos3) // Muestro datos finales Console.Write("{0} ",dato); Console.WriteLine(); } }
Y su resultado sería:
Ordenando mediante burbuja...
5 3 14 20 8 9 1
1 5 14 20 8 9 3
1 3 14 20 8 9 5
1 3 5 20 14 9 8
1 3 5 8 20 14 9
1 3 5 8 9 20 14
Ordenado:1 3 5 8 9 14 20
Ordenando mediante selección directa...
5 3 14 20 8 9 1
1 3 14 20 8 9 5
1 3 14 20 8 9 5
1 3 5 20 8 9 14
1 3 5 8 20 9 14
1 3 5 8 9 20 14
Ordenado:1 3 5 8 9 14 20
Ordenando mediante inserción directa...
5 3 14 20 8 9 1
3 5 14 20 8 9 1
3 5 14 20 8 9 1
3 5 14 20 8 9 1
3 5 8 14 20 9 1
3 5 8 9 14 20 1
Ordenado:1 3 5 8 9 14 20