Saltar al contenido
EjemplosEnglishEspacio →

Ordenamiento rápido (Quicksort)

Elige un pivote, separa los menores de los mayores y ordena cada lado con recursión.

Nivel
Avanzado
Tema:
Ordenamiento y búsqueda
Conceptos:
Entrada y salida
Arreglos
SubProcesos
Funciones
Recursión
Repetir
Si
Azar
Abrir en Codoritmo

Ejecuta, modifica y depura este ejemplo en el navegador.

Lo que aprenderás

Particionar usa el método de Hoare: dos índices avanzan desde los extremos hacia el centro y se intercambian cuando cada uno encuentra un valor del lado equivocado del pivote. Después cada parte se ordena con la misma idea. Si el pivote parte el arreglo más o menos por la mitad cuesta O(n log n); si siempre cae en un extremo, O(n²). No necesita arreglo extra, solo la pila de llamadas (O(log n)).

Código

quicksort.psc · 63 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], ")"    FinSiFinSubProceso// Partición de Hoare: deja a la izquierda los valores <= pivote y a la derecha// los >= pivote, y devuelve dónde termina la parte izquierda.Funcion corte <- Particionar(datos, izquierda, derecha)    Definir corte, pivote, i, j, aux Como Entero    // Usamos el elemento del medio como pivote    pivote <- datos[Trunc((izquierda + derecha) / 2)]    i <- izquierda - 1    j <- derecha + 1    Repetir        // i avanza hasta encontrar uno que no debería estar a la izquierda        Repetir            i <- i + 1        Hasta Que datos[i] >= pivote        // j retrocede hasta encontrar uno que no debería estar a la derecha        Repetir            j <- j - 1        Hasta Que datos[j] <= pivote        // Si no se cruzaron, los intercambiamos y seguimos        Si i < j Entonces            aux <- datos[i]            datos[i] <- datos[j]            datos[j] <- aux        FinSi    Hasta Que i >= j    corte <- jFinFuncionSubProceso OrdenarRapido(datos, izquierda, derecha)    Definir corte Como Entero    Si izquierda < derecha Entonces        corte <- Particionar(datos, izquierda, derecha)        // Cada lado se ordena por separado, con la misma idea        OrdenarRapido(datos, izquierda, corte)        OrdenarRapido(datos, corte + 1, derecha)    FinSiFinSubProcesoAlgoritmo Quicksort    Definir datos, n, i 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)    OrdenarRapido(datos, 1, n)    MostrarDatos("Después: ", datos, n)FinAlgoritmo

Diagrama de flujo

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

Algoritmo Quicksort
Algoritmo QuicksortAlgoritmo QuicksortAlgoritmo QuicksortDefinir datos, n, i Como EnteroDefinir datos, n, i 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)OrdenarRapido(datos, 1, n)OrdenarRapido(datos, 1, n)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
Funcion Particionar
Funcion ParticionarNoNoSíSíNoSíNoSíFuncion corte <- Particionar(datos, izquierda, derecha)Funcion corte <-Particionar(datos, izquierda,…Definir corte, pivote, i, j, aux Como EnteroDefinir corte, pivote, i, j,aux Como Enteropivote <- datos[Trunc((izquierda + derecha) / 2)]pivote <-datos[Trunc((izquierda +derecha) / 2)]i <- izquierda - 1i <- izquierda - 1j <- derecha + 1j <- derecha + 1i <- i + 1i <- i + 1Hasta Que datos[i] >= pivotedatos[i] >= pivotej <- j - 1j <- j - 1Hasta Que datos[j] <= pivotedatos[j] <= pivoteSi i < j Entoncesi < jaux <- datos[i]aux <- datos[i]datos[i] <- datos[j]datos[i] <- datos[j]datos[j] <- auxdatos[j] <- auxHasta Que i >= ji >= jcorte <- jcorte <- jFinFuncion (devuelve corte)FinFuncion (devuelve corte)
SubProceso OrdenarRapido
SubProceso OrdenarRapidoSíNoSubProceso OrdenarRapido(datos, izquierda, derecha)SubProceso OrdenarRapido(datos,izquierda, derecha)Definir corte Como EnteroDefinir corte Como EnteroSi izquierda < derecha Entoncesizquierda < derechacorte <- Particionar(datos, izquierda, derecha)corte <- Particionar(datos,izquierda, derecha)OrdenarRapido(datos, izquierda, corte)OrdenarRapido(datos,izquierda, corte)OrdenarRapido(datos, corte + 1, derecha)OrdenarRapido(datos, corte +1, derecha)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: 12Antes:   57 95 53 48 81 13 78 10 53 4 56 3 Después: 3 4 10 13 48 53 53 56 57 78 81 95

Complejidad

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

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

Características:No estableEn el lugar

Desafío

Usa como pivote un elemento al azar del tramo en lugar del del medio.

Ver pista

Aleatorio(izquierda, derecha) da una posición del tramo; guarda datos[esa posición] en pivote.

Abrir en Codoritmo

Ejemplos relacionados