Metodo De Ordenamiento Quicksort

METODO DE ORDENAMIENTO QUICKSORT

IVAN DARIO DELGADO DIAZ 90092352128
CARLOS JHOVAN LENIS VALENCIA 90022857109

INGENIERIA DE SISTEMAS
UNIVERSIDAD DE PAMPLONA
JUNIO 2 DE 2011
SAN JOSE DE CUCUTA
METODO DE ORDENAMIENTO QUICKSORT

PROFESOR:
FELIX FERNANDO VARGAS

PARA OBTENER EL LOGRO #1 DE ANALISIS Y DISEÑO DE ALGORITMOS

IVAN DARIO DELGADO DIAZCARLOS JHOVAN LENIS VALENCIA

INGENIERIA DE SISTEMAS
UNIVERSIDAD DE PAMPLONA
JUNIO 2 DE 2011
SAN JOSE DE CUCUTA
INTRODUCCION

En el siguiente trabajo daremos a conocer la importancia de la utilización de este método, debido a que las estructuras de datos son utilizadas para almacenar información y para poder recuperar esa información de manera eficiente es deseable que aquella esté ordenada.Existen varios métodos para ordenar las diferentes estructuras de datos básicas. En general los métodos de ordenamiento no son utilizados con frecuencia, en algunos casos sólo una vez. Hay métodos muy simples de implementar que son útiles en los casos en donde el número de elementos a ordenar no es muy grande. Por otro lado hay métodos sofisticados, más difíciles de implementar pero que son máseficientes en cuestión de tiempo de ejecución como es nuestro método el QUICKSORT.

OBJETIVOS

OBJETICOS GENERALES
* Actualizar nuestros conocimientos frente al método de ordenamiento QUICKSORT.

OBJETIVOS ESPECÍFICOS
* Aprender la utilización e implementación de este método.
* Conocer la importancia de tener conocimiento de un método muy eficiente y eficaz en tiempo de ejecución.HISTORIA DEL QUICKSORT

El método de ordenamiento QuickSort es actualmente el más eficiente y veloz de los métodos de ordenación interna. Este método es una mejora sustancial del método de intercambio directo y recibe el nombre de QuickSort por la velocidad con que ordena los elementos del arreglo.
Su autor C.A. Hoare lo bautizó así, es un algoritmo basado en la técnica de divide yvencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n. El algoritmo original es recursivo, pero se utilizan versiones iterativas para mejorar su rendimiento (los algoritmos recursivos son en general más lentos que los iterativos, y consumen más recursos). Fue desarrollada por C. Antony R. Hoare en 1960.

La idea central de este algoritmo consiste en los siguiente:Se toma un elemento x de una posición cualquiera del arreglo. Se trata de ubicar a x en la posición correcta del arreglo, de tal forma que todos los elementos que se encuentran a su izquierda sean menores o iguales a x y todos los elementos que se encuentren a su derecha sean mayores o iguales a x. Se repiten los pasos anteriores pero ahora para los conjuntos de datos que se encuentran a laizquierda y a la derecha de la posición correcta de x en el arreglo.
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. Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de unelemento. 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.





DESCRIPCIÓN DEL ALGORITMO



El algoritmo constade los siguientes pasos:
* 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. Los elementos iguales al pivote pueden ser colocados tanto a su derecha como a su izquierda, dependiendo de la implementación deseada....