Skip to content
ExamplesEspañolWorkspace →

Heap Sort

Arranges the array as a heap, then takes the largest out again and again.

Level
Advanced
Topic:
Sorting & searching
Concepts:
Input & output
Arrays
SubProcesos
Mientras
Para
Si
Logic
Randomness
Open in Codoritmo

Run, change and debug this example in your browser.

What you'll learn

A heap is a tree stored in the array: the children of position k are at 2k and 2k + 1, and every parent is larger than its children, so the largest value sits at position 1. It's swapped with the last one, the heap shrinks, and Hundir repairs it in log n steps. It always costs O(n log n) and uses no extra memory.

Code

heap-sort.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// En un montículo, el padre de la posición k está en Trunc(k / 2)// y sus hijos en 2k y 2k + 1. Cada padre es mayor o igual que sus hijos.// Hundir baja el valor de la posición raiz hasta que vuelve a cumplirse.SubProceso Hundir(datos, raiz, tamanio)    Definir actual, hijo, aux Como Entero    Definir listo Como Logico    actual <- raiz    listo <- Falso    Mientras (NO listo) Y 2 * actual <= tamanio Hacer        // Elegimos el mayor de los dos hijos        hijo <- 2 * actual        Si hijo + 1 <= tamanio Entonces            Si datos[hijo + 1] > datos[hijo] Entonces                hijo <- hijo + 1            FinSi        FinSi        Si datos[hijo] > datos[actual] Entonces            aux <- datos[actual]            datos[actual] <- datos[hijo]            datos[hijo] <- aux            actual <- hijo        SiNo            listo <- Verdadero        FinSi    FinMientrasFinSubProcesoAlgoritmo OrdenamientoMonticulo    Definir datos, n, i, ultimo, aux 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)    // 1) Armamos el montículo, desde el último padre hasta la raíz    Para i <- Trunc(n / 2) Hasta 1 Con Paso -1 Hacer        Hundir(datos, i, n)    FinPara    // 2) El mayor está en la raíz: lo llevamos al final y reparamos el resto    Para ultimo <- n Hasta 2 Con Paso -1 Hacer        aux <- datos[1]        datos[1] <- datos[ultimo]        datos[ultimo] <- aux        Hundir(datos, 1, ultimo - 1)    FinPara    MostrarDatos("Después: ", datos, n)FinAlgoritmo

Flowchart

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

Algoritmo OrdenamientoMonticulo
Algoritmo OrdenamientoMonticuloAlgoritmo OrdenamientoMonticuloAlgoritmo OrdenamientoMonticuloDefinir datos, n, i, ultimo, aux Como EnteroDefinir datos, n, i, ultimo,aux Como EnteroEscribir "¿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)Para i <- Trunc(n / 2) Hasta 1 Con Paso -1 HacerPara i <- Trunc(n / 2) Hasta1 Con Paso -1Hundir(datos, i, n)Hundir(datos, i, n)Para ultimo <- n Hasta 2 Con Paso -1 HacerPara ultimo <- n Hasta 2 ConPaso -1aux <- datos[1]aux <- datos[1]datos[1] <- datos[ultimo]datos[1] <- datos[ultimo]datos[ultimo] <- auxdatos[ultimo] <- auxHundir(datos, 1, ultimo - 1)Hundir(datos, 1, ultimo - 1)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
SubProceso Hundir
SubProceso HundirSíNoSíNoSíNoSíNoSubProceso Hundir(datos, raiz, tamanio)SubProceso Hundir(datos, raiz,tamanio)Definir actual, hijo, aux Como EnteroDefinir actual, hijo, aux ComoEnteroDefinir listo Como LogicoDefinir listo Como Logicoactual <- raizactual <- raizlisto <- Falsolisto <- FalsoMientras (NO listo) Y 2 * actual <= tamanio Hacer(NO listo) Y 2 *actual <= tamaniohijo <- 2 * actualhijo <- 2 * actualSi hijo + 1 <= tamanio Entonceshijo + 1 <= tamanioSi datos[hijo + 1] > datos[hijo] Entoncesdatos[hijo + 1] >datos[hijo]hijo <- hijo + 1hijo <- hijo + 1Si datos[hijo] > datos[actual] Entoncesdatos[hijo] >datos[actual]aux <- datos[actual]aux <- datos[actual]datos[actual] <- datos[hijo]datos[actual] <- datos[hijo]datos[hijo] <- auxdatos[hijo] <- auxactual <- hijoactual <- hijolisto <- Verdaderolisto <- VerdaderoFinSubProcesoFinSubProceso

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:   63 59 13 90 53 24 26 22 61 5 81 21 Después: 5 13 21 22 24 26 53 59 61 63 81 90

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 log n)
MemoryO(1)

Traits:Not stableIn place

Challenge

Print the array right after the heap is built and check that datos[1] is the largest.

Show hint

Call MostrarDatos between the two Para loops of the main algorithm.

Open in Codoritmo

Related examples

  • 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

  • Insertion Sort

    Inserts each number among the sorted ones, like arranging cards in your hand.

    Intermediate