Métodos de ordenamiento.

La ordenación o clasificación es el proceso de organizar datos en algún orden o secuencia específica, tal como creciente o decreciente, para datos numéricos, o alfabéticos, para datos de caracteres. Los métodos de ordenación más directos son los que se realizan en el espacio ocupado por el array. Los más populares son:

Método de Intercambio o de Burbuja:

Se basa en el principio de comparar pares de elementos adyacentes e intercambiarlos entre si hasta que estén todos ordenados. Supongamos que se desea clasificar en orden ascendente el vector o lista:

9, 8, 0, 2, 5, 1, 3, 2, 9

A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8]

Los pasos a dar son:

- CompararA[1] yA[2] si están en orden, se mantienen como están, en caso contrario se intercambian entre si.

- A continuación se comparan los elementos 2 y 3; de nuevo se intercambian si es necesario.

- El proceso continua hasta que cada elemento del vector ha sido comparado con sus elementos adyacentes y se han realizado los intercambios necesarios.

Este video muestra de manera simple el ordenamiento de burbuja:

Ejemplo Práctico

    /*Ordenamiento Burbuja */
 
    #include <stdio.h> 
    #include <conio.h> 
    #define TAM 9

    int main() 
    { 
        int a[TAM] = { 9, 8, 0, 2, 5, 1, 3, 2, 9};
        int i, pasada, aux;

        printf("Datos en el orden inicial:\n\n");
            for(i=0;i<=TAM-1;i++)
                printf("%4d",a[i]);
        for (pasada=1;pasada<=TAM-1;pasada++) /*pasadas*/
            for (i=0;i<=TAM-2;i++)
                if (a[i]>a[i+1]) /*comparación */
                {
                    /*intercambio*/
                    aux=a[i]; 
                    a[i] = a[i+1]; 
                    a[i+1] = aux;
                }
        printf( "\n\nDatos ordenados en sentido ascendente:\n\n" );
            for (i=0;i<=TAM-1;i++ )
                printf("%4d", a[i]);
        printf("\n"); 
        getch(); 
    return 0; 
    }

Ordenamiento por inserción (Insertion Sort).

Consiste en insertar un elemento en el vector en una parte ya ordenada de este vector y comenzar de nuevo con los elementos restantes. Por ser utilizado generalmente por los jugadores de cartas se le conoce también por el método de la baraja. Por ejemplo, supóngase que se tiene la lista desordenada;

5 14 24 39 43 65 84 45

Para insertar el elemento 45, habrá que insertar entre 43 y 65, lo que supone desplazar a la derecha todos aquellos números de valor superior a 45, es decir, saltar sobre 65 y 84.

5 14 24 39 43 65 84 45

El método se basa en comparaciones y desplazamientos sucesivos. El algoritmo de clasificaciones de un vector X para N elementos se realiza con un recorrido de todo el vector y la inserción del elemento correspondiente en el lugar adecuado. El recorrido se realiza desde el segundo elemento al n-ésimo.

Veamos el siguiente ejemplo.

Ejemplo Práctico.

#include <stdio.h> 
int arreglo[10] = {3,10,1,8,15,5,12,6,5,4}; /*Declaracion e inicialización 
del arreglo. */
        

/*imprimearreglo - Funcion que muestra por pantalla 
el contenido de un arreglo.*/ 
void imprimearreglo() { 
    int i; for (i=0;i<10;i++) 
        printf("Elemento %d: %d \n",i,arreglo[i]); 
} 
        
void main() /*Funcion Principal del Programa*/ 
{ 
    int i,j,k;
    imprimearreglo(); 
    for (i=1; i<10; i++) { 
        j=i; 
            while (j>=0 && arreglo[j]<arreglo[j-1]) { 
                k=arreglo[j]; 
                arreglo[j]=arreglo[j-1]; 
                arreglo[j-1]=k; 
                j--; 
            } 
    } 
    printf("\n\nArreglo ordenado \n\n"); 
    imprimearreglo(); 
}

Ordenamiento Rápido (Quicksort).

El ordenamiento rápido (quicksort en inglés) es un algoritmo 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. Esta es la técnica de ordenamiento más rápida conocida. El algoritmo fundamental es el siguiente:

Veamos el siguiente ejemplo.

Puedes ver otra explicación, esta vez con voz Aquí

Pseudocódigo QuickSort:

Nombre Función: OrdRap
Parámetros: 
    lista a ordenar (lista) 
    índice inferior (inf) 
    índice superior (sup)

    // Inicialización de variables
    1. elem_div = lista[sup];
    2. i = inf - 1; 
    3. j = sup; 
    4. cont = 1;

    // Verificamos que no se crucen los límites 
    5. if (inf >= sup) 
    6. retornar;

    // Clasificamos la sublista 
    7. while (cont) 
    8. while (lista[++i] < elem_div); 
    9. while (lista[--j] > elem_div); 
    10. if (i < j) 
    11. temp = lista[i]; 
    12. lista[i] = lista[j]; 
    13. lista[j] = temp; 
    14. else 
    15. cont = 0;

    // Copiamos el elemento de división 
    // en su posición final 
    16. temp = lista[i]; 
    17. lista[i] = lista[sup]; 
    18. lista[sup] = temp;

    // Aplicamos la función 
    19. OrdRap (lista, inf, i - 1); 
    20. OrdRap (lista, i + 1, sup);

Ejemplo de Implementación de Quicksort en C

void SortArray (int array[],int first,int last)
{
    int i,j,p,t;

    // i se hace igual al índice del primer elemento
    i= first;
    // y j igual al índice del último elemento
    j= last;
    // p se hace igual al elemento pivote del arreglo
    p= array[(first+last)/2];

    do { 
        // se hace la partición del arreglo
        while (array[i]<p) i++; 
        while (p<array[j]) j--;
        if (i<=j) {

                // se intercambian los elementos i-esimo y j-esimo del arreglo
                t= array[i]; 
                array[i]= array[j]; 
                array[j]= t; 
                i++; j--;
            }
    } while (i<=j); 
    if (first<j) SortArray(array,first,j); 
    if (i<last) SortArray(array,i,last); 
}

Seguir a paginadeC en Twitter Foro de Página de C ¡CSS Válido!