Algoritmos de Ordenamiento

De Departamento de Informatica
Saltar a: navegación, buscar

Estos algoritmos permiten ordenar una colección de valores que poseen una relación de orden (relación transitiva). Para saber que algoritmo se debe usar en cada situaciones, son factores importantes el tiempo de ejecución de un algoritmo, asi como la memoria que este usa. Se explicarán 6 algoritmos: el Bubble sort, Selection sort, Insertion sort, Shell sort, Quick sort, Heap sort.

Contenido

Bubble sort

La Ordenación de burbuja (Bubble Sort en inglés) es un sencillo algoritmo de ordenamiento. Funciona revisando cada elemento de la lista que va a ser ordenada con el siguiente, intercambiándolos de posición si están en el orden equivocado. Es necesario revisar varias veces toda la lista hasta que no se necesiten más intercambios, lo cual significa que la lista está ordenada. Este algoritmo obtiene su nombre de la forma con la que suben por la lista los elementos durante los intercambios, como si fueran pequeñas "burbujas". También es conocido como el método del intercambio directo. Dado que solo usa comparaciones para operar elementos, se lo considera un algoritmo de comparación, siendo el más sencillo de implementar.

Este algoritmo es esencialmente un algoritmo de fuerza bruta lógica.

PseudoCódigo

Comenzando desde el inicio del vector, se compara cada par de elementos adyacentes. Si ambos no están ordenados (el segundo es menor que el primero), se intercambian sus posiciones. En cada iteración, un elemento menos necesita ser evaluados (el último), ya que no hay más elementos a su derecha que necesiten ser comparados, puesto que ya están ordenados.

for (i=1; i<TAM; i++)
    for (j=0 ; j<TAM - i; j++)
         if (lista[j] > lista[j+1])
              temp = lista[j];
              lista[j] = lista[j+1];
              lista[j+1] = temp;

Ejemplo

Bubble-sort.gif

Selection sort

Su funcionamiento es el siguiente:

  • Buscar el mínimo elemento de la lista
  • Intercambiarlo con el primero
  • Buscar el siguiente mínimo en el resto de la lista
  • Intercambiarlo con el segundo

Y en general:

  • Buscar el mínimo elemento entre una posición i y el final de la lista
  • Intercambiar el mínimo con el elemento de la posición i

PseudoCódigo

De esta manera se puede escribir el siguiente pseudocódigo para ordenar una lista de n elementos indexados desde el 1:

para i=1 hasta n-1
    mínimo = i;
    para j=i+1 hasta n
        si lista[j] < lista[mínimo] entonces
            mínimo = j /* (!) */
        fin si
    fin para
    intercambiar(lista[i], lista[mínimo])
fin para

Ejemplo

Selection-Sort.gif

Insertion sort

El algoritmo por inserción (Insertion Sort) consiste en insertar cada elemento (partiendo por el segundo) en la posición correcta, desplazando cada elemento que sea mayor a su izquierda, hasta encontrar un elemento que sea menor, insertando el elemento a la derecha de este.

PseudoCódigo

for (i=1; i<TAM; i++)

   temp = lista[i];
   j = i - 1;
   while ( (lista[j] > temp) && (j >= 0) )
       lista[j+1] = lista[j];
        j--;
   lista[j+1] = temp;

Ejemplo

Insertion-sort.gif

Shell sort

El ordenamiento Shell (Shell sort en inglés) es un algoritmo de ordenamiento. El método se denomina Shell en honor de su inventor Donald Shell. Su implementación original, requiere O(n2) comparaciones e intercambios en el peor caso. Un cambio menor presentado en el libro de V. Pratt produce una implementación con un rendimiento de O(n log2 n) en el peor caso. Esto es mejor que las O(n2) comparaciones requeridas por algoritmos simples pero peor que el óptimo O(n log n). Aunque es fácil desarrollar un sentido intuitivo de cómo funciona este algoritmo, es muy difícil analizar su tiempo de ejecución.

El Shell sort es una generalización del ordenamiento por inserción, teniendo en cuenta dos observaciones:

  1. El ordenamiento por inserción es eficiente si la entrada está "casi ordenada".
  2. El ordenamiento por inserción es ineficiente, en general, porque mueve los valores sólo una posición cada vez.

El algoritmo Shell sort mejora el ordenamiento por inserción comparando elementos separados por un espacio de varias posiciones. Esto permite que un elemento haga "pasos más grandes" hacia su posición esperada. Los pasos múltiples sobre los datos se hacen con tamaños de espacio cada vez más pequeños. El último paso del Shell sort es un simple ordenamiento por inserción, pero para entonces, ya está garantizado que los datos del vector están casi ordenados.

Ejemplo

Considere un valor pequeño que está inicialmente almacenado en el final del vector que se quiere ordenar de forma ascendente. Usando un ordenamiento O(n2) como el ordenamiento de burbuja o el ordenamiento por inserción, tomará aproximadamente n comparaciones e intercambios para mover este valor hacia el otro extremo del vector. El Shell sort primero mueve los valores usando tamaños de espacio gigantes, de manera que un valor pequeño se moverá bastantes posiciones hacia su posición final, con sólo unas pocas comparaciones e intercambios.

Uno puede visualizar el algoritmo Shell sort de la siguiente manera: coloque la lista en una tabla y ordene las columnas (usando un ordenamiento por inserción). Repita este proceso, cada vez con un número menor de columnas más largas. Al final, la tabla tiene sólo una columna. Mientras que transformar la lista en una tabla hace más fácil visualizarlo, el algoritmo propiamente hace su ordenamiento en contexto (incrementando el índice por el tamaño de paso, esto es usando i += tamaño_de_paso en vez de i++).

Por ejemplo, considere una lista de números como [ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]. Si comenzamos con un tamaño de paso de 5, podríamos visualizar esto dividiendo la lista de números en una tabla con 5 columnas. Esto quedaría así:

13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10

Entonces ordenamos cada columna, lo que nos da

10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45

Cuando lo leemos de nuevo como una única lista de números, obtenemos [ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]. Aquí, el 10 que estaba en el extremo final, se ha movido hasta el extremo inicial. Esta lista es entonces de nuevo ordenada usando un ordenamiento con un espacio de 3 posiciones, y después un ordenamiento con un espacio de 1 posición (ordenamiento por inserción simple).

Quick sort

El ordenamiento rápido (quicksort en inglés) es un algoritmo creado por el científico británico en computación C. A. R. Hoare, basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n.

Descripción del algoritmo

El algoritmo trabaja de la siguiente forma:

  • Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote.
  • Resituar los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden todos los menores que él, y al otro los mayores. Los elementos iguales al pivote pueden ser colocados tanto a su derecha como a su izquierda, dependiendo de la implementación deseada. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada.
  • La lista queda separada en dos sublistas, una formada por los elementos a la izquierda del pivote, y otra por los elementos a su derecha.
  • Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados.

Como se puede suponer, la eficiencia del algoritmo depende de la posición en la que termine el pivote elegido.

  • En el mejor caso, el pivote termina en el centro de la lista, dividiéndola en dos sublistas de igual tamaño. En este caso, el orden de complejidad del algoritmo es O(n·log n).
  • En el peor caso, el pivote termina en un extremo de la lista. El orden de complejidad del algoritmo es entonces de O(n²). El peor caso dependerá de la implementación del algoritmo, aunque habitualmente ocurre en listas que se encuentran ordenadas, o casi ordenadas. Pero principalmente depende del pivote, si por ejemplo el algoritmo implementado toma como pivote siempre el primer elemento del array, y el array que le pasamos está ordenado, siempre va a generar a su izquierda un array vacío, lo que es ineficiente.


  • En el caso promedio, el orden es O(n·log n).

No es extraño, pues, que la mayoría de optimizaciones que se aplican al algoritmo se centren en la elección del pivote.

Ejemplo

En el siguiente ejemplo se marcan el pivote y los índices i y j con las letras p, i y j respectivamente.

Comenzamos con la lista completa. El elemento pivote será el 4:

5 - 3 - 7 - 6 - 2 - 1 - 4
                        p

Comparamos con el 5 por la izquierda y el 1 por la derecha.

5 - 3 - 7 - 6 - 2 - 1 - 4 
i                   j   p

5 es mayor que 4 y 1 es menor. Intercambiamos:

1 - 3 - 7 - 6 - 2 - 5 - 4
i                   j   p 

Avanzamos por la izquierda y la derecha:

1 - 3 - 7 - 6 - 2 - 5 - 4
    i           j       p 

3 es menor que 4: avanzamos por la izquierda. 2 es menor que 4: nos mantenemos ahí.

1 - 3 - 7 - 6 - 2 - 5 - 4
        i       j       p 

7 es mayor que 4 y 2 es menor: intercambiamos.

1 - 3 - 2 - 6 - 7 - 5 - 4
        i       j       p 

Avanzamos por ambos lados:

1 - 3 - 2 - 6 - 7 - 5 - 4
           iyj          p 

En este momento termina el ciclo principal, porque los índices se cruzaron. Ahora intercambiamos lista[i] con lista[sup] (pasos 16-18):

1 - 3 - 2 - 4 - 7 - 5 - 6
            p 

Aplicamos recursivamente a la sublista de la izquierda (índices 0 - 2). Tenemos lo siguiente:

1 - 3 - 2 

1 es menor que 2: avanzamos por la izquierda. 3 es mayor: avanzamos por la derecha. Como se intercambiaron los índices termina el ciclo. Se intercambia lista[i] con lista[sup]:

1 - 2 - 3 

El mismo procedimiento se aplicará a la otra sublista. Al finalizar y unir todas las sublistas queda la lista inicial ordenada en forma ascendente.

1 - 2 - 3 - 4 - 5 - 6 - 7

Heap sort

El ordenamiento por montículo (Heap Sort), consiste en:

  • Construir un montículo
  • Eliminar la raíz del montículo de manera iterativa

Montículo

Un montículo o heap es un tipo de árbol binario, el cual cumple con que cada nodo es mayor que cualquiera de sus hijos. Por ello, este tipo de árboles binarios tiene el nodo de mayor valor en su raíz. Es por ello que se usa en este tipo de ordenamiento, pues siempre se tiene el mayor elemento en la raíz del árbol.

Heap.png

Descripción del Algoritmo

El algoritmo es de tipo iterativo. Se puede describir de la siguiente forma:

  1. Construir un montículo con los elementos del arreglo A[1],A[2]...A[n]
  2. Reinsertar los elementos del montículo en el arreglo, en orden por nivel (De esta forma, siempre A[1] corresponderá al mayor)
  3. Intercambiar A[1] con A[n], tanto en el montículo como en el arreglo.
  4. Eliminar la ex-raíz del montículo de este, y reordenar para tener la condición de montículo nuevamente, intercambiando los elementos tanto en el arreglo como en el montículo.
  5. Intercambiar A[1] con A[n-1] (Pues A[n] quedó en su posición final), y volver a 4.

Esta es la idea general del algoritmo, tal como se muestra en el ejemplo. Normalmente, al implementar este algoritmo, se usa la misma estructura para el montículo y el arreglo, simplemente haciendo las conexiones del árbol usando punteros en la misma estructura lineal.

Ejemplo

Heapsort.gif

Herramientas personales
Espacios de nombres
Variantes
Acciones
Navegación
Herramientas