Skip to content
ExamplesEspañolWorkspace →

Selection Sort

Finds the smallest of the remaining numbers and puts it in its place.

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

Run, change and debug this example in your browser.

What you'll learn

On round i it looks for the smallest value between positions i and n and moves it to position i with a single swap. It always scans everything that's left, so it makes about n²/2 comparisons even if the data is already sorted: O(n²) in every case, but at most n - 1 swaps.

Code

selection-sort.psc · 44 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 OrdenamientoSeleccion    Definir datos, n, i, j, minimo, aux, intercambios 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)    intercambios <- 0    // "Con Paso 1" evita que el Para cuente hacia atrás cuando n = 1    Para i <- 1 Hasta n - 1 Con Paso 1 Hacer        // Buscamos el menor entre las posiciones i y n        minimo <- i        Para j <- i + 1 Hasta n Hacer            Si datos[j] < datos[minimo] Entonces                minimo <- j            FinSi        FinPara        // Y lo llevamos a la posición i con un solo intercambio        Si minimo <> i Entonces            aux <- datos[i]            datos[i] <- datos[minimo]            datos[minimo] <- aux            intercambios <- intercambios + 1        FinSi    FinPara    MostrarDatos("Después: ", datos, n)    Escribir "Intercambios realizados: ", intercambiosFinAlgoritmo

Flowchart

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

Algoritmo OrdenamientoSeleccion
Algoritmo OrdenamientoSeleccionSíNoSíNoAlgoritmo OrdenamientoSeleccionAlgoritmo OrdenamientoSeleccionDefinir datos, n, i, j, minimo, aux, intercambios Como EnteroDefinir datos, n, i, j,minimo, aux, intercambios 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)intercambios <- 0intercambios <- 0Para i <- 1 Hasta n - 1 Con Paso 1 HacerPara i <- 1 Hasta n - 1 ConPaso 1minimo <- iminimo <- iPara j <- i + 1 Hasta n HacerPara j <- i + 1 Hasta nSi datos[j] < datos[minimo] Entoncesdatos[j] <datos[minimo]minimo <- jminimo <- jSi minimo <> i Entoncesminimo <> iaux <- datos[i]aux <- datos[i]datos[i] <- datos[minimo]datos[i] <- datos[minimo]datos[minimo] <- auxdatos[minimo] <- auxintercambios <- intercambios + 1intercambios <- intercambios +1MostrarDatos("Después: ", datos, n)MostrarDatos("Después: ",datos, n)Escribir "Intercambios realizados: ", intercambiosEscribir "Intercambiosrealizados: ", intercambiosFinAlgoritmoFinAlgoritmo
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:   68 56 75 80 18 35 34 44 6 37 11 41 Después: 6 11 18 34 35 37 41 44 56 68 75 80 Intercambios realizados: 9

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:Not stableIn place

Challenge

Also count the comparisons and check them against n * (n - 1) / 2.

Show hint

Add 1 to a counter right before the Si that compares datos[j] with datos[minimo].

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

  • Merge Sort

    Splits the array in halves, sorts each one recursively and merges them.

    Advanced