transparencias del método de clasificación quicksort

ALGORITMOS DE CLASIFICACIÓN INTERNA

1) Inserción directa. Mejoras:

1) Inserción Binaria

2) Selección directa

2) Intercambio directo (Burbuja)

3) Inserción con incrementos decrecientes (Shell)

4) Método del montículo (“Heapsort”)

5) Método rápido (“Quicksort”)

QUICKSORT = METODO DE ORDENAMIENTO RÁPIDO

El ordenamiento rápido (quicksort en ingles) es un algoritmo basado en la

técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en una complejidad de n log n. Es la técnica de

ordenamiento más rápida conocida.

Fue Charles Antony Richard Hoare un científico Británico en

computación, quien en 1960 invento el método de

ordenación mas rápido, “Quicksort”,. También se le

conoce por el desarrollo de la Lógica de Hoare, y el lenguaje

formal CSP.

El algoritmo fundamental es el siguiente :

1º Elegimos un elemento del vector, puede ser cualquiera. Lo llamaremos elemento de división o pivote.

Pivote o elemento de división

La forma más efectiva es coger como pivote el elemento intermedio

2º Buscamos la posición que le corresponde en el vector al pivote y ordenamos los elementos de la lista de manera que a lado queden los menores y a otro los mayores.

PIVOTE

Mayores Menores

3º Realizamos esto de forma recursiva para que cada “subvector” mientras este tengan un largo mayor que 1

EJEMPLO. QUICKSORT ITERATIVO 

8 1 4 9 6 3 5 2 7 0

Pivote  = 6 izq=1 inf=1 

der=10 sup=10 

0 1 4 9 6 3 5 2 7 8

Pivote  = 6 izq=1  der=10 inf=2  sup=9 

0 1 4 9 6 3 5 2 7 8

Pivote  = 6 izq=1  der=10 inf=3  sup=9 

0 1 4 9 6 3 5 2 7 8

Pivote  = 6 izq=1  der=10 inf=4  sup=9 

cima=0 

EJEMPLO. QUICKSORT ITERATIVO 

0 1 4 9 6 3 5 2 7 0

Pivote  = 6 izq=1  der=10 

0 1 4 2 6 3 5 9 7 8

Pivote  = 6       inf=5 

izq=1  der=10 sup=7 

0 1 4 2 5 3 6 9 7 8

Pivote  = 6 izq=1  der=10    inf=6 sup=6 

0 1 4 2 5 3 6 9 7 8

Pivote  = 6     inf=7 

izq=1  der=10 sup=6 

sup=8 inf=4 

EJEMPLO. QUICKSORT ITERATIVO 

0 1 4 2 5 3 6 9 7 8

Pivote  = 9  der=10 sup=10 

0 1 4 2 5 3 6 9 7 8

Pivote = 9      inf=8 

der=10 sup=10 

izq=7 

0 1 4 2 5 3 6 8 7 9

izq=7  der=10 Pivote = 9 

sup=9 Inf=9 

0 1 4 2 5 3 6 8 7 9

izq=7  der=10 Inf = 10 Pivote = 9 

sup=9 

cima=1 Lim_izq=1 Lim_der=6 

izq=7 inf=7 

cima=2 Lim_izq=7 Lim_der=9 

Algoritmo Quicksort recursivo PROCEDIMIENTO quicksort (a: tipo_vector (E/S), izq: entero (E), der: entero (E))

VAR i,j: entero x,w: tipo_elemento INICIO

iizq jder xa [(izq+der)/2] Mientras (i<=j) hacer Mientras (a[i].clave<x.clave) hacer ii+1 Fin_mientras Mientras (x.clave<a[j].clave) hacer jj-1 Fin_mientras Si (i<=j) entonces wa[i] a[i]a[j] a[j]w ii+1 jj-1 Fin_si Fin_mientras Si (izq<j) entonces LLAMAR A quicksort (a,izq,j) Fin_si Si (i<der) entonces LLAMAR A quicksort (a,i,der) Fin_si

FIN_PROCEDIMIENTO

Algoritmo Quicksort iterativo [1] TIPO tipo_pila= REGISTRO

izq, der : entero FIN_REGISTRO TIPO tpila=vector [Max] de tipo_pila

PROCEDIMIENTO quicksort_pila (a: tipo_vector (E/S))

VAR i, j, izq, der, cima: entero x,w: tipo_elemento pila: tpila

INICIO

cima0 pila [0].izq0 pila [0].dern-1 Mientras (cima>=0) hacer izqpila [cima].izq derpila [cima].der cimacima-1

1 2

Algoritmo Quicksort iterativo [2]

Mientras (izq<der) hacer iizq jder xa [(izq+der)/2 Mientras (i<=j) hacer Mientras (a[i].clave<x.clave) hacer ii+1 Fin_mientras Mientras (x.clave<a[j].clave) hacer jj-1 Fin_mientras Si (i<=j) entonces

wa[i] a [i]a[j] a [j]w ii+1 jj-1 Fin_si Fin_mientras

1 2

1 2

Algoritmo Quicksort iterativo [3]

Si ((j-izq) < (der-i)) entonces Si (i<der) entonces cimacima+1 pila [cima].izqi pila [cima].derder Fin_si derj Si_no Si (j>izq) entonces cimacima+1 pila [cima].izqizq pila [cima].derj Fin_si izqi Fin_si

Fin_mientras Fin_mientras FIN_PROCEDIMIENTO

1 2

COMPLEJIDAD

•  Mejor caso: Pivote en el centro de la lista. Orden de complejidad del algoritmo: O(n·logn).

•  Peor caso: Pivote en un extremo de la lista. Orden de complejidad del algoritmo: O (n²). Suele producirse en algoritmos ordenados o casi ordenados.

•  Caso promedio: el orden es O (n·log n).

Conclusiones

Ventajas:

•  Su orden de complejidad. • Muy rápido. • No requiere memoria adicional para su forma

recursiva, aunque para la iterativa sí que necesita espacio adicional (para la pila).

Conclusiones

Desventajas:

•  Es muy poco estable. •  La complejidad depende de donde elijamos el pivote,

aunque lo más adecuado es elegirlo en el centro. •  Implementación algo complicada. •  El algoritmo en su forma recursiva emplea muchos

recursos. •  Mucha diferencia entre el peor y el mejor caso.