Post on 28-Sep-2018
Declaremos un arreglo de 9 posiciones con numeros aleatorios...
44 75 23 43 55 12 64 77 33
1 2 3 4 5 6 7 8 9
Declaramos el primer elemento del arreglo como primeroY al ultimo como ultimo.
44 75 23 43 55 12 64 77 33
1 2 3 4 5 6 7 8 9
Primero Ultimo
44 75 23 43 55 12 64 77 33
1 2 3 4 5 6 7 8 9
Primero Ultimo
Pivote
Declaramos el primero como el pivote del arreglo.
44 75 23 43 55 12 64 77 33
1 2 3 4 5 6 7 8 9
Primero Ultimo
Up
Pivote44
Down
Colocamos a Up como Primero y Down como Ultimo.
44 75 23 43 55 12 64 77 33
1 2 3 4 5 6 7 8 9
Primero Ultimo
Up Down
Muevo Up al primer valor mayor que el pivote
Up
Despues movemos Down al primer valor de derecha a izquierdamenor que el pivote (en este caso Down no se mueve).
Pivote44
44 75 23 43 55 12 64 77 331 2 3 4 5 6 7 8 9
Primero UltimoDownUp
Pivote44
Ahora intercambiamos los valores de Up y Down
44 33 23 43 55 12 64 77 751 2 3 4 5 6 7 8 9
44 33 23 43 55 12 64 77 751 2 3 4 5 6 7 8 9
PrimeroDownUp
Pivote44
Ultimo
Desde la posicion en que se encuentra movemos Up a un valor mayorque el pivote.
44 33 23 43 55 12 64 77 75
1 2 3 4 5 6 7 8 9
PrimeroDownUp
Ultimo
44 33 23 43 55 12 64 77 75
1 2 3 4 5 6 7 8 9
PrimeroUp UltimoDown
Cambiamos Down a la posicion menor que el pivote recorriendo deDerecha a Izquierda
Down
Pivote44
44 33 23 43 55 12 64 77 75
1 2 3 4 5 6 7 8 9
PrimeroUp UltimoDown
Down
Pivote44
Intercambiamos los valores de Up y Down…
44 33 23 43 12 55 64 77 75
1 2 3 4 5 6 7 8 9
44 33 23 43 12 55 64 77 75
1 2 3 4 5 6 7 8 9
Primero Up UltimoDown
Pivote44
Movemos Up desde la posicion en que se encuetra a la primera posicion mayor que el pivote y Down a la primera posicion de derecha a Izquierda menor que el pivote.
44 33 23 43 12 55 64 77 75
1 2 3 4 5 6 7 8 9
Primero Up Down Ultimo
Como Up y Down se cruzaron, entonces debemos intercambiar el valor de Down por el pivote.
12 33 23 43 44 55 64 77 75
1 2 3 4 5 6 7 8 9
Primero Down Ultimo
Pivote44
PivIndexAhora notemos que todos los valores debajo de PivIndex son menores que el y los que estan por encima son mayores que el.
12 33 23 43 44 55 64 77 75
1 2 3 4 5 6 7 8 9
Primero 1 Ultimo 1PivIndex
Esto nos da ahora dos nuevos subarreglos que hay que ordenar
Ultimo 2Primero 2
Se debe repetir el proceso hasta que los subarreglos estén ordenados, lo cual nos dará como resultado el arreglo ordenado.
El algoritmo del método de ordenamiento estará formado por tres procesos:
• QuickSort, proceso que inicia el ordenamiento.• Encuentra Pivote, busca el mejor pivote a partir
del primer elemento del vector• Partición, va comparando por ambos extremos e
intercambia en caso de ser necesario
1. Inicio quicksort( i , j : enteras)2. indice-pivoteencuentra-pivote( i , j)3. Si indice-pivote < > 0 entonces
3.1 pivote A[indice-pivote].data3.2 kparticion( i , j , pivote)3.3 quicksort( i , k – 1)3.4 quicksort(k , j )
4. Fin quicksort
1. Inicio encuentra-pivote( i , j : enteras)2. primera-claveA[i].data3. Para k i +1 hasta j hacer
3.1 Si a[k].data > primera-clave entoncesreturna k
de lo contrario,Si A[k].data > primera-clave entoncesreturna i
4. returna 05. Fin
1. Inicio partición( i , j : enteras, pivote:tipo-clave) : entero2. z i;3. dj;4. Repetir
intercambiar(A[z],A[d])Mientras A[z].data < pivote hacer
z z + 1Mientras A[d].data >= pivote hacer
d d + 1hasta
z > d4. returna z5. Fin
Si un arreglo esta dado por:x = [25 57 48 37 12 92 86 33]