Transparencias del Mtodo de Clasificacin Quicksort

  • Published on
    13-Jun-2015

  • View
    1.284

  • Download
    2

Transcript

ALGORITMOS DE CLASIFICACIN INTERNA 1) nsercin directa. Mejoras: I 1) nsercin Binaria I 2) eleccin directa S 2) ntercambio directo (Burbuja) I 3) nsercin con incrementos decrecientes (Shell) I 4) todo del montculo (Heapsort) M 5) todo rpido (Quicksort) M

QUICKSORT = METODO DE ORDENAMIENTO RPIDOEl ordenamiento rpido (quicksort en ingles) es un algoritmo basado en la tcnica de divide y vencers, que permite, en promedio, ordenar n elementos en una complejidad de n log n. Es la tcnica de ordenamiento ms rpida conocida.

Fue Charles Antony Richard Hoare un cientfico Britnico en computacin, quien en 1960 invento el mtodo de ordenacin mas rpido, Quicksort,. Tambin se le conoce por el desarrollo de la Lgica 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 divisin o pivote.

Pivote o elemento de divisin

La forma ms efectiva es coger como pivote el elemento intermedio

2 Buscamos la posicin 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.

Menores PIVOTE

Mayores

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

EJEMPLO.QUICKSORTITERATIVO

8cima=0izq=1 inf=1

1

4

9

6Pivote=6

3

5

2

7

0der=10 sup=10

0izq=1

1inf=2

4

9

6Pivote=6

3

5

2

7sup=9

8der=10

0izq=1

1

4inf=3

9

6Pivote=6

3

5

2

7sup=9

8der=10

0izq=1

1

4

9inf=4

6Pivote=6

3

5

2

7sup=9

8der=10

EJEMPLO.QUICKSORTITERATIVO

0izq=1

1

4

9inf=4

6Pivote=6

3

5

2sup=8

7

0der=10

0izq=1

1

4

2

6Pivote=6 inf=5

3

5sup=7

9

7

8der=10

0izq=1

1

4

2

5

3inf=6 sup=6

6Pivote=6

9

7

8der=10

0izq=1

1

4

2

5

3sup=6

6Pivote=6 inf=7

9

7

8der=10

EJEMPLO.QUICKSORTITERATIVO

0cima=1 Lim_izq=1 Lim_der=6

1

4

2

5

3

6izq=7 inf=7

9Pivote=9

7

8der=10 sup=10

0

1

4

2

5

3

6izq=7

9Pivote=9 inf=8

7

8der=10 sup=10

0

1

4

2

5

3

6izq=7

8

7sup=9 Inf=9

9der=10 Pivote=9

0cima=2 Lim_izq=7 Lim_der=9

1

4

2

5

3

6izq=7

8

7sup=9

9der=10 Inf=10 Pivote=9

Algoritmo Quicksort recursivoPROCEDIMIENTO 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