Ordenamiento por inserción

Origen

El algoritmo Quicksort fue desarrollado en el año 1960 por Charles Antony Richard Hoare mientras se encontraba en la Unión Soviética, en la Universidad Estatal de Moscú.

En ese entonces, Hoare trabajó en un proyecto de traducción automática para el Laboratorio Nacional de Física (Reino Unido). Desarrolló el algoritmo para poder ordenar las palabras a ser traducidas, para volverlas más fácil de coincidir con un diccionario ya ordenado de ruso a inglés.

 ¿Que es el Metodo de Inserción?

El algoritmo de ordenamiento por inserción es un algoritmo de facil aplicación que permite el ordenamiento de una lista.
Su funcionamiento consiste en el recorrido por la lista seleccionando en cada iteración un valor como clave y compararlo con el resto insertándolo en el lugar correspondiente.

Ventajas	Desventajas
Fácil implementación	Lento
Requerimientos mínimos de memoria.	Realiza numerosas comparaciones.

 

Pasos para realizar ordenamiento por algoritmo Quick Sort

• Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote.

• Resituar los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden todos los menores que él, y al otro los mayores. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada.

• La lista queda separada en dos sublistas, una formada por los elementos a la izquierda del pivote, y otra por los elementos a su derecha.

• Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados. Como se puede suponer, la eficiencia del algoritmo depende de la posición en la que termine el pivote elegido.

    

   Codigo en C 

  El ordenamiento por partición (Quick Sort) se puede definir en una forma más conveniente como un procedimiento recursivo.

  
  void ordena( int vect[], int izq, int der ){ 

  
              int i = 0, j = 0, x = 0, aux = 0 ;
     
              i = izq;
              j = der; 
  
              x = vect [ (izq + der) /2 ]; 
  
              do{ 
  
                  while( (vect[i] < x) && (j <= der) ){
                         i++;}
                  while( (x < vect[j]) && (j > izq) ){
                         j--;}
                  if( i <= j ){
                      aux = vect[i];
                      vect[i] = vect[j];
                      vect[j] = aux;
                      i++;  j--;
                  }
              }while( i <= j ); 
  
              if( izq < j )
                  ordena( vect, izq, j ); 
  
              if( i < der )
                  ordena( vect, i, der );
          }