QUICKSORT
Páginas: 3 (670 palabras)
Publicado: 9 de agosto de 2015
**QUICKSORT
**
¿Qué es?
¿En que consiste?
Analisis
Implementación en c
Expresión de recurrencia
Método iterativo
Árbol de recurrencia
Método maestro
¿Qué es?
Esun algoritmo creado por el científico británico en
computación C. A. R. Hoare.
Esta basado en la técnica de divide y vencerás.
Permite, en promedio, ordenar n elementos en un
tiempoproporcional a n log n en el mejor de los
casos y n^2 en el peor de los casos.
¿En que consiste?
Consiste en ordenar un arreglo de forma
ascendente de la siguiente manera:
1.
Elegir un elemento de la listade elementos a
ordenar, al que llamaremos pivote.
2.
Acomodar los elementos del arreglo a cada lado del
pivote, de manera que del lado izquierdo queden
todos los menores al pivote y del ladoderecho los
mayores al pivote
3.
Colocar el pivote en su lugar, el arreglo queda
separado en dos subarreglos.
4.
Repetir este proceso de forma recursiva para cada
subarreglo mientras estos contengan masde un
elemento. Una vez terminado este proceso todos los
elementos estarán ordenados.
Elección del pivote
1.
El pivote será el primer elemento del arreglo
2.
El pivote será el elemento queesta a la mitad del
arreglo
3.
Que el pivote se elija de entre tres elementos del
arreglo(cualesquiera), los cuales debe comparar
para seleccionar el valor intermedio de los tres y
considerarlo comoel pivote.
PSEUDOCÓDIGO
función quickSort (RegistroT *a, entero p, entero
r)
comienza
si p < r entonces
q ← particionar (a, p, r)
quickSort (a, p, q−1)
quickSort (a, q+1, r)
fin si
fin Particionar(*a,p,r)
X a[r]
ip-1
for jp to r-1
do if a[j]<= x
then ii+1
a[i]a[j]
a[i+1]a[r]
return i+1
Análisis
Como se puede suponer, la eficiencia del algoritmo
depende de la posición en la quetermine el pivote
elegido.
En el mejor caso, el pivote termina en el centro de la
lista. En este caso, el orden de complejidad del
algoritmo es O(n·log n).
En el peor caso, el pivote termina en...
**
¿Qué es?
¿En que consiste?
Analisis
Implementación en c
Expresión de recurrencia
Método iterativo
Árbol de recurrencia
Método maestro
¿Qué es?
Esun algoritmo creado por el científico británico en
computación C. A. R. Hoare.
Esta basado en la técnica de divide y vencerás.
Permite, en promedio, ordenar n elementos en un
tiempoproporcional a n log n en el mejor de los
casos y n^2 en el peor de los casos.
¿En que consiste?
Consiste en ordenar un arreglo de forma
ascendente de la siguiente manera:
1.
Elegir un elemento de la listade elementos a
ordenar, al que llamaremos pivote.
2.
Acomodar los elementos del arreglo a cada lado del
pivote, de manera que del lado izquierdo queden
todos los menores al pivote y del ladoderecho los
mayores al pivote
3.
Colocar el pivote en su lugar, el arreglo queda
separado en dos subarreglos.
4.
Repetir este proceso de forma recursiva para cada
subarreglo mientras estos contengan masde un
elemento. Una vez terminado este proceso todos los
elementos estarán ordenados.
Elección del pivote
1.
El pivote será el primer elemento del arreglo
2.
El pivote será el elemento queesta a la mitad del
arreglo
3.
Que el pivote se elija de entre tres elementos del
arreglo(cualesquiera), los cuales debe comparar
para seleccionar el valor intermedio de los tres y
considerarlo comoel pivote.
PSEUDOCÓDIGO
función quickSort (RegistroT *a, entero p, entero
r)
comienza
si p < r entonces
q ← particionar (a, p, r)
quickSort (a, p, q−1)
quickSort (a, q+1, r)
fin si
fin Particionar(*a,p,r)
X a[r]
ip-1
for jp to r-1
do if a[j]<= x
then ii+1
a[i]a[j]
a[i+1]a[r]
return i+1
Análisis
Como se puede suponer, la eficiencia del algoritmo
depende de la posición en la quetermine el pivote
elegido.
En el mejor caso, el pivote termina en el centro de la
lista. En este caso, el orden de complejidad del
algoritmo es O(n·log n).
En el peor caso, el pivote termina en...
Leer documento completo
Regístrate para leer el documento completo.