{"id":6707,"date":"2019-06-05T07:42:01","date_gmt":"2019-06-05T05:42:01","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=6707"},"modified":"2019-06-09T07:42:40","modified_gmt":"2019-06-09T05:42:40","slug":"i1m2018-algoritmos-de-ordenacion-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2018-algoritmos-de-ordenacion-en-haskell\/","title":{"rendered":"I1M2018: Algoritmos de ordenaci\u00f3n en Haskell"},"content":{"rendered":"<p>En la primera parte de la clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-18\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> hemos comentado las soluciones de los ejercicios de la relaci\u00f3n 45 sobre algoritmos de ordenaci\u00f3n en Haskell y sus complejidades.<\/p>\n<p>Los ejercicios y su soluci\u00f3n se muestran a continuaci\u00f3n<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\n-- ---------------------------------------------------------------------\n-- Introducci\u00f3n                                                       --\n-- ---------------------------------------------------------------------\n\n-- El objetivo de esta relaci\u00f3n es presentar una recopilaci\u00f3n de los\n-- algoritmos de ordenaci\u00f3n y el estudio de su complejidad.\n-- \n-- Para realizar los ejercicios hay que tener instalada la librer\u00eda I1M\n-- que contiene la implementaci\u00f3n de TAD de las colas de prioridad. Los\n-- pasos para instalarla son los siguientes:\n-- + Descargar el paquete I1M desde http:\/\/bit.ly\/1pbnDqm\n-- + Descomprimirlo (y se crea el directorio I1M-master.zip).\n-- + Cambiar al directorio I1M-master.\n-- + Ejecutar cabal install I1M.cabal\n-- \n-- Otra forma es descargar la implementaci\u00f3n del TAD de las colas de\n-- prioridad: \n-- + ColaDePrioridadConListas.hs     que est\u00e1 en http:\/\/bit.ly\/1TJRgv8\n-- + ColaDePrioridadConMonticulos.hs que est\u00e1 en http:\/\/bit.ly\/1TJReDn\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Librer\u00edas auxiliares                                             --\n-- ---------------------------------------------------------------------\n\nimport Data.List\n\n-- Hay que elegir una implementaci\u00f3n del TAD de las colas de prioridad:\n-- import qualified ColaDePrioridadConListas as CP\n-- import qualified ColaDePrioridadConMonticulos as CP\nimport qualified I1M.ColaDePrioridad as CP\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Ordenaci\u00f3n por selecci\u00f3n                                         --\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1.1. Para ordenar una lista xs mediante el algoritmo de\n-- ordenaci\u00f3n por selecci\u00f3n se selecciona el menor elemento de xs y se\n-- le a\u00f1ade a la ordenaci\u00f3n por selecci\u00f3n de los restantes. Por ejemplo,\n-- para ordenar la lista [3,1,4,1,5,9,2] el proceso es el siguiente:\n--       ordenaPorSeleccion [3,1,4,1,5,9,2] \n--     = 1 : ordenaPorSeleccion [3,4,1,5,9,2] \n--     = 1 : 1 : ordenaPorSeleccion [3,4,5,9,2] \n--     = 1 : 1 : 2 : ordenaPorSeleccion [3,4,5,9] \n--     = 1 : 1 : 2 : 3 : ordenaPorSeleccion [4,5,9] \n--     = 1 : 1 : 2 : 3 : 4 : ordenaPorSeleccion [5,9] \n--     = 1 : 1 : 2 : 3 : 4 : 5 : ordenaPorSeleccion [9] \n--     = 1 : 1 : 2 : 3 : 4 : 5 : 9 : ordenaPorSeleccion [] \n--     = 1 : 1 : 2 : 3 : 4 : 5 : 9 : []\n--     = [1,1,2,3,4,5,9]\n--\n-- Definir la funci\u00f3n \n--    ordenaPorSeleccion :: Ord a => [a] -> [a]\n-- tal que (ordenaPorSeleccion xs) es la lista obtenida ordenando por\n-- selecci\u00f3n la lista xs. Por ejemplo,\n--    ordenaPorSeleccion [3,1,4,1,5,9,2]  ==  [1,1,2,3,4,5,9]\n-- ---------------------------------------------------------------------\n\nordenaPorSeleccion :: Ord a => [a] -> [a]\nordenaPorSeleccion [] = []\nordenaPorSeleccion xs = m : ordenaPorSeleccion (delete m xs)\n    where m = minimum xs                                      \n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1.2. Calcular los tiempos necesarios para calcular \n--     let n = k in length (ordenaPorSeleccion [n,n-1..1])\n-- para k en [1000, 2000, 3000, 4000].\n-- \n-- \u00bfCu\u00e1l es el orden de complejidad de ordenaPorSeleccion?\n-- ---------------------------------------------------------------------\n\n-- El resumen de los tiempos es\n--    k    | segs.\n--    -----+-----\n--    1000 | 0.05\n--    2000 | 0.25\n--    3000 | 0.58\n--    4000 | 1.13\n\n-- La complejidad de ordenaPorSeleccion es O(n^2).\n-- \n-- Las ecuaciones de recurrencia del coste de ordenaPorSeleccion son\n--    T(0) = 1\n--    T(n) = 1 + T(n-1) + 2n\n-- Luego, T(n) = (n+1)^2 (ver http:\/\/bit.ly\/1DGsMeW )\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1.3. Definir la funci\u00f3n\n--    ordenaPorSeleccion2 :: Ord a => [a] -> [a] \n-- tal que (ordenaPorSeleccion2 xs) es la lista xs ordenada por el\n-- algoritmo de selecci\u00f3n, pero usando un acumulador. Por ejemplo,\n--    ordenaPorSeleccion2 [3,1,4,1,5,9,2]  ==  [1,1,2,3,4,5,9]\n-- ---------------------------------------------------------------------\n\nordenaPorSeleccion2 :: Ord a => [a] -> [a] \nordenaPorSeleccion2 [] = []\nordenaPorSeleccion2 (x:xs) = aux xs x []\n    where aux [] m r = m : ordenaPorSeleccion2 r\n          aux (x:xs) m r | x < m     = aux xs x (m:r)\n                         | otherwise = aux xs m (x:r)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1.4. Calcular los tiempos necesarios para calcular \n--    let n = k in length (ordenaPorSeleccion2 [n,n-1..1])\n-- para k en [1000, 2000, 3000, 4000]\n-- ---------------------------------------------------------------------\n\n-- El resumen de los tiempos es\n--    k    | segs.\n--    -----+-----\n--    1000 | 0.39\n--    2000 | 1.53\n--    3000 | 3.48\n--    4000 | 6.35\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Ordenaci\u00f3n r\u00e1pida (Quicksort)                                    --\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2.1. Para ordenar una lista xs mediante el algoritmo de\n-- ordenaci\u00f3n r\u00e1pida se selecciona el primer elemento x de xs, se divide\n-- los restantes en los menores o iguales que x y en los mayores que x,\n-- se ordena cada una de las dos partes y se unen los resultados. Por\n-- ejemplo, para ordenar la lista [3,1,4,1,5,9,2] el proceso es el\n-- siguiente: \n--       or [3,1,4,1,5,9,2]\n--     = or [1,1,2] ++ [3] ++ or [4,5,9]  \n--     = (or [1] ++ [1] ++ or [2]) ++ [3] ++ (or [] ++ [4] ++ or [5,9])\n--     = ((or [] ++ [1] ++ or []) ++ [1] ++ (or [] ++ [2] ++ or [])) \n--       ++ [3] ++ ([] ++ [4] ++ (or [] ++ [5] ++ or [9]))\n--     = (([] ++ [1] ++ []) ++ [1] ++ ([] ++ [2] ++ [])) \n--       ++ [3] ++ ([4] ++ ([] ++ [5] ++ (or [] ++ [9] ++ or [])))\n--     = ([1] ++ [1] ++ [2] ++ \n--       ++ [3] ++ ([4] ++ ([5] ++ (or [] ++ [9] ++ or [])))\n--     = ([1] ++ [1] ++ [2] ++ \n--       ++ [3] ++ ([4] ++ ([5] ++ ([] ++ [9] ++ [])))\n--     = ([1] ++ [1] ++ [2] ++ \n--       ++ [3] ++ ([4] ++ ([5] ++ [9]))\n--     = [1,1,2,3,4,5,9]\n--\n-- Definir la funci\u00f3n \n--    ordenaRapida :: Ord a => [a] -> [a]\n-- tal que (ordenaRapida xs) es la lista obtenida ordenando por\n-- selecci\u00f3n la lista xs. Por ejemplo,\n--    ordenaRapida [3,1,4,1,5,9,2]  ==  [1,1,2,3,4,5,9]\n-- ---------------------------------------------------------------------\n\nordenaRapida :: Ord a => [a] -> [a]\nordenaRapida [] = []\nordenaRapida (x:xs) = \n    ordenaRapida menores ++ [x] ++ ordenaRapida mayores\n    where menores = [y | y <- xs, y <= x]\n          mayores = [y | y <- xs, y >  x] \n     \n-- ---------------------------------------------------------------------\n-- Ejercicio 2.2. Calcular los tiempos necesarios para calcular \n--     let n = k in length (ordenaRapida [n,n-1..1])\n-- para k en [1000, 2000, 3000, 4000]\n-- \n-- \u00bfCu\u00e1l es el orden de complejidad de ordenaRapida?\n-- ---------------------------------------------------------------------\n\n-- El resumen de los tiempos es\n--    k    | segs.\n--    -----+------\n--    1000 |  0.64\n--    2000 |  2.57\n--    3000 |  6.64\n--    4000 | 12.33\n\n-- La complejidad de ordenaRapida es O(n log(n)).\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2.3. Definir, usando un acumulador, la funci\u00f3n\n--    ordenaRapida2 :: Ord a => [a] -> [a]\n-- tal que (ordenaRapida2 xs) es la lista obtenida ordenando xs\n-- por el procedimiento de ordenaci\u00f3n r\u00e1pida. Por ejemplo, \n--    ordenaRapida2 [3,1,4,1,5,9,2]  ==  [1,1,2,3,4,5,9]\n-- ---------------------------------------------------------------------\n\nordenaRapida2 :: Ord a => [a] -> [a]\nordenaRapida2 xs = aux xs []\n    where aux [] s     = s\n          aux (x:xs) s = aux menores (x : aux mayores s)\n              where menores = [y | y <- xs, y <= x]\n                    mayores = [y | y <- xs, y >  x] \n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2.4. Calcular los tiempos necesarios para calcular \n--     let n = k in length (ordenaRapida2 [n,n-1..1])\n-- para k en [1000, 2000, 3000, 4000]\n-- ---------------------------------------------------------------------\n\n-- El resumen de los tiempos es\n--    k    | segs.\n--    -----+------\n--    1000 |  0.56\n--    2000 |  2.42\n--    3000 |  5.87\n--    4000 | 10.93\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Ordenaci\u00f3n por inserci\u00f3n                                         --\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3.1. Para ordenar una lista xs mediante el algoritmo de\n-- ordenaci\u00f3n por inserci\u00f3n se selecciona el primer elemento x de xs, se\n-- ordena el resto de xs y se inserta x en su lugar. Por ejemplo, para\n-- ordenar la lista [3,1,4,1,5,9,2] el proceso es el siguiente: \n--      ordenaPorInsercion [3,1,4,1,5,9,2]\n--    = 3 : ordenaPorInsercion [1,4,1,5,9,2]\n--    = 3 : 1 : ordenaPorInsercion [4,1,5,9,2]\n--    = 3 : 1 : 4 : ordenaPorInsercion [1,5,9,2]\n--    = 3 : 1 : 4 : 1 : ordenaPorInsercion [5,9,2]\n--    = 3 : 1 : 4 : 1 : 5 : ordenaPorInsercion [9,2]\n--    = 3 : 1 : 4 : 1 : 5 : 9 : ordenaPorInsercion [2]\n--    = 3 : 1 : 4 : 1 : 5 : 9 : 2 : ordenaPorInsercion []\n--    = 3 : 1 : 4 : 1 : 5 : 9 : 2 : []\n--    = 3 : 1 : 4 : 1 : 5 : 9 : [2]\n--    = 3 : 1 : 4 : 1 : 5 : [2,9]\n--    = 3 : 1 : 4 : 1 : [2,5,9]\n--    = 3 : 1 : 4 : [1,2,5,9]\n--    = 3 : 1 : [1,2,4,5,9]\n--    = 3 : [1,1,2,4,5,9]\n--    = [1,1,2,3,4,5,9]\n--\n-- Definir la funci\u00f3n \n--    ordenaPorInsercion :: Ord a => [a] -> [a]\n-- tal que (ordenaPorInsercion xs) es la lista obtenida ordenando por\n-- selecci\u00f3n la lista xs. Por ejemplo,\n--    ordenaPorInsercion [3,1,4,1,5,9,2]  ==  [1,1,2,3,4,5,9]\n-- ---------------------------------------------------------------------\n\nordenaPorInsercion :: Ord a => [a] -> [a]\nordenaPorInsercion []     = []\nordenaPorInsercion (x:xs) = inserta x (ordenaPorInsercion xs) \n\n-- (inserta x xs) inserta el elemento x despu\u00e9s de los elementos de xs\n-- que son menores o iguales que x. Por ejemplo,\n--    inserta 5 [3,2,6,4]  ==  [3,2,5,6,4]\ninserta :: Ord a => a -> [a] -> [a]\ninserta y []                   = [y]\ninserta y l@(x:xs) | y <= x    = y : l\n                   | otherwise = x : inserta y xs\n\n-- 2\u00aa definici\u00f3n de inserta: \ninserta2 :: Ord a => a -> [a] -> [a]\ninserta2 x xs = takeWhile (<= x) xs ++ [x] ++ dropWhile (<=x) xs\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3.2. Calcular los tiempos necesarios para calcular \n--     let n = k in length (ordenaPorInsercion [n,n-1..1])\n-- para k en [1000, 2000, 3000, 4000]\n--\n-- \u00bfCu\u00e1l es la complejidad de ordenaPorInsercion?\n-- ---------------------------------------------------------------------\n\n-- El resumen de los tiempos es\n--    k    | segs.\n--    -----+-----\n--    1000 | 0.39\n--    2000 | 1.53\n--    3000 | 3.49\n--    4000 | 6.32\n\n-- La complejidad de ordenaPorInsercion es O(n^2)\n-- \n-- Las ecuaciones de recurrencia del coste de ordenaPorInsercion son\n--    T(0) = 1\n--    T(n) = 4n + T(n-1)\n-- Luego, T(n) = 2n(n+1)+1 (ver http:\/\/bit.ly\/19FmQq4 )\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3.3. Definir, por plegados, la funci\u00f3n\n--    ordenaPorInsercion2 :: Ord a => [a] -> [a]\n-- tal que (ordenaPorInsercion2 xs) es la lista obtenida ordenando xs\n-- por el procedimiento de ordenaci\u00f3n por inserci\u00f3n. Por ejemplo, \n--    ordenaPorInsercion2 [3,1,4,1,5,9,2]  ==  [1,1,2,3,4,5,9]\n-- ---------------------------------------------------------------------\n\nordenaPorInsercion2 :: Ord a => [a] -> [a]\nordenaPorInsercion2 = foldr inserta []\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3.2. Calcular los tiempos necesarios para calcular \n--     let n = k in length (ordenaPorInsercion2 [n,n-1..1])\n-- para k en [1000, 2000, 3000, 4000]\n-- ---------------------------------------------------------------------\n\n-- El resumen de los tiempos es\n--    k    | segs.\n--    -----+------\n--    1000 | 0.38\n--    2000 | 1.54\n--    3000 | 3.46\n--    4000 | 6.29\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Ordenaci\u00f3n por mezcla (\"Mergesort\")                              --\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4.1. Para ordenar una lista xs mediante el algoritmo de\n-- ordenaci\u00f3n por mezcla se divide xs por la mitad, se ordena cada una\n-- de las partes y se mezclan los resultados. Por ejemplo, para\n-- ordenar la lista [3,1,4,1,5,9,2] el proceso es el siguiente: \n--      om [3,1,4,1,5,9,2]\n--    = m (om [3,1,4]) (om 1,5,9,2])  \n--    = m (m (om [3]) (om [1,4])) (m (om [1,5]) (om [9,2]))\n--    = m (m [3] (m (om [1]) (om [4]))) \n--        (m (m (om [1]) (om [5])) (m (om [9]) (om [2])))\n--    = m (m [3] (m [1] [4])) \n--        (m (m [1] [5]) (m [9] [2]))\n--    = m (m [3] [1,4]) (m [1,5] [2,9])\n--    = m [1,3,4] [1,2,5,9]\n--    = [1,1,2,3,4,5,9]\n-- donde om es ordenaPorMezcla y m es mezcla.\n--\n-- Definir la funci\u00f3n \n--    ordenaPorMezcla :: Ord a => [a] -> [a]\n-- tal que (ordenaPorMezcla xs) es la lista obtenida ordenando por\n-- selecci\u00f3n la lista xs. Por ejemplo,\n--    ordenaPorMezcla [3,1,4,1,5,9,2]  ==  [1,1,2,3,4,5,9]\n-- ---------------------------------------------------------------------\n\nordenaPorMezcla :: Ord a => [a] -> [a]\nordenaPorMezcla []  = []\nordenaPorMezcla [x] = [x]\nordenaPorMezcla l   = mezcla (ordenaPorMezcla l1) (ordenaPorMezcla l2)\n    where l1 = take k l\n          l2 = drop k l\n          k  = length l `div` 2 \n\n-- (mezcla xs ys) es la lista obtenida mezclando xs e ys. Por ejemplo,\n--    mezcla [1,3] [2,4,6]  ==  [1,2,3,4,6]\nmezcla :: Ord a => [a] -> [a] -> [a]\nmezcla [] b = b\nmezcla a [] = a\nmezcla a@(x:xs) b@(y:ys) | x <= y    = x : mezcla xs b\n                         | otherwise = y : mezcla a ys\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4.2. Calcular los tiempos necesarios para calcular \n--     let n = k in length (ordenaPorMezcla [n,n-1..1])\n-- para k en [1000, 2000, 3000, 4000]\n--\n-- \u00bfCu\u00e1l es la complejidad de ordenaPorMezcla?\n-- ---------------------------------------------------------------------\n\n-- El resumen de los tiempos es\n--    k    | segs.\n--    -----+-----\n--    1000 | 0.02\n--    2000 | 0.03\n--    3000 | 0.05\n--    4000 | 0.06\n\n-- La complejidad de ordenaPorMezcla es O(n log(n)).\n-- \n-- Las ecuaciones de recurrencia del coste de ordenaPorMezcla son\n--    T(0) = 1\n--    T(1) = 1\n--    T(n) = n + 2*T(n\/n)\n-- Luego, T(n) = (c*n)\/2+(n log(n))\/(log(2)) (ver http:\/\/bit.ly\/1EyUTYG )\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4.3. Otra forma de ordenar una lista xs mediante el\n-- algoritmo de ordenaci\u00f3n por mezcla consiste en dividir xs en listas\n-- unitarias y mezclar los resultados. Por ejemplo, para\n-- ordenar la lista [3,1,4,1,5,9,2] el proceso es el siguiente: \n--      om [3,1,4,1,5,9,2]\n--    = mp [[3],[1],[4],[1],[5],[9],[2]]\n--    = mp [[1,3],[1,4],[5,9],[2]]\n--    = mp [[1,1,3,4],[2,5,9]]\n--    = [1,1,2,3,4,5,9]\n-- donde om es ordenaPorMezcla y mp es mezclaPares.\n--\n-- Definir la funci\u00f3n \n--    ordenaPorMezcla2 :: Ord a => [a] -> [a]\n-- tal que (ordenaPorMezcla2 xs) es la lista obtenida ordenando por\n-- mezcla la lista xs. Por ejemplo,\n--    ordenaPorMezcla2 [3,1,4,1,5,9,2]  ==  [1,1,2,3,4,5,9]\n-- ---------------------------------------------------------------------\n\nordenaPorMezcla2 :: Ord a => [a] -> [a]\nordenaPorMezcla2 l = aux (divide l)\n    where aux [r] = r\n          aux l   = aux (mezclaPares l)\n\n-- (divide xs) es la lista de de las listas unitarias formadas por los\n-- elementos de xs. Por ejemplo,\n--    divide [3,1,4,1,5,9,2,8]  ==  [[3],[1],[4],[1],[5],[9],[2],[8]]\ndivide :: Ord a => [a] -> [[a]]\ndivide xs = [[x] | x <- xs]\n\n-- Tambi\u00e9n se puede definir por recursi\u00f3n\ndivide2 :: Ord a => [a] -> [[a]]\ndivide2 []     = []\ndivide2 (x:xs) = [x] : divide2 xs\n\n-- (mezclaPares xs) es la lista obtenida mezclando los pares de\n-- elementos consecutivos de xs. Por ejemplo,\n--    ghci> mezclaPares [[3],[1],[4],[1],[5],[9],[2],[8]]\n--    [[1,3],[1,4],[5,9],[2,8]]\n--    ghci> mezclaPares [[1,3],[1,4],[5,9],[2,8]]\n--    [[1,1,3,4],[2,5,8,9]]\n--    ghci> mezclaPares [[1,1,3,4],[2,5,8,9]]\n--    [[1,1,2,3,4,5,8,9]]\n--    ghci> mezclaPares [[1],[3],[2]]\n--    [[1,3],[2]]\nmezclaPares :: (Ord a) => [[a]] -> [[a]]\nmezclaPares []           = []\nmezclaPares [x]          = [x]\nmezclaPares (xs:ys:zss)  = mezcla xs ys : mezclaPares zss\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4.4. Calcular los tiempos necesarios para calcular \n--     let n = k in length (ordenaPorMezcla2 [n,n-1..1])\n-- para k en [1000, 2000, 3000, 4000]\n-- ---------------------------------------------------------------------\n\n-- El resumen de los tiempos es\n--    k    | segs.\n--    -----+-----\n--    1000 | 0.02\n--    2000 | 0.03\n--    3000 | 0.03\n--    4000 | 0.05\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Ordenaci\u00f3n por mont\u00edculos (\"heapsort\")                           --\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5.1. El procedimiento de ordenaci\u00f3n de una lista por\n-- mont\u00edculos consiste en almacenar todos los elementos del vector a\n-- ordenar en un mont\u00edculo (heap), y luego extraer el nodo que queda\n-- como nodo ra\u00edz del mont\u00edculo (cima) en sucesivas iteraciones\n-- obteniendo el conjunto ordenado.  \n-- \n-- Usando la implementaci\u00f3n de las colas de prioridad mediante\n-- mont\u00edculos (que se encuentra en la librer\u00eda I1M.ColaDePrioridad),\n-- definir la funci\u00f3n \n--    ordenaPorMonticulos :: Ord a => [a] -> [a]\n-- tal que (ordenaPorMonticulos xs) es la lista obtenida ordenando xs\n-- por el procedimiento de ordenaci\u00f3n por mont\u00edculos. Por ejemplo, \n--    ordenaPorMonticulos [3,1,4,1,5,9,2]  ==  [1,1,2,3,4,5,9]\n-- ---------------------------------------------------------------------\n\nordenaPorMonticulos :: Ord a => [a] -> [a]\nordenaPorMonticulos xs = aux (creaCP xs) where\n    aux cp | CP.esVacia cp = []\n           | otherwise     = CP.primero cp : aux (CP.resto cp)\n\n-- (creaCP xs) es la cola de prioridad correspondiente a la lista\n-- xs. Por ejemplo,\n--    ghci> creaCP [3,1,4,1,5,9,2,8]\n--    CP (M 1 2 \n--          (M 1 2 \n--             (M 2 2 \n--                (M 8 1 Vacio Vacio) \n--                (M 5 1 \n--                   (M 9 1 Vacio Vacio) \n--                   Vacio)) \n--             (M 4 1 Vacio Vacio)) \n--          (M 3 1 Vacio Vacio))\ncreaCP :: Ord a => [a] -> CP.CPrioridad a\ncreaCP xs = foldr CP . inserta CP . vacia xs\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5.2. Calcular los tiempos necesarios para calcular \n--     let n = k in length (ordenaPorMonticulos [n,n-1..1])\n-- para k en [1000, 2000, 3000, 4000]\n--\n-- \u00bfCu\u00e1l es la complejidad de ordenaPorMonticulos?\n-- ---------------------------------------------------------------------\n\n-- El resumen de los tiempos es\n--    k    | segs.\n--    -----+-----\n--    1000 | 0.02\n--    2000 | 0.03\n--    3000 | 0.04\n--    4000 | 0.05\n\n-- La complejidad de ordenaPorMonticulos es O(n log(n)).\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En la primera parte de la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas hemos comentado las soluciones de los ejercicios de la relaci\u00f3n 45 sobre algoritmos de ordenaci\u00f3n en Haskell y sus complejidades. Los ejercicios y su soluci\u00f3n se muestran a continuaci\u00f3n<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[320],"tags":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":false,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/6707"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/comments?post=6707"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/6707\/revisions"}],"predecessor-version":[{"id":6708,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/6707\/revisions\/6708"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=6707"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=6707"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=6707"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}