하스켈로 알고리즘을 구현하는 것이 좀더 큰 목적이지만, 그렇다고 알고리즘 구현에 뛰어난 것이 아니기 때문에 복습도 해볼겸해서 정렬알고리즘을 하스켈로 구현하고 각각의 특징을 정리 해보려고 합니다. 
그 1탄으로 Insertion sort, Selection sort, Merge sort, Quick sort입니다.
오늘은 어려운 코드가 아니므로 알고리즘 구현에 대한 자세한 설명은 생략하는 것이 좋을 것 같습니다.
일단 코드 부터 보겠습니다. 기존에 C와 다른 코드 이므로 좀더 신중하게 보세요.. 
하스켈을 모르셔도 읽는데는 무리가 없을 것이라고 생각합니다. (필요한부분은 설명을 하도록 하겠습니다.)

-- this function is inserttion sort
insert :: Ord a => a -> [a] -> [a]
insert x [] = [x]
insert x (y:ys)
| x < y  = x : y : ys
| otherwise = y : insert x ys 
isort :: Ord a => [a] -> [a]
isort [] = []
isort (x:xs) = insert x (isort xs)

위의 코드는 Insertion sort입니다. 보통 책에는 Iterative하게 구현했지만 함수형 언어의 특징을 살려 recursive함수로 구현했습니다. (참고로, 저도 아직 배우는 중이라서 비슷하게는 구현했지만 부족한 부분은 인터넷에 떠도는 멜버른 대학의 코드를 가져 왔습니다.)

-- this function is selection sort
myMin :: Ord a => [a] -> a
myMin [] = undefined 
myMin [x] = x 
myMin (x:xs) 
| x <= myMin(xs) = x
| otherwise = myMin(xs)
delete :: Eq a => a -> [a] -> [a]
delete x [] = []
delete x (y:ys)
| x == y = ys
| otherwise = y : (delete x ys)    
ssort :: Ord a => [a] -> [a]
ssort [] = []
ssort xs = [x] ++ ssort (delete x xs) 
where x = myMin (xs)

이번 코드는 Selection sort입니다. 개인적으로 이 코드를 구현하는게 좀더 쉬었네요...

-- this function is merge sort 
merge :: Ord a => [a] -> [a] -> [a]
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys)
| x <= y = x : (merge xs (y:ys))
| otherwise = y : (merge (x:xs) ys)
msort :: Ord a => [a] -> [a]
msort [] = []
msort [x] = [x]
msort xs = merge (msort top) (msort bottom)
where (top, bottom) = splitAt (length xs `div` 2) xs

이번 코드는 Merge sort입니다. 조심하셔야 하는 것은 종료 조건을 정확하게 기준해야 한다는 점입니다. 정렬 알고리즘을 재귀함수로 구현 하기 때문에 종료 조건이 특히 중요 합니다. 다른 언어보다 알고리즘을 표현하기 쉽기 때문에 이런 부분만 신경쓴다면 알고리즘 외의 부분에서는 오류 날일이 거의 없을 듯 합니다.

-- this function is quick sort
qsort :: Ord a => [a] -> [a]
qsort [] = []
qsort (x:xs) = qsort smaller ++ [x] ++ qsort bigger
where smaller = [a | a <- xs, a <= x]
     bigger = [b | b <- xs, b > x]  

개인적으로 하스켈을 공부한지 한달 정도 되었는데, 이 코드가 가장 좋아 하는 코드 입니다. 너무너무나 Clear하죠^^(저희 학교에 어떤 교수님께서 잘 쓰시는 말을 인용했습니다.)
신고
by danguria 2010.02.27 16:05
| 1 |