Skip to content
ExamplesEspañolWorkspace →

Insertion Sort

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

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

Run, change and debug this example in your browser.

What you'll learn

The left part of the array is always sorted. Each new number is kept in actual, the larger ones shift one place to the right, and actual drops into the gap. With nearly sorted data it barely shifts anything (O(n)); on average and in the worst case it's O(n²).

Code

insertion-sort.psc · 46 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], ")"    FinSiFinSubProcesoAlgoritmo OrdenamientoInsercion    Definir datos, n, i, j, actual, desplazamientos Como Entero    Definir ubicado Como Logico    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)    desplazamientos <- 0    // Las posiciones 1 a i-1 ya están ordenadas; insertamos datos[i] entre ellas    Para i <- 2 Hasta n Con Paso 1 Hacer        actual <- datos[i]        j <- i - 1        ubicado <- Falso        // Corremos un lugar a la derecha los que son mayores que actual        Mientras j >= 1 Y (NO ubicado) Hacer            Si datos[j] > actual Entonces                datos[j + 1] <- datos[j]                j <- j - 1                desplazamientos <- desplazamientos + 1            SiNo                ubicado <- Verdadero            FinSi        FinMientras        // El hueco que quedó es su lugar        datos[j + 1] <- actual    FinPara    MostrarDatos("Después: ", datos, n)    Escribir "Desplazamientos: ", desplazamientosFinAlgoritmo

Flowchart

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

Algoritmo OrdenamientoInsercion
Algoritmo OrdenamientoInsercionSíNoSíNoAlgoritmo OrdenamientoInsercionAlgoritmo OrdenamientoInsercionDefinir datos, n, i, j, actual, desplazamientos Como EnteroDefinir datos, n, i, j,actual, desplazamientos ComoEnteroDefinir ubicado Como LogicoDefinir ubicado Como LogicoEscribir "¿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)desplazamientos <- 0desplazamientos <- 0Para i <- 2 Hasta n Con Paso 1 HacerPara i <- 2 Hasta n Con Paso1actual <- datos[i]actual <- datos[i]j <- i - 1j <- i - 1ubicado <- Falsoubicado <- FalsoMientras j >= 1 Y (NO ubicado) Hacerj >= 1 Y (NOubicado)Si datos[j] > actual Entoncesdatos[j] > actualdatos[j + 1] <- datos[j]datos[j + 1] <- datos[j]j <- j - 1j <- j - 1desplazamientos <- desplazamientos + 1desplazamientos <-desplazamientos + 1ubicado <- Verdaderoubicado <- Verdaderodatos[j + 1] <- actualdatos[j + 1] <- actualMostrarDatos("Después: ", datos, n)MostrarDatos("Después: ",datos, n)Escribir "Desplazamientos: ", desplazamientosEscribir "Desplazamientos: ",desplazamientosFinAlgoritmoFinAlgoritmo
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

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:   45 56 40 56 96 77 8 60 39 86 74 43 Después: 8 39 40 43 45 56 56 60 74 77 86 96 Desplazamientos: 30

Complexity

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

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

Traits:StableIn place

Challenge

Generate data that's already sorted (for example datos[i] <- i) and see how many shifts it makes.

Show hint

Replace Aleatorio(1, 99) with i in the first Para; the shift counter should end at 0.

Open in Codoritmo

Related examples

  • Bubble Sort

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

    Intermediate

  • Heap Sort

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

    Advanced

  • Linear vs. Binary Search

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

    Intermediate