Algoritmos De Ordenamiento Recursivo

Algoritmos de ordenamiento Recursivo
Dentro de los algoritmos de ordenamiento recursivo se encuentran los métodos de MergeSort (Ordenación por mezclas sucesivas) y QuickSort (Ordenamiento Rápido).
3.2.1 MergeSort
El algoritmo Merge divide el arreglo original en dos arreglos y los coloca en arreglos separados. Cada arreglo es recursivamente ordenado y finalmente se unen los arreglos en un arregloordenado. Como cualquiera de los algoritmos de ordenamiento recursivo el algoritmo Merge tiene complejidad de O(n log n). Fue desarrollado por John Von Neumann.
Algoritmo
void ordenarMezcla(TipoEle A[], int izq, int der)
{ if ( izq < der )
  { centro = ( izq + der ) % 2; 
    ordenarMezcla( A, izq, centro );
    ordenarMezcla( A, centro+1, der);
    intercalar( A, izq, centro, der ); 
  }
}
voidintercalar(TipoEle A[], int a, int c, int b )
{ k = 0;
  i = a;
  j = c + 1;
  n = b - a;
  while ( i < c + 1 ) && ( j < b + 1 )
  { if ( A[i] < A[j] )
    { B[k] = A[i];
      i = i + 1;
    }
    else
    { B[k] = A[j];
      j = j + 1;
    }
   k = k + 1;
  };
while ( i < c + 1 )
{ B[k] = A[i];
  i++;
  k++;
};
while ( j < b + 1 )
{ B[k] = A[j];
  j++;
  k++;
};
i = a;
for ( k = 0; k < n; i++)
{ A[i] = B[k];
  i++;
};
};
Este método aplica la técnica divide-y-vencerás, dividiendo la secuencia de datos en dos subsecuencias hasta que las subsecuencias tengan un único elemento, luego se ordenan mezclando dos subsecuencias ordenadas en una secuencia ordenada, en forma sucesiva hasta obtener una secuencia única ya ordenada. Si n = 1 solo hay un elemento por ordenar, sino se hace unaordenación de mezcla de la primera mitad del arreglo con la segunda mitad. Las dos mitades se ordenan de igual forma. Ejemplo: Se tiene un arreglo de 8 elementos, se ordenan los 4 elementos de cada arreglo y luego se mezclan. El arreglo de 4 elementos, se ordenan los 2 elementos de cada arreglo y luego se mezclan. El arreglo de 2 elementos, como cada arreglo sólo tiene n = 1 elemento, solo se mezclan.Ejemplo 3.5 Esquema procedimiento Algoritmo MergeSort

Análisis del algoritmo.
Estabilidad: Sí es estable.
Requerimientos de Memoria: Se necesita memoria auxiliar del mismo tamaño de los conjuntos a mezclar.
Tiempo de Ejecución: O(n log n).
Ventajas
Desventajas
A) Rápido
A) Implementación compleja.
B) Especial para datos atómicos o registros con pocos componentes
B) Grandes Requerimientos deMemoria
3.2.2 QuickSort
La ordenacion rapida, inventada y nombrada por C.A.R. Hoare en 1960, esta considerada como el mejor algoritmo de ordenacion disponible actualmente. Esta basada en la ordenacion por el metodo de intercambio.
La ordenacion rápida se basa en la idea de las particiones. El procedimiento general es seleccionar un valor llamado COMPARANDO y entonces dividir el array en dos partes. En unlado todos los elementos mayores o iguales al valor de particion y en otro todos los elementos menores que el valor. Este proceso se repite en cada parte restante hasta que el array esté ordenado.
Como se puede ver, este proceso es esencialmente recursivo por naturaleza y, de hecho, las implementaciones mas claras de la ordenacion rapida es por algoritmos recursivos.
La seleccion del valorcomparado se puede obtener de dos formas. Se puede seleccionar aleatoriamente o haciendo la media de un pequeno conjunto de valores tomados del array. Para una ordenacion optima es mejor seleccionar un valor que este precisamente en medio del rango de valores. Sin embargo, esto no es facil de hacer en la mayoria de los conjuntos de datos. En el caso peor, el valor escogido esta en un extremo. Incluso eneste, la ordenacion rapida todavia funciona bien. La version de la ordenacion rapida que sigue selecciona el elemento mitad del array. Aunque no siempre sera una buena eleccion, la ordenacion sigue funcionando correctamente.
Ejemplo 3.6 Ordenamiento por QuickSort
Secuencia inicial 8 2 5 3 9
Elemento comparando: 5
Primer paso 3 2 5 8 9
Ahora se ordena con el mismo procedimiento los vectores '3...