2012-10-06 9 views
1

I 라인의 몇 삽입 정렬과 퀵을 구현하기 위해 관리가 간단하지만, 선택 정렬과 머지 소트는 여전히 나에게 두통을 줄? 나는 행운없이 (a -> a -> Bool/Ordering) -> [a] -> (a, [a])을 위해 놀고 다녔다.는 선택 정렬과 머지 소트

mergesort [ ] = [ ] 

mergesort [x] = [x] 

mergesort xs = 
    let (left, right) = splitAt (length xs `div` 2) xs 
    in merge (mergesort left) (mergesort right) 

merge xs [] = xs 

merge [] ys = ys 

merge [email protected](x:xs) [email protected](y:ys) 
    | x < y  = x : merge xs yys 
    | otherwise = y : merge xxs ys 

다시 말하지만, 나는 merge에게 자신을 작성해야합니까, 아니면 기존 구성 요소를 재사용 할 수 있습니까? Hoogle은 (a -> a -> Bool/Ordering) -> [a] -> [a] -> [a]에 대한 유용한 결과를 제공하지 않았습니다.

+6

nb @sudo_o와 그 편집을 승인 한 사람 : [Hoogle] (http://www.haskell.org/hoogle/)은 형식 서명을 통해 하스켈 라이브러리 기능을 검색 할 수있는 검색 엔진입니다. 그것은 Google의 오타가 아닙니다. – dave4420

+0

실례지만 내 무지 하하 .. –

+2

그건 그렇고, 하향식 mergesort 하스켈에있는 목록과 아주 가난한 생각입니다. 목록을 분할하고 목록의 길이를 찾는 데는 많은 시간을 소비합니다. 아래에서 위로 작업하는 것이 훨씬 간단합니다. 입력을 길이 1 목록으로 변환 한 다음 왼쪽에 하나만 남을 때까지 인접 목록 쌍을 병합하십시오. – Carl

답변

2

표준 라이브러리에는 아무 것도 없지만, merge은 패키지에 의해 hackage에 제공됩니다. 그러나이 간단한 기능에 대한 종속성을 끌어낼 가치가 있는지는 잘 모르겠습니다.

그러나

,

merge [email protected](x:xs) [email protected](y:ys) 
    | x < y  = x : merge xs yys 
    | otherwise = y : merge xxs ys 

안정적인 종류를 얻기 위해, 비 안정 종류를 생산, x을 배치 할 수있는 조건은 x <= y해야한다. extractMinimum를 들어

이, 나도 아무것도 발견하지 않은,하지만 난

extractMinimum :: Ord a => a -> [a] -> (a,[a]) 
extractMinimum x = foldl' select (x, []) 
    where 
    select (mini, greater) y 
     | y < mini = (y, mini:greater) 
     | otherwise = (mini, y:greater) 

selectionSort의 좋은 정의는 것, 다른 정의를 제공 할 수

import Data.List -- for unfoldr 

selectionSort :: Ord a => [a] -> [a] 
selectionSort = unfoldr getMin 
    where 
    getMin [] = Nothing 
    getMin (x:xs) = Just $ extractMinimum x xs 
0

선택 정렬에 대한 나의 제안 :

import Data.List 

selectionsort xs = unfoldr f xs where 
    f [] = Nothing 
    f xs = Just $ extractMinimum xs 

extractMinimum (x:xs) = foldl' f (x,[]) xs where 
    f (minimum, greater) x | x < minimum = (x, minimum : greater) 
         | otherwise = (minimum, x : greater)