Quick sort
Páginas: 2 (362 palabras)
Publicado: 15 de mayo de 2010
Quicksort
Quicksort el ordenamiento rápido
El método de ordenamiento Quick Sort es actualmente el más eficiente y veloz de los métodos de ordenación interna. Este método es una mejorasustancial del método de intercambio directo y recibe el nombre de Quick Sort por la velocidad con que ordena los elementos del arreglo. Su autor C.A. Hoare lo bautizó así. es un algoritmo basado en latécnica de divide y vencerá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 surendimiento (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.
Descripción deelementos a ordenar, al que llamaremos pivote. del algoritmo Elegir un elemento de la lista
La idea central de este algoritmo consiste en los siguiente: Se toma un elemento x de una posicióncualquiera 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 quese 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 la izquierda y a la derecha de la posición correctade 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 ocupaexactamente el lugar que le corresponderá en la lista ordenada. Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este procesotodos 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
...
Quicksort el ordenamiento rápido
El método de ordenamiento Quick Sort es actualmente el más eficiente y veloz de los métodos de ordenación interna. Este método es una mejorasustancial del método de intercambio directo y recibe el nombre de Quick Sort por la velocidad con que ordena los elementos del arreglo. Su autor C.A. Hoare lo bautizó así. es un algoritmo basado en latécnica de divide y vencerá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 surendimiento (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.
Descripción deelementos a ordenar, al que llamaremos pivote. del algoritmo Elegir un elemento de la lista
La idea central de este algoritmo consiste en los siguiente: Se toma un elemento x de una posicióncualquiera 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 quese 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 la izquierda y a la derecha de la posición correctade 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 ocupaexactamente el lugar que le corresponderá en la lista ordenada. Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este procesotodos 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
...
Leer documento completo
Regístrate para leer el documento completo.