I1M2012: Ordenación por mezcla
En la segunda parte de la clase de hoy de Informática de 1º del Grado en Matemáticas hemos comentado las soluciones de los ejercicios de la 8ª relación que tratan de la ordenación por mezcla.
Los ejercicios, y sus soluciones, se muestran a continuación:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 |
-- --------------------------------------------------------------------- -- Introducción -- -- --------------------------------------------------------------------- -- El objetivo de esta relación es definir la ordenación por mezclas y -- comprobar su corrección con QuickCheck. import Test.QuickCheck -- --------------------------------------------------------------------- -- Ejercicio 14.1. Definir por recursión la función -- mezcla :: Ord a => [a] -> [a] -> [a] -- tal que (mezcla xs ys) es la lista obtenida mezclando las listas -- ordenadas xs e ys. Por ejemplo, -- mezcla [2,5,6] [1,3,4] == [1,2,3,4,5,6] -- --------------------------------------------------------------------- mezcla :: Ord a => [a] -> [a] -> [a] mezcla [] ys = ys mezcla xs [] = xs mezcla (x:xs) (y:ys) | x <= y = x : mezcla xs (y:ys) | otherwise = y : mezcla (x:xs) ys -- --------------------------------------------------------------------- -- Ejercicio 14.2. Definir la función -- mitades :: [a] -> ([a],[a]) -- tal que (mitades xs) es el par formado por las dos mitades en que se -- divide xs tales que sus longitudes difieren como máximo en uno. Por -- ejemplo, -- mitades [2,3,5,7,9] == ([2,3],[5,7,9]) -- --------------------------------------------------------------------- mitades :: [a] -> ([a],[a]) mitades xs = splitAt (length xs `div` 2) xs -- --------------------------------------------------------------------- -- Ejercicio 14.3. Definir por recursión la función -- ordMezcla :: Ord a => [a] -> [a] -- tal que (ordMezcla xs) es la lista obtenida ordenado xs por mezcla -- (es decir, considerando que la lista vacía y las listas unitarias -- están ordenadas y cualquier otra lista se ordena mezclando las dos -- listas que resultan de ordenar sus dos mitades por separado). Por -- ejemplo, -- ordMezcla [5,2,3,1,7,2,5] == [1,2,2,3,5,5,7] -- --------------------------------------------------------------------- ordMezcla :: Ord a => [a] -> [a] ordMezcla [] = [] ordMezcla [x] = [x] ordMezcla xs = mezcla (ordMezcla ys) (ordMezcla zs) where (ys,zs) = mitades xs -- --------------------------------------------------------------------- -- Ejercicio 14.4. Definir por recursión la función -- ordenada :: Ord a => [a] -> Bool -- tal que (ordenada xs) se verifica si xs es una lista ordenada. Por -- ejemplo, -- ordenada [2,3,5] == True -- ordenada [2,5,3] == False -- --------------------------------------------------------------------- ordenada :: Ord a => [a] -> Bool ordenada [] = True ordenada [_] = True ordenada (x:y:xs) = x <= y && ordenada (y:xs) -- --------------------------------------------------------------------- -- Ejercicio 14.5. Comprobar con QuickCheck que la ordenación por mezcla -- de una lista es una lista ordenada. -- --------------------------------------------------------------------- -- La propiedad es prop_ordMezcla_ordenada :: [Int] -> Bool prop_ordMezcla_ordenada xs = ordenada (ordMezcla xs) -- La comprobación es -- ghci> quickCheck prop_ordMezcla_ordenada -- +++ OK, passed 100 tests. -- --------------------------------------------------------------------- -- Ejercicio 14.6. Definir por recursión la función -- borra :: Eq a => a -> [a] -> [a] -- tal que (borra x xs) es la lista obtenida borrando una ocurrencia de -- x en la lista xs. Por ejemplo, -- borra 1 [1,2,1] == [2,1] -- borra 3 [1,2,1] == [1,2,1] -- --------------------------------------------------------------------- borra :: Eq a => a -> [a] -> [a] borra x [] = [] borra x (y:ys) | x == y = ys | otherwise = y : borra x ys -- --------------------------------------------------------------------- -- Ejercicio 14.7. Definir por recursión la función -- esPermutacion :: Eq a => [a] -> [a] -> Bool -- tal que (esPermutacion xs ys) se verifica si xs es una permutación de -- ys. Por ejemplo, -- esPermutacion [1,2,1] [2,1,1] == True -- esPermutacion [1,2,1] [1,2,2] == False -- --------------------------------------------------------------------- esPermutacion :: Eq a => [a] -> [a] -> Bool esPermutacion [] [] = True esPermutacion [] (y:ys) = False esPermutacion (x:xs) ys = elem x ys && esPermutacion xs (borra x ys) -- --------------------------------------------------------------------- -- Ejercicio 14.8. Comprobar con QuickCheck que la ordenación por mezcla -- de una lista es una permutación de la lista. -- --------------------------------------------------------------------- -- La propiedad es prop_ordMezcla_pemutacion :: [Int] -> Bool prop_ordMezcla_pemutacion xs = esPermutacion (ordMezcla xs) xs -- La comprobación es -- ghci> quickCheck prop_ordMezcla_pemutacion -- +++ OK, passed 100 tests. |