Algoritmo de ordenamientos recursivos

Bueno este fue un tema que quise dejar despues de la explicación de ordenamientos y de recursividad por que es una mezcla de los dos, es un algoritmo de ordenamiento recursivo.

Este tema se ve muy interesante, espero que en la practica sea de mucho agrado para todos ya que puede llegar a ser una gran fuente de ayuda.

El dia de hoy trataremos 2 de estos algoritmos:

• Quicsort
• Mergesort

Quicsort

Este algoritmo actualemente es el mas eficiente y veloz, su funcionamiento es de la siguiente manera:

• tomamos un valor 'a' del arreglo.
• buscamos la posición correcta del dato de tal forma que todos los que se encuentran a su izquierda seas menores o iguales que el y los de la derecha sean mayores o iguales a el.
• nos damos cuenta que el valor 'a' ya se encuentra en la posición correcta, el problema si divide en dos (se basa en la tecnica de divide y venceras, muy utilizado en programación orientado a objetos), al final reunimos los resultados en un vector.
  
• y repetimos el procedimiento inicial (usamos recursividad)
• el proceso finaliza cuando cada dato encuentra su posición correcta.

Este metodo recibe un vector de enteros, el dato en la posición inicial y el ultimo dato valido del array(n-1). la elelección del pivote se puede decir que la promedio ya se suba el dato inicial mas dato final entre dos, es una manera de asegurarse que sea el valor medio.
Hasta que i sea menor que el ultimo valor que es j, se realizaran los while que hacen referencia a:

• Mientras que el valor que se encuentre en la posición sea menor al que escogimos de pivote, se sumara a la posición mientras encontremos un valor igual o mayor al que se encuentre en el pivote.
• En este caso es muy parecido solo con la diferencia que el valor que se encuentre en la posición es mayor mientras encontremos un valor que sea igual o menos al del pivote.

Dentro del if se hace el intercambio de valores dependiendo la situación, por ultimo en los dos if finales el metodo se vuelve recursivo pero en un lado actualiza el valor maximo, mientras que en el otro if se actualiza el valor inicial.

Mergesort

Es un algoritmo de ordenación tambien denominado ordenamiento por mezcla, se basa en la tecnica de divide y venceras; funciona de la siguiente manera:

• Si el largo de un array es de 0 ó 1, entonces ya está ordenado.
• Dividir el array desordenado en dos subarrays de aproximadamente la mitad del tamaño.
• Ordenamos cada subarray recursivamente aplicando el ordenamiento por mezcla.
• Mezclamos los dos subarrays en una solo array ordenado.
  

El algoritmo mergesort incorpora una idea principal para mejorar su tiempo de ejecución:

Siempre es mejor pequeños problemas que uno grande, es bueno aplicar la tecnica de divide y venceras. ya que es mas facil enlazar dos arrays previamente ordenados que desordenados.

Bibliografia

• Ordenamiento por mezcla, consultado [18 de abril 2010], http://es.wikipedia.org/wiki/Ordenamiento_por_mezcla
• Quicsort, consultado [17 de abril 2010], http://es.wikipedia.org/wiki/Quicksort
• Quicsort, consultado [17 de abril 2010], http://www.angelfire.com/wy2/est_info/quicksort.html
• Mergesort implementation in Java, consultado [18 de abril 2010], http://www.java-tips.org/java-se-tips/java.lang/merge-sort-implementation-in-java.html