Saltar al contenido
EjemplosEnglishEspacio →

Ordenamiento Shell

Una inserción entre elementos lejanos, con un salto que se achica en cada pasada.

Nivel
Avanzado
Tema:
Ordenamiento y búsqueda
Conceptos:
Entrada y salida
Arreglos
Para
Mientras
Si
Lógicos
Azar
SubProcesos
Abrir en Codoritmo

Ejecuta, modifica y depura este ejemplo en el navegador.

Lo que aprenderás

Primero ordena por inserción los elementos separados por un salto grande, para que los números muy fuera de lugar viajen lejos de una vez. Después divide el salto a la mitad hasta llegar a 1, que es una inserción común sobre datos casi ordenados. Con estos saltos suele andar cerca de O(n√n), y el peor caso es O(n²).

Código

shell-sort.psc · 48 líneas
// 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

Diagrama de flujo

Cada bloque del diagrama corresponde a una instrucción del código.

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

Ejemplo de ejecución

Esto muestra el programa al ejecutarlo. Las respuestas escritas por el usuario aparecen resaltadas.

¿Cuántos números quieres ordenar? (1 a 512)Respuesta del usuario: 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

Complejidad

Cuánto trabajo y memoria necesita según la cantidad de datos (n).

Complejidad
CasoCosto
MejorO(n log n)
PromedioO(n√n)
PeorO(n²)
MemoriaO(1)

Características:No estableEn el lugar

Desafío

Prueba dividir el salto por 3 en lugar de 2 y compara cuántas pasadas hace.

Ver pista

Cambia las dos líneas con Trunc(... / 2); cuida que la última pasada siga siendo con salto 1.

Abrir en Codoritmo

Ejemplos relacionados