5.7 Ordenaciones simples

  Curso: Fundamentos de programación en C, por Nacho Cabanes

5.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 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 1
    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])

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).

 

Ejercicios propuestos:

• Un programa que cree un array de 7 números enteros y lo ordene con cada uno de estos tres métodos, mostrando el resultado de los pasos intermedios.

 

 

Actualizado el: 24-07-2014 15:39