Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

QUICKSORT

No description
by

Laura Grisales

on 18 February 2015

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of QUICKSORT

HISTORIA
Desarrollado por el científico de computación
CHARLES ANTONY RICHARD HOARE
quién se basó en la técnica
"Divide y vencerás"
, es decir, dividir en vectores cada vez más pequeños lo cual permite ordenar n cantidad de elementos en un tiempo proporcional a n log n
QUICKSORT
ELEMENTOS IMPORTANTES
Pivote
Indicador izquierdo
Indicador derecho
Auxiliar
FUNCIONAMIENTO
DEMOSTRACIÓN DE UN CASO PARTICULAR
Ejemplo: Se tiene un arreglo en el cual la cantidad de elementos que se van a ordenar son en potencia de 2, por lo tanto la fórmula es
K = log2(n)
, donde en este caso K es la cantidad de divisiones que se realizarán
TIPS PARA ELEGIR EL PIVOTE
El pivote puede ser cualquier elemento del arreglo, sin embargo hay que tener en cuenta:
Se puede recorrer inicialmente el arreglo y elegir un elemento de la mitad, pero por ser un elemento de la mitad provoca que el proceso tarde más de lo esperado
Lo más recomendable es elegir el primer, segundo o último elemento como pivote o elegir el valor intermedio entre 3 elementos del arreglo
Laura Grisales
Javir Urro
En la primera fase el algoritmo hará n comparaciones, en la segunda fase creará 2 sublistas de un tamaño aproximado de
n/2
, lo que quiere decir es que la cantidad total de comparaciones de las sublistas es de
2(n/2)
, en la tercera fase creará 4 sublistas, por lo tanto la cantidad de comparaciones es de
4(n/4)
PSEUDOCÓDIGO
Si izq es menor igual a der
Asigne a pivote el valor de izq
Mientras izq sea diferente de der haga
Mientras numeros[der] sea mayor a numeros[pivote]
Decremente en 1 a der
Fin Mientras
Mientras numeros[izq] sea menor a numeros[pivote]
Aumente en 1 a izq
Fin Mientras
Si der es diferente a izq
Asigne a aux el valor de numeros[der]
Asigne a numeros[der] el valor de numeros[izq]
Asigne a numeros[izq] el valor de aux
Fin Si
Fin Mientras
Gracias por la atención prestada
Full transcript