Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 267 vistas

    Método Quick Sort

    Cargado por

    Alán Manuel Guillén López
    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".

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Descargue como PPTX, PDF, TXT o lea en línea desde Scribd

    Método Quick Sort

    Cargado por

    Alán Manuel Guillén López
    267 vistas14 páginas
    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".

    Derechos de autor

    © Attribution Non-Commercial (BY-NC)

    Formatos disponibles

    PPTX, PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    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".

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Descargue como PPTX, PDF, TXT o lea en línea desde Scribd
    Descargar como pptx, pdf o txt
    267 vistas14 páginas

    Método Quick Sort

    Cargado por

    Alán Manuel Guillén López
    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".

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Descargue como PPTX, PDF, TXT o lea en línea desde Scribd
    Descargar como pptx, pdf o txt
    Está en la página 1de 14

    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