{"id":2364,"date":"2012-11-27T16:49:57","date_gmt":"2012-11-27T16:49:57","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=2364"},"modified":"2013-03-08T05:47:38","modified_gmt":"2013-03-08T05:47:38","slug":"i1m2012-ordenacion-por-mezcla","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2012-ordenacion-por-mezcla\/","title":{"rendered":"I1M2012: Ordenaci\u00f3n por mezcla"},"content":{"rendered":"<p>En la segunda parte de la clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-12\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> hemos comentado las soluciones de los ejercicios de la <a href=\"https:\/\/www.glc.us.es\/~jalonso\/ejerciciosI1M2012G2\/images\/2\/20\/Rel_8.hs\" >8\u00aa relaci\u00f3n<\/a> que tratan de la ordenaci\u00f3n por mezcla.<\/p>\n<p>Los ejercicios, y sus soluciones, se muestran a continuaci\u00f3n:<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\r\n-- ---------------------------------------------------------------------\r\n-- Introducci\u00f3n                                                       --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- El objetivo de esta relaci\u00f3n es definir la ordenaci\u00f3n por mezclas y\r\n-- comprobar su correcci\u00f3n con QuickCheck.\r\n\r\nimport Test.QuickCheck\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 14.1. Definir por recursi\u00f3n la funci\u00f3n\r\n--    mezcla :: Ord a => [a] -> [a] -> [a] \r\n-- tal que (mezcla xs ys) es la lista obtenida mezclando las listas\r\n-- ordenadas xs e ys. Por ejemplo,  \r\n--    mezcla [2,5,6] [1,3,4]  ==  [1,2,3,4,5,6]\r\n-- ---------------------------------------------------------------------\r\n\r\nmezcla :: Ord a => [a] -> [a] -> [a] \r\nmezcla []     ys                 = ys\r\nmezcla xs     []                 = xs\r\nmezcla (x:xs) (y:ys) | x <= y    = x : mezcla xs (y:ys)\r\n                     | otherwise = y : mezcla (x:xs) ys\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 14.2. Definir la funci\u00f3n \r\n--    mitades :: [a] -> ([a],[a]) \r\n-- tal que (mitades xs) es el par formado por las dos mitades en que se\r\n-- divide xs tales que sus longitudes difieren como m\u00e1ximo en uno. Por\r\n-- ejemplo, \r\n--    mitades [2,3,5,7,9]  ==  ([2,3],[5,7,9])\r\n-- ---------------------------------------------------------------------\r\n\r\nmitades :: [a] -> ([a],[a]) \r\nmitades xs = splitAt (length xs `div` 2) xs\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 14.3. Definir por recursi\u00f3n la funci\u00f3n \r\n--    ordMezcla :: Ord a => [a] -> [a]\r\n-- tal que (ordMezcla xs) es la lista obtenida ordenado xs por mezcla\r\n-- (es decir, considerando que la lista vac\u00eda y las listas unitarias\r\n-- est\u00e1n ordenadas y cualquier otra lista se ordena mezclando las dos\r\n-- listas que resultan de ordenar sus dos mitades por separado). Por\r\n-- ejemplo, \r\n--    ordMezcla [5,2,3,1,7,2,5]  ==  [1,2,2,3,5,5,7]\r\n-- ---------------------------------------------------------------------\r\n\r\nordMezcla :: Ord a => [a] -> [a]\r\nordMezcla []  = []\r\nordMezcla [x] = [x]\r\nordMezcla xs  = mezcla (ordMezcla ys) (ordMezcla zs)\r\n                where (ys,zs) = mitades xs\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 14.4. Definir por recursi\u00f3n la funci\u00f3n\r\n--    ordenada :: Ord a => [a] -> Bool\r\n-- tal que (ordenada xs) se verifica si xs es una lista ordenada. Por\r\n-- ejemplo, \r\n--    ordenada [2,3,5]  ==  True\r\n--    ordenada [2,5,3]  ==  False\r\n-- ---------------------------------------------------------------------\r\n\r\nordenada :: Ord a => [a] -> Bool\r\nordenada []       = True\r\nordenada [_]      = True\r\nordenada (x:y:xs) = x <= y &#038;&#038; ordenada (y:xs)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 14.5. Comprobar con QuickCheck que la ordenaci\u00f3n por mezcla\r\n-- de una lista es una lista ordenada.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La propiedad es\r\nprop_ordMezcla_ordenada :: [Int] -> Bool\r\nprop_ordMezcla_ordenada xs = ordenada (ordMezcla xs)\r\n\r\n-- La comprobaci\u00f3n es\r\n--    ghci> quickCheck prop_ordMezcla_ordenada\r\n--    +++ OK, passed 100 tests.\r\n    \r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 14.6. Definir por recursi\u00f3n la funci\u00f3n\r\n--    borra :: Eq a => a -> [a] -> [a]\r\n-- tal que (borra x xs) es la lista obtenida borrando una ocurrencia de\r\n-- x en la lista xs. Por ejemplo, \r\n--    borra 1 [1,2,1]  ==  [2,1]\r\n--    borra 3 [1,2,1]  ==  [1,2,1]\r\n-- ---------------------------------------------------------------------\r\n\r\nborra :: Eq a => a -> [a] -> [a]\r\nborra x []                 = []\r\nborra x (y:ys) | x == y    = ys\r\n               | otherwise = y : borra x ys\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 14.7. Definir por recursi\u00f3n la funci\u00f3n \r\n--    esPermutacion :: Eq a => [a] -> [a] -> Bool\r\n-- tal que (esPermutacion xs ys) se verifica si xs es una permutaci\u00f3n de\r\n-- ys. Por ejemplo, \r\n--    esPermutacion [1,2,1] [2,1,1]  ==  True\r\n--    esPermutacion [1,2,1] [1,2,2]  ==  False\r\n-- ---------------------------------------------------------------------\r\n\r\nesPermutacion :: Eq a => [a] -> [a] -> Bool\r\nesPermutacion []     []     = True\r\nesPermutacion []     (y:ys) = False\r\nesPermutacion (x:xs) ys     = elem x ys && esPermutacion xs (borra x ys)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 14.8. Comprobar con QuickCheck que la ordenaci\u00f3n por mezcla\r\n-- de una lista es una permutaci\u00f3n de la lista.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La propiedad es\r\nprop_ordMezcla_pemutacion :: [Int] -> Bool\r\nprop_ordMezcla_pemutacion xs = esPermutacion (ordMezcla xs) xs\r\n\r\n-- La comprobaci\u00f3n es\r\n--    ghci> quickCheck prop_ordMezcla_pemutacion\r\n--    +++ OK, passed 100 tests.\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En la segunda 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 8\u00aa relaci\u00f3n que tratan de la ordenaci\u00f3n por mezcla. Los ejercicios, y sus soluciones, 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":[1],"tags":[298],"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\/2364"}],"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=2364"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/2364\/revisions"}],"predecessor-version":[{"id":2738,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/2364\/revisions\/2738"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=2364"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=2364"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=2364"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}