Algoritmos de ordenamiento (Burbuja, Seleccion, Insercion)

INTRODUCCION

La ordenación (sort) de datos consiste en la disposición de los mismos de acuerdo a cierta característica.
Una colección de datos clasificados se pueden almacenar en un archivo, vector o tabla, una lista enlazada o árbol.

Clasificación de ordenación:

• Interna.- cuando los datos son almacenados en vectores, listas enlazadas, tablas o arboles.
• Externa.- aquellos que están almacenados en archivos, cintas o dispositivos electrónicos.

Clasificación de ordenación:

• Ascendente.- cuando se tiene de menor a mayor los elementos de la lista, ya sea alfabéticamente o numéricamente.
• Descendente.- cuando se tiene de mayor a menor los elementos de la lista.

 
Distintos metodos de ordenamiento:

• Ordenamiento de burbuja
• Ordenamiento por montículos
• Ordenamiento por inserción
• Ordenamiento por mezcla
• Ordenamiento rápido
• Ordenamiento por selección
• Ordenamiento de Shell

A continuacion les mostrare un video que encontre en youtube y muestra como funciona cada uno de los metodos de ordenamiento que les mostrare mas adelante.

BURBUJA

• Llamado también de intercambio directo o bubble sort.
• Es uno de los mas conocidos.
• Mas sencillo.
• Mas fácil de implementar.

Descripcion

Comparar elementos consecutivos en cada paso a lo largo del arreglo.
Cada vez que se realiza una comparación, los elementos se intercambian entre si en caso de no estar en orden.
Se le llama de burbuja, porque en la ordenación los elementos mas ligeros suben en la lista.

Se pasa varias veces a través del arreglo en forma secuencial.
Cada paso consiste en la comparación de cada elemento con su sucesor, y el intercambio de los dos elementos si no están en el orden correcto.

Una vez acomodado el más grande, prosigue a encontrar  y acomodar el siguiente más grande comparando de nuevo los números desde el inicio del vector, y así sigue hasta ordenar todo los elementos el arreglo.

Procedimiento Bubble Sort

paso 1: [Inicializa i al final de arreglo] For i <- N down to 1 do

paso 2: [Inicia desde la segunda pos.]          For j <- 2 to i do

paso 4: [Si a[j-1] es mayor que el que le sigue]       If a[j-1] < a[j] then

paso 5: [Los intercambia]      Swap(a, j-1, j).

paso 7: [Fin]    End.

Tiempo de ejecución del algoritmo burbuja:

·         Para el mejor caso (un paso) O(n)

·         Peor caso n(n-1)/2

·         Promedio O(n2)

 Programa en C:

void ordenamientoBurbuja(int v[], int util_v) 

{          

         int temp, i, j;            

         for (i = 0; i < util_v -1 ; i++) 

        {                  

                for (j = i + 1; j < util_v ; j++) 

                {                         

                       if (v[i] > v[j]) 

                      {                                

                             temp = v[i];                                 

                             v[i] = v[j];                                 

                             v[j] = temp;                  

                           }                  

                     }                  

              } 

}

Analisis de eficiencia

Hay n-1 comparaciones y pasos en este método. Por lo que el numero total de comparaciones es O(n ).
El numero de intercambios depende del orden original del archivo.

La única característica redentora de este ordenamiento, es que requiere de poco espacio adicional para guardar el valor temporal para el intercambio y de algunas variables enteras simples.
Que es O(n) en el caso de un arreglo ordenado en su totalidad o casi desordenado en su totalidad.

SELECCION

Descripcion

Encontrar el elemento menor ( o mayor) de la lista y colocarlo en la primera posición, a continuación, el elemento siguiente menor (o mayor) se lleva a la segunda posición y así sucesivamente hasta que queda ordenado.
Cualquier ordenamiento por selección puede conceptualizarse como un algoritmo que usa una cola de prioridad descendente.

El método de selección es similar al de burbuja, pero la forma de ordenamiento es diferente, y el primero es casi tan eficiente como el segundo.

Ejemplo:

• El arreglo a ordenar es a = ['a','s','o','r','t','i','n','g','e','x','a','m','p','l','e'].
• Se empieza por recorrer el arreglo hasta encontrar el menor elemento. En este caso el menor elemento es la primera 'a'. De manera que no ocurre ningún cambio. Luego se procede a buscar el siguiente elemento y se encuentra la segunda 'a'.
• Esta se intercambia con el dato que está en la segunda posición, la 's', quedando el arreglo así después de dos recorridos: a = ['a','a','o','r','t','i','n','g','e','x','s','m','p','l','e'].
• El siguiente elemento, el tercero en orden de menor mayor es la primera 'e', la cual se intercambia con lo que está en la tercera posición, o sea, la 'o'. Le sigue la segunda 's', la cual es intercambiada con la 'r'.
• El arreglo ahora se ve de la siguiente manera: a = ['a','a','e','e','t','i','n','g','o','x','s','m','p','l','r'].
• De esta manera se va buscando el elemento que debe ir en la siguiente posición hasta ordenar todo el arreglo.
• El número de comparaciones que realiza este algoritmo es :
• Para el primer elemento se comparan n-1 datos, en general para el elemento i-ésimo se hacen n-i comparaciones, por lo tanto, el total de comparaciones es:
• la sumatoria para i de 1 a n-1 (n-i) = 1/2 n (n-1).

Programa en C:

void ordsel(int * x, int n) 

{    

        int minimo=0,swap;   

        for(i=0 ; i<n-1 ; i++)    

        {       

             minimo=i;       

             for(j=i+1 ; j<n ; j++)

             {        

                    if (x[minimo] > x[j])

                    {               

                       minimo=j;       

                       swap=x[minimo];       

                       x[minimo]=x[i]; 

                       x[i]=swap;    

                    }

             }

        }  

}

Análisis de eficiencia

En el primer paso se efectúan n-1 comparaciones, en el segundo n-2 comparaciones y así sucesivamente. O sea que es del orden de O(n2).
El numero de intercambios es siempre n-1.
Solo se requiere un poco de memoria adicional, para guardar unas variables temporales.

El ordenamiento puede ser categorizado como mas rápido que el de burbuja.
No hay mejora si el arreglo esta ordenado o desordenado.
A pesar de ser fácil de codificar, es improbable que se use este método, solamente cuando son arreglos pequeños.

INSERCION

• Se le llama de Inserción directa.
• Es relativamente sencillo.
• Se basa en intentar construir una lista ordenada. 
• También llamado método de la baraja o naipes.

Descripcion

• Hacer comparaciones, en donde en cada iteración forma una lista ordenada.
• Donde la primera pasada compara los dos primeros elementos y los ordena.
• La siguiente pasada, toma el tercer elemento y lo compara con los dos anteriores, colocando a este en su posición correcta.
• Y así sucesivamente, hasta que queda ordenado. 

Algoritmo (pseudocodigo):

paso 1: [Para cada pos. del arreglo] For i ← 2 to N do

paso 2: [Inicializa v y j] v ← a[i] j ← i.

paso 3: [Compara v con los anteriores] While a[j-1] > v AND j>1 do

paso 4: [Recorre los datos mayores] Set a[j] ← a[j-1],

paso 5: [Decrementa j] set j ← j-1.

paso 5: [Inserta v en su posición] Set a[j] ← v.

paso 6: [Fin] End.

Ejemplo:

• Si el arreglo a ordenar es a = ['a','s','o','r','t','i','n','g','e','x','a','m','p','l','e'], el algoritmo va a recorrer el arreglo de izquierda a derecha. Primero toma el segundo dato 's' y lo asigna a v y i toma el valor de la posición actual de v.
• Luego compara esta 's' con lo que hay en la posición j-1, es decir, con 'a'. Debido a que 's' no es menor que 'a' no sucede nada y avanza i.
• Ahora v toma el valor 'o' y lo compara con 's', como es menor recorre a la 's' a la posición de la 'o'; decrementa j, la cual ahora tiene la posición en dónde estaba la 's'; compara a 'o' con a[j-1] , es decir, con 'a'. Como no es menor que la 'a' sale del for y pone la 'o' en la posición a[j]. El resultado hasta este punto es el arreglo siguiente: a = ['a','o','s','r',....]
• Así se continúa y el resultado final es el arreglo ordenado :
• a = ['a','a','e','e','g','i','l','m','n','o','p','r','s','t','x']

Aunque este algoritmo tiene un mejor orden de complejidad que el de burbuja, es muy ineficiente al compararlo con otros algoritmos como quicksort. Sin embargo, para listas relativamente pequeñas el orden por inserción es una buena elección, no sólo porque puede ser más rápido para cantidades pequeñas de elementos sino particularmente debido a su facilidad de programación.

Programa en C:
 

void insertionSort(int numbers[], int array_size) 

{    

       int i, a, index;      

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

       {       

              index = numbers[i];         

              for (a=i-1;a >= 0 && numbers[a] > index;a--) 

              {          

                     numbers[a + 1] = numbers[a];       

              }      

              numbers[a+2] = index;    

       }

}

Fuentes:
http://es.wikipedia.org/wiki/Algoritmo_de_ordenamiento
Presentacion en PowerPoint "Estructuras: Algoritmos de ordenamiento y busqueda". Autor: M.C. Blanca I. Martnez C.
Investigacion en Word "Algoritmos de busqueda y ordenamiento".