Skip to content
ExamplesEspañolWorkspace →

Bubble Sort

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

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

Each pass compares neighbors and swaps them when they're out of order, so the largest one "bubbles up" to the end. If a pass makes no swaps, everything is already sorted and the Mientras loop ends early. That's why it costs O(n) when the data comes sorted and O(n²) on average and in the worst case.

Code

bubble-sort.psc · 43 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 OrdenamientoBurbuja    Definir datos, n, i, j, aux, pasadas Como Entero    Definir huboCambios 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)    // En cada pasada, el mayor "sube" hasta su lugar al final    pasadas <- 0    huboCambios <- Verdadero    Mientras huboCambios Y pasadas < n - 1 Hacer        pasadas <- pasadas + 1        huboCambios <- Falso        Para j <- 1 Hasta n - pasadas Hacer            Si datos[j] > datos[j + 1] Entonces                aux <- datos[j]                datos[j] <- datos[j + 1]                datos[j + 1] <- aux                huboCambios <- Verdadero            FinSi        FinPara        // Si una pasada no cambió nada, el arreglo ya está ordenado    FinMientras    MostrarDatos("Después: ", datos, n)    Escribir "Pasadas necesarias: ", pasadasFinAlgoritmo

Flowchart

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

Algoritmo OrdenamientoBurbuja
Algoritmo OrdenamientoBurbujaSíNoSíNoAlgoritmo OrdenamientoBurbujaAlgoritmo OrdenamientoBurbujaDefinir datos, n, i, j, aux, pasadas Como EnteroDefinir datos, n, i, j, aux,pasadas Como EnteroDefinir huboCambios Como LogicoDefinir huboCambios ComoLogicoEscribir "¿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)pasadas <- 0pasadas <- 0huboCambios <- VerdaderohuboCambios <- VerdaderoMientras huboCambios Y pasadas < n - 1 HacerhuboCambios Ypasadas < n - 1pasadas <- pasadas + 1pasadas <- pasadas + 1huboCambios <- FalsohuboCambios <- FalsoPara j <- 1 Hasta n - pasadas HacerPara j <- 1 Hasta n -pasadasSi datos[j] > datos[j + 1] Entoncesdatos[j] > datos[j +1]aux <- datos[j]aux <- datos[j]datos[j] <- datos[j + 1]datos[j] <- datos[j + 1]datos[j + 1] <- auxdatos[j + 1] <- auxhuboCambios <- VerdaderohuboCambios <- VerdaderoMostrarDatos("Después: ", datos, n)MostrarDatos("Después: ",datos, n)Escribir "Pasadas necesarias: ", pasadasEscribir "Pasadas necesarias:", pasadasFinAlgoritmoFinAlgoritmo
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:   18 31 82 57 10 74 26 85 29 44 60 91 Después: 10 18 26 29 31 44 57 60 74 82 85 91 Pasadas necesarias: 6

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

Sort the numbers from largest to smallest.

Show hint

Changing the comparison operator inside the Si is enough.

Open in Codoritmo

Related examples

  • Insertion Sort

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

    Intermediate

  • Shell Sort

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

    Advanced

  • Heap Sort

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

    Advanced