Skip to content
ExamplesEspañolWorkspace →

Quicksort

Picks a pivot, splits smaller from larger values and sorts each side recursively.

Level
Advanced
Topic:
Sorting & searching
Concepts:
Input & output
Arrays
SubProcesos
Functions
Recursion
Repetir
Si
Randomness
Open in Codoritmo

Run, change and debug this example in your browser.

What you'll learn

Particionar uses Hoare's method: two indexes walk in from both ends and swap whenever each one finds a value on the wrong side of the pivot. Then each part is sorted with the same idea. If the pivot splits the array roughly in half it costs O(n log n); if it always lands at one end, O(n²). It needs no extra array, only the call stack (O(log n)).

Code

quicksort.psc · 63 lines
// Muestra el arreglo completo solo si es corto (30 o menos)SubProceso MostrarDatos(titulo, datos, n)    Definir i Como Entero    Si n <= 30 Entonces        Escribir Sin Saltar titulo        Para i <- 1 Hasta n Hacer            Escribir Sin Saltar datos[i], " "        FinPara        Escribir ""    SiNo        Escribir titulo, n, " números (el primero es ", datos[1], " y el último ", datos[n], ")"    FinSiFinSubProceso// Partición de Hoare: deja a la izquierda los valores <= pivote y a la derecha// los >= pivote, y devuelve dónde termina la parte izquierda.Funcion corte <- Particionar(datos, izquierda, derecha)    Definir corte, pivote, i, j, aux Como Entero    // Usamos el elemento del medio como pivote    pivote <- datos[Trunc((izquierda + derecha) / 2)]    i <- izquierda - 1    j <- derecha + 1    Repetir        // i avanza hasta encontrar uno que no debería estar a la izquierda        Repetir            i <- i + 1        Hasta Que datos[i] >= pivote        // j retrocede hasta encontrar uno que no debería estar a la derecha        Repetir            j <- j - 1        Hasta Que datos[j] <= pivote        // Si no se cruzaron, los intercambiamos y seguimos        Si i < j Entonces            aux <- datos[i]            datos[i] <- datos[j]            datos[j] <- aux        FinSi    Hasta Que i >= j    corte <- jFinFuncionSubProceso OrdenarRapido(datos, izquierda, derecha)    Definir corte Como Entero    Si izquierda < derecha Entonces        corte <- Particionar(datos, izquierda, derecha)        // Cada lado se ordena por separado, con la misma idea        OrdenarRapido(datos, izquierda, corte)        OrdenarRapido(datos, corte + 1, derecha)    FinSiFinSubProcesoAlgoritmo Quicksort    Definir datos, n, i Como Entero    Escribir "¿Cuántos números quieres ordenar? (1 a 512)"    Leer n    Dimension datos[n]    Para i <- 1 Hasta n Hacer        datos[i] <- Aleatorio(1, 99)    FinPara    MostrarDatos("Antes:   ", datos, n)    OrdenarRapido(datos, 1, n)    MostrarDatos("Después: ", datos, n)FinAlgoritmo

Flowchart

Each block in the flowchart matches one instruction in the code.

Algoritmo Quicksort
Algoritmo QuicksortAlgoritmo QuicksortAlgoritmo QuicksortDefinir datos, n, i Como EnteroDefinir datos, n, i ComoEnteroEscribir "¿Cuántos números quieres ordenar? (1 a 512)"Escribir "¿Cuántos númerosquieres ordenar? (1 a 512)"Leer nLeer nDimension datos[n]Dimension datos[n]Para i <- 1 Hasta n HacerPara i <- 1 Hasta ndatos[i] <- Aleatorio(1, 99)datos[i] <- Aleatorio(1, 99)MostrarDatos("Antes: ", datos, n)MostrarDatos("Antes: ",datos, n)OrdenarRapido(datos, 1, n)OrdenarRapido(datos, 1, n)MostrarDatos("Después: ", datos, n)MostrarDatos("Después: ",datos, n)FinAlgoritmoFinAlgoritmo
SubProceso MostrarDatos
SubProceso MostrarDatosSíNoSubProceso MostrarDatos(titulo, datos, n)SubProceso MostrarDatos(titulo,datos, n)Definir i Como EnteroDefinir i Como EnteroSi n <= 30 Entoncesn <= 30Escribir Sin Saltar tituloEscribir Sin Saltar tituloPara i <- 1 Hasta n HacerPara i <- 1 Hasta nEscribir Sin Saltar datos[i], " "Escribir Sin Saltar datos[i]," "Escribir ""Escribir ""Escribir titulo, n, " números (el primero es ", datos[1], " y el último ", datos[n], ")"Escribir titulo, n, " números(el primero es ", datos[1], "y el último ", datos[n], ")"FinSubProcesoFinSubProceso
Funcion Particionar
Funcion ParticionarNoNoSíSíNoSíNoSíFuncion corte <- Particionar(datos, izquierda, derecha)Funcion corte <-Particionar(datos, izquierda,…Definir corte, pivote, i, j, aux Como EnteroDefinir corte, pivote, i, j,aux Como Enteropivote <- datos[Trunc((izquierda + derecha) / 2)]pivote <-datos[Trunc((izquierda +derecha) / 2)]i <- izquierda - 1i <- izquierda - 1j <- derecha + 1j <- derecha + 1i <- i + 1i <- i + 1Hasta Que datos[i] >= pivotedatos[i] >= pivotej <- j - 1j <- j - 1Hasta Que datos[j] <= pivotedatos[j] <= pivoteSi i < j Entoncesi < jaux <- datos[i]aux <- datos[i]datos[i] <- datos[j]datos[i] <- datos[j]datos[j] <- auxdatos[j] <- auxHasta Que i >= ji >= jcorte <- jcorte <- jFinFuncion (devuelve corte)FinFuncion (devuelve corte)
SubProceso OrdenarRapido
SubProceso OrdenarRapidoSíNoSubProceso OrdenarRapido(datos, izquierda, derecha)SubProceso OrdenarRapido(datos,izquierda, derecha)Definir corte Como EnteroDefinir corte Como EnteroSi izquierda < derecha Entoncesizquierda < derechacorte <- Particionar(datos, izquierda, derecha)corte <- Particionar(datos,izquierda, derecha)OrdenarRapido(datos, izquierda, corte)OrdenarRapido(datos,izquierda, corte)OrdenarRapido(datos, corte + 1, derecha)OrdenarRapido(datos, corte +1, derecha)FinSubProcesoFinSubProceso

Sample run

This is what the program shows when it runs. The answers typed by the user are highlighted.

¿Cuántos números quieres ordenar? (1 a 512)User answer: 12Antes:   57 95 53 48 81 13 78 10 53 4 56 3 Después: 3 4 10 13 48 53 53 56 57 78 81 95

Complexity

How much work and memory it needs as the amount of data (n) grows.

Complexity
CaseCost
BestO(n log n)
AverageO(n log n)
WorstO(n²)
MemoryO(log n)

Traits:Not stableIn place

Challenge

Use a random element of the range as the pivot instead of the middle one.

Show hint

Aleatorio(izquierda, derecha) gives a position in the range; store datos[that position] in pivote.

Open in Codoritmo

Related examples

  • Linear vs. Binary Search

    Counts the comparisons each search needs on the same sorted list.

    Intermediate

  • Shell Sort

    Insertion sort between far-apart elements, with a gap that shrinks every pass.

    Advanced

  • Bubble Sort

    Sorts random numbers by swapping neighbors, and stops as soon as they're in order.

    Intermediate