Scribd
Cargar
311 vistas14 páginas

Guía del Método Quick Sort en Ordenamiento

El método Quick Sort es actualmente el método de ordenamiento interno más eficiente y veloz. Funciona de forma recursiva dividiendo el arreglo en subconjuntos a la izquierda y derecha de un pivote, de modo que todos los elementos a la izquierda sean menores o iguales al pivote y todos los elementos a la derecha sean mayores o iguales. Este método es más rápido que el intercambio directo al ordenar elementos de forma más eficiente mediante la técnica de "divide y vencerás".

Cargado por

Alán Manuel Guillén López
Derechos de autor
© Attribution Non-Commercial (BY-NC)
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PPTX, PDF, TXT o lee en línea desde Scribd
311 vistas14 páginas

Guía del Método Quick Sort en Ordenamiento

El método Quick Sort es actualmente el método de ordenamiento interno más eficiente y veloz. Funciona de forma recursiva dividiendo el arreglo en subconjuntos a la izquierda y derecha de un pivote, de modo que todos los elementos a la izquierda sean menores o iguales al pivote y todos los elementos a la derecha sean mayores o iguales. Este método es más rápido que el intercambio directo al ordenar elementos de forma más eficiente mediante la técnica de "divide y vencerás".

Cargado por

Alán Manuel Guillén López
Derechos de autor
© Attribution Non-Commercial (BY-NC)
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PPTX, PDF, TXT o lee en línea desde Scribd

Mtodo Quick Sort

El mtodo de ordenamiento Quick Sort

es actualmente el ms eficiente y veloz de los mtodos de ordenacin interna

Es tambin conocido con el nombre del mtodo

rpido y de ordenamiento por particin, en el mundo de habla hispana.

Este mtodo es una mejora sustancial del mtodo 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.

La idea central de este algoritmo consiste en los

siguiente: Se toma un elemento x de una posicin cualquiera del arreglo. Se trata de ubicar a x en la posicin 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 la izquierda y a la derecha de la posicin correcta de x en el arreglo.

El ordenamiento por particin (Quick Sort) se puede

definir en una forma ms conveniente como un procedimiento recursivo.

Tiene aparentemente la propiedad de trabajar mejor

para elementos de entrada desordenados completamente, que para elementos semiordenados. Esta situacin es precisamente la opuesta al ordenamiento de burbuja.

Este tipo de algoritmos se basa en la tcnica "divide y

vencers", o sea es ms rpido y fcil ordenar dos arreglos o listas de datos pequeos , que un arreglo o lista grande.

Normalmente al inicio de la ordenacin se escoge un

elemento aproximadamente en la mitad del arreglo, as al empezar a ordenar, se debe llegar a que el arreglo este ordenado respecto al punto de divisin o la mitad del arreglo.

El algoritmo bsico del metodo Quicksort consiste en

tomar cualquier elemento de la lista al cual denominaremos como pivote, dependiendo de la particin en que se elija, el algoritmo ser ms o menos eficiente.

Tomar un elemento cualquiera como pivote tiene la

ventaja de no requerir ningn clculo adicional, lo cual lo hace bastante rpido. Otra opcin puede ser recorrer la lista para saber de antemano qu elemento ocupar la posicin central de la lista, para elegirlo como pivote. La opcin a medio camino es tomar tres elementos de la lista - por ejemplo, el primero, el segundo, y el ltimo - y compararlos, eligiendo el valor del medio como pivote.

Una idea preliminar para ubicar el pivote en su

posicin final sera contar la cantidad de elementos menores que l, y colocarlo un lugar ms arriba, moviendo luego todos esos elementos menores que l a su izquierda, para que pueda aplicarse la recursividad.

Existe, no obstante, un procedimiento mucho ms

efectivo. Se utilizan dos ndices: i, al que llamaremos ndice izquierdo, y j, al que llamaremos ndice derecho.

Parmetros:
Se debe llamar a la funcin Quicksort

desde donde quiera ejecutarse. sta llamar a colocar pivote para encontrar el valor del mismo. Se ejecutar el algoritmo Quicksort de forma recursiva a ambos lados del pivote.

También podría gustarte