Algoritmos de Ordenamiento

Algoritmos de ordenamiento

Los algoritmos de ordenamiento, como su nombre indica se utilizan para ordenar informacion a base de un criterio de ordenamiento.
A lo largo del tiempo se han desarrollado muchas tecnicas de ordenamiento cada una con caracteristicas propias y con ventajas y desventajas con respecto a otras.


Ordenamiento burbuja (Bubble sort)

El ordenamiento tipo burbuja se podria decir que es el mas simple, funciona revisando cada elemento con el siguiente e intercambiandolos si estan en el orden incorrecto, para esto es necesario recorrer varias veces la lista de tal manera que no queden mas intercambios.

 Este algoritmo es muy sencillo y logra su cometido, pero consume mucho tiempo de la computadora ya que requiere muchas lecturas y escrituras en memoria.

Ejemplo en c :

#include<stdio.h>
#include<stdlib.h>
int main(){
    int vector[10] = {8,7,6,19,3,5,11,15,1,2};
    int i,j,aux;
    printf("\n\nVector sin ordenar : ");
    for(i=0;i<10;i++){
        printf("%d ",vector[i]);
    }
    for(i=0;i<10;i++){
        for(j=0;j<10;j++){
            if(vector[j]>vector[j+1]){
                aux = vector[j];
                vector[j]=vector[j+1];
                vector[j+1]=aux;
            }
        }
    }
    printf("\n\nVector ordenado : ");
    for(i=0;i<10;i++){
        printf("%d ",vector[i]);
    }
    printf("\n\n");
    system("pause");
    return 0;
}



Ordenamiento por seleccion directa

El metodo de ordenamiento por seleccion directa consiste en hacer varias recorridos por la lista y encontrar el dato con menor valor y ubicarlo en la posicion equivalente, los siguientes recorridos se hacen por la parte no ordenada de la lista.


La ventaja de este algoritmo es que funciona muy bien en listas pequeñas, pero pierde eficiencia cuando se trata de listas ms grandes ya requiere una cantidad de n al cuadrado operaciones.

Ejemplo en c :

#include<stdio.h>
#include<stdlib.h>
int main(){
    int vect[10] = {9,5,13,2,8,16,21,12,17,4};
    int i,j,aux,min;
   
    printf("\n\nVector sin ordenar : ");
    for(i=0;i<10;i++){
        printf("%d ",vect[i]);
    }
    for(i=0;i<10;i++){
        min = i;
        for(j=i+1;j<10;j++){
            if(vect[j]<vect[min]){
                min = j;
            }
        }
        aux = vect[i];
        vect[i]=vect[min];
        vect[min]=aux;
    }
        printf("\n\nVector ordenado : ");
    for(i=0;i<10;i++){
        printf("%d ",vect[i]);
    }
    printf("\n\n");
    system("pause");
    return 0;
}

Ordenamiento por insercion

El metodo por insercion consta de tomar uno por uno los elementos de la lista empezando con el segundo y recorrerlo con respecto a los ya ordenados e intercambiandolos si estan en la posicion incorrecta.





Este metodo es de una facil implementacion y ocupa el minimo espacio requerido en memoria,
pero es lento y realiza muchas comparaciones.

Ejemplo en c :

#include<stdio.h>
#include<stdlib.h>
int main(){
    int vect[10]={7,9,4,14,12,5,1,17,6,16};
    int i,pos,aux;
    printf("\n\nVector desordenado : ");
    for(i=0;i<10;i++){
        printf("%d ",vect[i]);
    }
    for(i=0;i<10;i++){
        pos = i;
        aux = vect[i];
        while((pos>0) && (aux < vect[pos-1])){
            vect[pos] = vect[pos-1];
            pos --;
        }
        vect[pos] = aux;
    }
    printf("\n\nVector ordenado : ");
    for(i=0;i<10;i++){
        printf("%d ",vect[i]);
    }
    printf("\n\n");
    system("pause");
    return 0;
}

Ordenamiento shell

Creado por Donald Shell, este metodo funciona parecido al ordenamiento burbuja, solo que en vez de comparar elementos adyacentes en la lista hace una segmentacion que comienza desde un valor alto y que disminuyen hasta llegar a 1.


Este metodo no requiere espacio de memoria adiccional y es mas rapido que los anteriores, es algo complicado de implementar, realiza muchas comparaciones  e intecambios y es mas lento que otros metodos de misma complejidad.
Ejemplo en c:
#include<stdio.h>
#include<stdlib.h>
#define N 16
int main(){
    int vect[N]={10,16,18,3,8,17,7,9,1,21,20,6,18,2,12,4};
    int i,j,k,aux,intermedio;
    printf("\nVector Desordenado : ");
    for(i=0;i<N;i++){
        printf("%d ",vect[i]);
    }
    intermedio = N/2;
    while(intermedio>0){
        for(i=intermedio;i<N;i++){
                j = i - intermedio;
            while(j>=0){
                k = intermedio + j;
            if(vect[k]>=vect[j]){
                j --;
                }else{
                aux = vect[k];
                vect[k] = vect[j];
                vect[j] = aux;
                j = j - intermedio;
                }
            }
        }
        intermedio = intermedio/2;
    }
    printf("\n\nVector Ordenado : ");   
    for(i=0;i<N;i++){
        printf("%d ",vect[i]);
    }
    printf("\n\n");
    system("pause");
    return 0;
}
Ordenamiento por mezcla (Merge sort)

Este metodo usa la tecnica "divide y venceras" , la estrategia de esta es partir de una lista desordenada y dividirla en 2 sublistas luego se divide nuevamente hasta tener sublistas con 1 o 0 elementos alli la sublista ya va a estar ordenada y luego se mezcla con la sublista de al lado y ordenarlas,asi repitiendo hasta llegar al caso base.






Este metodo de ordenamiento es estable si se implementa correctamente, cuando la lista es de indice bajo es estable, caso contrario gasta el doble de espacio que los datos inicialmente, una desventaja es que esta definido recursivamente y implementarlo no recursivamente tendra que emplear una pila y requerir espacio adicional de memoria

Ejemplo en C :
#include<stdio.h>
#include<stdlib.h>
#define N 10

void mezcla(int array[],int tam);
void ordenar(int array1[],int n1,int array2[],int n2,int array3[]);

int main(){
    int vect[N]={8,15,9,12,1,19,5,7,14,13};
    int i;
    printf("\nVector desordenado : ");
    for(i=0;i<N;i++){
        printf("%d ",vect[i]);
    }
   
    mezcla(vect,N);
   
    printf("\n\nVector ordenado : ");
    for(i=0;i<N;i++){
        printf("%d ",vect[i]);
    }
    printf("\n\n");
    system("pause");
    return 0;
}

void mezcla(int array[],int tam){
    int *array1,*array2,n1,n2,i,j;
    if(tam>1){
        if(tam%2==0){
           n1=tam/2;
          n2=n1;
        }else{
        n1=tam/2;
        n2=n1+1;
        }
        array1=(int *) malloc(sizeof(int)*n1);
        array2=(int *) malloc(sizeof(int)*n2);
        for(i=0;i<n1;i++){
            array1[i] = array[i];
        }
        for(j=0;j<n2;j++,i++){
            array2[j] = array[i];
        }
        mezcla(array1,n1);
        mezcla(array2,n2);
        ordenar(array1,n1,array2,n2,array);
        free(array1);
        free(array2);
    }
}
void ordenar(int array1[],int n1,int array2[],int n2,int array3[]){
    int x1=0,x2=0,x3=0;
    while((x1<n1)&&(x2<n2)){
        if(array1[x1]<array2[x2]){
                array3[x3] = array1[x1];
                x1 ++;
        }else{
            array3[x3] = array2[x2];
            x2 ++;
        }
        x3 ++;
    }
    while (x1<n1) {
        array3[x3] = array1[x1];
        x1 ++;
        x3 ++;
    }
    while (x2<n2) {
        array3[x3] = array2[x2];
        x2 ++;
        x3 ++;
    }
}

Ordenamiento rapido (Quicksort)

Esta tecnica, al igual que el ordenamiento por mezcla utiliza el metodo "divide y conquista", pero el quicksort para empezar a dividir elige un elemento de la lista (puede ser cualquiera) y lo llamara pivot, este pivot se utilizara para comparar con los demas elementos de tal manera que los elementos menores al pivot queden a la izquierda y los mayores a la derecha, una vez dividida la lista, se repite el proceso recursivamente hasta ordenar la lista, la eficiencia del algoritmo se basa en la eleccion del pivot, en el mejor de los casos el pivot es un elemento del centro de la lista y en el peor es un elemento de uno de los extremos.

Este metodo es el mas rapido, poco estable, la diferencia entre el mejor y el peor de los casos es muy notable, implementacion mas complicada, pese a esto debido a su eficiencia es el mas utilizado.

Ejemplo en C :
 #include<stdio.h>
#include<stdlib.h>
#define N 20
void quicksort(int vect[],int izq,int der);
void intercambio(int array[],int a,int b);
void quick(int array[],int tam);
int main(){
    int vect[N]={20,18,9,31,84,56,8,19,41,5,6,72,98,13,15,29,1,68,54,12};
    int i;
    printf("\nVector desordenado : ");
    for(i=0;i<N;i++){
        printf("%d ",vect[i]);
    }

    quick(vect,N);
  
    printf("\n\nVector ordenado : ");
    for(i=0;i<N;i++){
        printf("%d ",vect[i]);
    }
    printf("\n\n");
    system("pause");
    return 0;
}
void quick(int vect[],int tam){
    quicksort(vect,0,tam);
}
void quicksort(int array[],int min,int max){
    int i,j,x,aux;
    i=min;
    j=max;
    x=array[(min+max)/2];
    while(i<=j){
        while((array[i]<x)&&(j<=max)){
            i ++;
        }
        while((x<array[j])&&(j >min)){
            j --;
        }
        if(i<=j){
            aux=array[i];
            array[i]=array[j];
            array[j]=aux;
            i ++;
            j --;
        }
    }
    if(min<j){
        quicksort(array,min,j);
    }
    if(i<max){
        quicksort(array,i,max);
    }
}







Muchas gracias por su atencion, disculpen si hay algun error y si lo hay comentenlo asi lo arreglamos. Todo este post fue una recopilacion de distintas paginas de internet , la mayoria de gifs y info se obtuvo de esta pagina : http://www.xybernetics.com/techtalk/SortingAlgorithmsExplained/SortingAlgorithmsExplained.html