{"id":4861,"date":"2015-04-13T16:47:18","date_gmt":"2015-04-13T14:47:18","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=4861"},"modified":"2015-04-14T11:49:15","modified_gmt":"2015-04-14T09:49:15","slug":"i1m2014-algoritmos-de-ordenacion-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2014-algoritmos-de-ordenacion-en-haskell\/","title":{"rendered":"I1M2014: Algoritmos de ordenaci\u00f3n en Haskell"},"content":{"rendered":"<p>En la clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-14\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> hemos comentado las soluciones a los ejercicios de la relaci\u00f3n 29 sobre algoritmos de ordenaci\u00f3n en Haskell.<\/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-- ---------------------------------------------------------------------\n-- \u00a7 Librer\u00edas auxiliares                                             --\n-- ---------------------------------------------------------------------\n\nimport Data.List\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 xs = foldr inserta [] xs \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-- selecci\u00f3n 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 clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas hemos comentado las soluciones a los ejercicios de la relaci\u00f3n 29 sobre algoritmos de ordenaci\u00f3n en Haskell. Los ejercicios y su soluci\u00f3n se muestran a continuaci\u00f3n<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","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":[238],"tags":[244,270,305],"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\/4861"}],"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=4861"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4861\/revisions"}],"predecessor-version":[{"id":4863,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4861\/revisions\/4863"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=4861"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=4861"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=4861"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}