Skip to content
ExamplesEspañolWorkspace →

Shell Sort

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

Level
Advanced
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

It first insertion-sorts the elements that are a big gap apart, so numbers that are way out of place travel far in one move. Then it halves the gap until it reaches 1, which is an ordinary insertion sort on nearly sorted data. With these gaps it usually runs close to O(n√n), and the worst case is O(n²).

Code

shell-sort.psc · 48 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 OrdenamientoShell    Definir datos, n, i, j, actual, salto 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)    // Empezamos comparando elementos lejanos: los muy desordenados viajan rápido    salto <- Trunc(n / 2)    Mientras salto > 0 Hacer        Escribir "Pasada con salto ", salto        // Inserción, pero entre elementos separados por "salto" posiciones        Para i <- salto + 1 Hasta n Hacer            actual <- datos[i]            j <- i            ubicado <- Falso            Mientras j > salto Y (NO ubicado) Hacer                Si datos[j - salto] > actual Entonces                    datos[j] <- datos[j - salto]                    j <- j - salto                SiNo                    ubicado <- Verdadero                FinSi            FinMientras            datos[j] <- actual        FinPara        // La última pasada (salto 1) es una inserción común sobre datos casi ordenados        salto <- Trunc(salto / 2)    FinMientras    MostrarDatos("Después: ", datos, n)FinAlgoritmo

Flowchart

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

Algoritmo OrdenamientoShell
Algoritmo OrdenamientoShellSíNoSíNoSíNoAlgoritmo OrdenamientoShellAlgoritmo OrdenamientoShellDefinir datos, n, i, j, actual, salto Como EnteroDefinir datos, n, i, j,actual, salto Como EnteroDefinir 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)salto <- Trunc(n / 2)salto <- Trunc(n / 2)Mientras salto > 0 Hacersalto > 0Escribir "Pasada con salto ", saltoEscribir "Pasada con salto ",saltoPara i <- salto + 1 Hasta n HacerPara i <- salto + 1 Hasta nactual <- datos[i]actual <- datos[i]j <- ij <- iubicado <- Falsoubicado <- FalsoMientras j > salto Y (NO ubicado) Hacerj > salto Y (NOubicado)Si datos[j - salto] > actual Entoncesdatos[j - salto] >actualdatos[j] <- datos[j - salto]datos[j] <- datos[j - salto]j <- j - saltoj <- j - saltoubicado <- Verdaderoubicado <- Verdaderodatos[j] <- actualdatos[j] <- actualsalto <- Trunc(salto / 2)salto <- Trunc(salto / 2)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

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: 16Antes:   53 1 57 68 74 96 25 65 80 33 66 15 27 77 36 90 Pasada con salto 8Pasada con salto 4Pasada con salto 2Pasada con salto 1Después: 1 15 25 27 33 36 53 57 65 66 68 74 77 80 90 96

Complexity

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

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

Traits:Not stableIn place

Challenge

Try dividing the gap by 3 instead of 2 and compare how many passes it makes.

Show hint

Change the two Trunc(... / 2) lines, and make sure the last pass still uses a gap of 1.

Open in Codoritmo

Related examples

  • Heap Sort

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

    Advanced

  • Bubble Sort

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

    Intermediate

  • Linear vs. Binary Search

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

    Intermediate