AnteriorPosterior

4.7. Ordenaciones simples

  Curso: Programación en C# (2015), por Nacho Cabanes

4.7. 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 único dato, y habrá que dar dan tantas pasadas como datos existen. Por tanto, para un array con 1.000 datos, podrían llegar ser necesarias un millón de comparaciones (1.000 x 1.000).

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 comentaremos 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 métodos 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_04_07a.cs
// Ordenaciones simples
// Introducción a C#, por Nacho Cabanes
 
using System;
 
public class Ejemplo_04_07a
{
 
    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:")#41;;
 
        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
 

Ejercicios propuestos:

Ejercicio propuesto 4.7.1: Un programa que pida al usuario 6 números en coma flotante y los muestre ordenados de menor a mayor. Escoge el método de ordenación que prefieras.
Ejercicio propuesto 4.7.2: Un programa que pida al usuario 5 nombres y los muestre ordenados alfabéticamente (recuerda que para comparar cadenas no podrás usar el símbolo ">", sino "CompareTo").
Ejercicio propuesto 4.7.3: Un programa que pida al usuario varios números, los vaya añadiendo a un array, mantenga el array ordenado continuamente y muestre el resultado tras añadir cada nuevo dato (todos los datos se mostrarán en la misma línea, separados por espacios en blanco). Terminará cuando el usuario teclee "fin".
Ejercicio propuesto 4.7.4: Amplia el ejercicio anterior, para añadir una segunda fase en la que el usuario pueda "preguntar" si un cierto valor está en el array. Como el array está ordenado, la búsqueda no se hará hasta el final de los datos, sino hasta que se encuentre el dato buscado o un un dato mayor que él.

Una vez que los datos están ordenados, podemos buscar uno concreto dentro de ellos empleando la búsqueda binaria: se comienza por el punto central; si el valor buscado es mayor que el del punto central, se busca esta vez sólo en la mitad superior (o en la inferior), y así sucesivamente, de modo que cada vez se busca entre un conjunto de datos que tiene la mitad de tamaño que el anterior. Esto puede suponer una enorme ganancia en velocidad: si tenemos 1.000 datos, una búsqueda lineal hará 500 comparaciones como media, mientras que una búsqueda lineal hará 10 comparaciones o menos.

// Ejemplo_04_07b.cs
// Búsqueda binaria
// Introducción a C#, por Nacho Cabanes
 
using System;
 
public class Ejemplo_04_07b
{
 
    public static void Main()
    {
        const int n = 1000;
        int[] datos = new int[n];
        int i,j,datoTemporal;
 
        // Primero generamos datos al azar
        Console.Write("Generando... ");
        Random r = new Random();
        for(i=0; i < n; i++)
            datos[i] = r.Next(1, n*2);
 
        // Luego los ordenamos mediante burbuja
        Console.Write("Ordenando... ");
        for(i=0; i < n-1; i++)
        {
            for(j=i+1; j < n; j++)
            {                 
                 if (datos[i] > datos[j])
                 {
                    datoTemporal = datos[i];
                    datos[i] = datos[j];
                    datos[j] = datoTemporal;
                 }
            }
        }
 
        foreach (int dato in datos)
            Console.Write("{0} ",dato);
        Console.WriteLine();
 
        int valorBuscado = 1001;
        Console.WriteLine("Buscando si aparece {0}...", valorBuscado);
 
        int limiteInferior = 0;
        int limiteSuperior = 999;
        bool terminado = false;
 
        while(! terminado)
        {
            int puntoMedio = limiteInferior+(limiteSuperior-limiteInferior) / 2;
            // Aviso de dónde buscamos
            Console.WriteLine("Buscando entre pos {0} y {1}, valores {2} y {3},"+
                " centro {4}:{5}",
                limiteInferior, limiteSuperior,
                datos[limiteInferior], datos[limiteSuperior],
                puntoMedio, datos[puntoMedio]);
            // Compruebo si hemos acertado
            if (datos[puntoMedio] == valorBuscado)
            {
                Console.WriteLine("Encontrado!");
                terminado = true;
            }
            else if (limiteInferior == limiteSuperior-1)
            {
                Console.WriteLine("No encontrado");
                terminado = true;
            }
            // Si no hemos terminado, debemos seguir buscando en una mitad
            if ( datos[puntoMedio] < valorBuscado )
                limiteInferior = puntoMedio;
            else
                limiteSuperior = puntoMedio;
        }
 
    }
}
 

Ejercicios propuestos:

Ejercicio propuesto 4.7.5: Realizar una variante del ejercicio 4.7.4, que en vez de hacer una búsqueda lineal (desde el principio), use "búsqueda binaria": se comenzará a comparar con el punto medio del array; si nuestro dato es menor, se vuelve a probar en el punto medio de la mitad inferior del array, y así sucesivamente.

Actualizado el: 04-12-2014 10:27

AnteriorPosterior