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 );
          }

   

   

   

   

   

   

   

   

   

   

   

 

Metodo de Inserción

 ¿Que es el Metodo de ordenamiento por Insercion?

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.

La idea de este algoritmo de ordenación consiste en ir insertando un elemento de la lista ó un arreglo en la parte ordenada de la misma, asumiendo que el primer elemento es la parte ordenada, el algoritmo ira comparando un elemento de la parte desordenada de la lista con los elementos de la parte ordenada, insertando el elemento en la posición correcta dentro de la parte ordenada, y así sucesivamente hasta obtener la lista ordenada.

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

 Pasos para realizar el ordenamiento de Inserción

1. Comenzamos con una lista de elementos no ordenados

    

     2. Se selecciona el segundo valor como clave y se lo compara con los valores ubicados a su izquierda y se inserta en el lugar correspondiente

 3.Se selecciona el siguiente número como clave y se repite el proceso para todos los valores anteriores

    4.Se selecciona la siguiente clave

     5. Finalmente se selecciona la última clave

   

  6.Al finalizar el algoritmo tenemos como resultado la lista ordenado

 Algoritmo en C

void insert_sort(int v[], int size)
{
    int i, j, temp;
    for (i = 0; i < size; i++)
    {
        temp = v[i];
        j = i - 1;
        while (j >= 0 && v[j] > temp)
        {
            v[j + 1] = v[j];
            j--;
        }

        v[j + 1] = temp;
    }
}

Ejemplo Metodo de Ordenacion por Inserción