Métodos de ordenamiento

Métodos de ordenamiento:

Ordenamiento Burbuja (Bubblesort): 

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. En resumen este es el algoritmo más sencillo probablemente. Ideal para empezar. Consiste en ciclar repetidamente a través de la lista, comparando elementos adyacentes de dos en dos. Si un elemento es mayor que el que está en la siguiente posición se intercambian. ¿Sencillo no? 

Otro ejemplo:

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

 for(j=0; j < n-1; j++){ 

 if(vec[j] > vec[j+1]){ 

 aux=vec[j]; 

 vec[j]=vec[j+1];

 vec[j+1]=aux;

} 

 } 

 }

Método de ordenamiento Quicksort:

Si bien el método de la burbuja era considerado como el mejor método de ordenación simple, el método Quicksort basa su estrategia en la idea intuitiva de que es más fácil ordenar una gran estructura de datos subdividiéndolas en otras más pequeñas introduciendo un orden relativo entre ellas. En otras palabras, si dividimos el array a ordenar en dos subarrays de forma que los elementos del subarray inferior sean más pequeños que los del subarray superior, y aplicamos el método reiteradamente, al final tendremos el array inicial totalmente ordenado. Existen además otros métodos conocidos, el de ordenación por montículo y el de shell. A continuación el algoritmo en Lenguaje C para ordenar un arreglo mediante el método quicksort:

#include <stdlib.h>
#include <stdio.h>

/*funcion para intercambiar los valores de dos elementos*/
void intercambio(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

/*funcion recursiva quicksort para ordenar el arreglo*/
void quicksort(int* izq, int* der) {
    if (der < izq)
        return;
    int pivote = *izq;
    int* ult = der;
    int* pri = izq;

    while (izq < der) {
        while (*izq <= pivote && izq < der+1)
            izq++;
        while (*der > pivote && der > izq-1)
            der--;
        if (izq < der)
            intercambio(izq, der);

    }
    intercambio(pri, der);
    quicksort(pri, der-1);
    quicksort(der+1, ult);
}

int main(void) {
    int i;
    int tam;
    /*definimos el tamaño del arreglo*/
    printf("Ingrese el tamaño del arreglo:\n");
    scanf("%d", &tam);
    int arreglo[tam];

    /*llenamos el arreglo*/
    printf("Ingrese valores para el arreglo:\n");
    for (i = 0; i < tam; i++)
        scanf("%d", &arreglo[i]);
    printf("n");

    /*mostramos el arreglo original*/
    printf("Arreglo Original\n");
    for (i = 0; i < tam; i++)
        printf("%d ", arreglo[i]);
    printf("nn");

    /*hacemos el llamado a la funcion quicksort
      para que ordene el arreglo*/
    quicksort(&arreglo[0], &arreglo[tam-1]);

    /*mostramos el arreglo ordenado*/
    printf("Arreglo Ordenado\n");
    for (i = 0; i < tam; i++)
        printf("%d ", arreglo[i]);
    printf("\n\n");

}

En Lenguaje C hay una función que realiza este método de ordenamiento sin tener que implementarla, la función se encuentra incluida en la librería stdlib.h, se llama qsort, a continuación les dejo un algoritmo usando esta función:

#include <stdlib.h>
#include <stdio.h>

/*funcion para comparar dos elementos del arreglo*/
int comparacion(const void *i, const void *j) {
    return *(int *)i - *(int *)j;
}

int main(void) {
    int i;
    int tam;
 
    /*definimos el tamaño del arreglo*/
    printf("Ingrese el tamaño del arreglo:n");
    scanf("%d", &tam);
    int arreglo[tam];
  
    /*llenamos el arreglo*/
    printf("Ingrese valores para el arreglo:n");
    for (i = 0; i < tam; i++)
        scanf("%d", &arreglo[i]);
    printf("n");
  
    /*mostramos el arreglo original*/
    printf("Arreglo Originaln");
    for (i = 0; i < tam; i++)
        printf("%d ", arreglo[i]);
    printf("nn");

    /*hacemos el llamado a la funcion qsort
      para que ordene el arreglo*/
    qsort(arreglo, tam, sizeof(int), comparacion);

    /*mostramos el arreglo ordenado*/
    printf("Arreglo Ordenadon");
    for (i = 0; i < tam; i++)
        printf("%d ", arreglo[i]);
    printf("nn");
}