Algoritmos de Ordenamiento

Standard

Hola a todos, el día de hoy vamos a hablar un poco de métodos de ordenamiento. El conocer este tipo de algoritmos ayuda a mejorar el desempeño de algunas de nuestras aplicaciones. Mucho se ha hablado de este tema dada su importancia, ya que, existe un número considerable de algoritmos de ordenamiento, por lo que en este pequeño tutorial vamos a hablar solo de unos pocos. Así que comencemos.

Selection Sort

La idea principal de este algoritmo se basa en encontrar el mínimo o máximo elemento en el arreglo y ponerlo en la posición correspondiente para un arreglo ordenado. Por ejemplo, dado un arreglo de la forma A={7,5,4,2} que se desea ordenar de manera ascendente (de menor a mayor), lo primero es buscar el mínimo elemento en A, que es 2. Una vez encontrado, lo intercambiamos con la posición del primer elemento que se encuentra en A, es decir 7. Después, buscamos el segundo en el resto A y lo ponemos en la segunda posición y así sucesivamente. Ahora vamos a ver su implementación:

1
2
3
4
5
6
7
8
9
10
11
12
13
void selection_sort (int A[ ], int n) {
 int minimum;        
 for(int i = 0; i < n-1 ; i++)  
 {
   minimum = i ;
   for(int j = i+1; j < n ; j++ ) {
     if(A[ j ] < A[ minimum ])  {         
       minimum = j ;
     }
   }
   swap ( A[ minimum ], A[ i ]) ;
 }
}

selectionSort

Para encontrar el mínimo elemento del array tendríamos que hacer n-1 comparaciones. Después de poner el mínimo elemento en su posición el tamaño se reduce n-1 y después n-2 comparaciones para encontrar el mínimo.

Merge Sort

El algoritmo merge sort trabaja con el principio de dividir un arreglo en dos partes, ordenar cada una de las partes y al final hacer el merge de ambos. Dado un arreglo de la forma A={9,7,8,3,2,1}, lo primero es dividirlo en A1={9,7,8} y A2={3,2,1}. Ahora procederemos a dividir otra vez A1 en dos mitades A1_a={9,7}, A1_b={8} otra vez dividimos A1_a   y como ya no se podrá dividir mas entonces hacemos el merge de estos comparándolos. A1_a={7,9}  después hacemos la comparación y el merge con A1_b. Como resultado tendríamos A1={7,8,9}. Hacemos lo mismo para A2 y como resultado tendríamos A2={1,2,3}. Ahora comparamos A1 con A2 y hacemos el merge teniendo como resultado A={1,2,4,7,8,9}.

2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void merge(int A[ ] , int start, int mid, int end) {
   int p = start ,q = mid+1;
   int Arr[end-start+1] , k=0;
   for(int i = start ;i <= end ;i++) {
       if(p > mid)      
          Arr[ k++ ] = A[ q++] ;
      else if ( q > end)   
          Arr[ k++ ] = A[ p++ ];
      else if( A[ p ] < A[ q ])
         Arr[ k++ ] = A[ p++ ];
      else
         Arr[ k++ ] = A[ q++];
  }
  for (int p=0 ; p< k ;p ++) {
      A[ start++ ] = Arr[ p ] ;                          
  }
}

mergeSort

Quick Sort

Este algoritmo está basado en la filosofía de divide y vencerás, además de eliminar la necesidad de tener arreglos auxiliares como el caso de merge sort. La idea principal de este algoritmo es escoger un elemento pivote y particionar el arreglo alrededor de este dejando del lado izquierdo los elementos menores que el elemento pivote y del lado derecho los mayores.

3
4
5
6
7
8
9
10
11
12
13
14
int partition ( int A[],int start ,int end) {
   int i = start + 1;
   int piv = A[start] ;            
   for(int j =start + 1; j <= end ; j++ )  {
         if ( A[ j ] < piv) {
                swap (A[ i ],A [ j ]);
           i += 1;
       }
  }
  swap ( A[ start ] ,A[ i-1 ] ) ;  
  return i-1;                      
}

Una vez que se divide el arreglo en dos mitades teniendo del lado izquierdo los elementos menores al elemento pivote y del lado derecho los mayores,se aplica este paso de manera recursiva.

Ahora esta es la implementación del quick sort:

4
5
6
7
8
9
10
void quick_sort ( int A[ ] ,int start , int end ) {
  if( start < end ) {
        int piv_pos = partition (A,start , end ) ;     
        quick_sort (A,start , piv_pos -1);
        quick_sort ( A,piv_pos +1 , end) ;
  }
}

quickSort

Bueno aquí terminamos este pequeño tutorial espero y les sirva.Saludos.

Leave a Reply

Your email address will not be published. Required fields are marked *