2votos

Algoritmo de ordenación merge sort en Haskell

por josejuan hace 6 años

Como Haskell es perezoso, la implementación eficiente con listas es elegante y curiosa (por la diferente forma respecto la versión típica imperativa en que se divide y fusiona la lista original).

Existen muchos algoritmos de ordenación, quizá el más conocido es el de la burbuja pero el 'merge sort' resulta mucho más eficiente. ¿Qué tal se te da mezclar arrays?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
-- FUENTE: 
-- http://en.literateprograms.org/Merge_sort_%28Haskell%29 
 
merge pred xs []         = xs 
merge pred [] ys         = ys 
merge pred (x:xs) (y:ys) = 
  case pred x y of 
    True  -> x: merge pred xs (y:ys) 
    False -> y: merge pred (x:xs) ys 
 
mergesort pred [] = [] 
mergesort pred xs = go [[x] | x <- xs] 
  where 
    go xs@(_:_:_)  = go (pairs xs) 
    go [xs]        = xs 
    pairs (x:y:xs) = merge pred x y : pairs xs 
    pairs xs       = xs 
1 comentario
0votos

Escrito por jneira hace 6 años

Precioso, parece que haskell se diseño para hacer cosas como esta.

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.