Scala로 만들어본 Quick Sort

퀵소트는 아주 강력하고 쉬운 정렬 알고리즘이다.

배열의 값 하나를 선택해서(pivot), pivot보다 작은 것을 왼쪽, pivot보다 큰 것을 오른쪽으로 모은 후 

왼쪽에 대한 재귀호출, pivot, 오른쪽에 대한 재귀호출 셋을 순서대로 이어붙이면 된다.

함수가 호출될 때마다 피벗의 위치가 확정되고 재귀호출되어 재실행되는 리스트는 이전 배열의 절반 수준이기 때문에 복잡도를 로그단위로 끌어내릴 수 있다.

함수형 프로그래밍 언어들에서는 그 특유의 콤비네이터들이 있어 구현을 굉장히 쉽게 만든다.

구글링으로 가장 먼저 볼 수 있는 스칼라 퀵 소트의 알고리즘은

def quickSortHead[A](lst: List[A])(implicit ord: A => Ordered[A]): List[A] = lst match{
  case x if x.isEmpty || x.length == 1 => lst
  case pivot::tail =>
    val (lLst, rLst) = tail.partition(_ < pivot)
    quickSortHead(lLst) ::: pivot :: quickSortHead(rLst)
}

(정렬 가능한 제네릭을 사용하기 위해 implicit 키워드를 사용했다. 순서있는 자료형 A라고 생각하면 될 듯하다.)

이런 형태다. 

이 알고리즘에서는 pivot을 리스트의 head로 잡는다. 

덕분에 '조건에 따라 true면 _1, false면 _2로 묶어주는 partition 함수'와 패턴매칭을 이용해 구현할 수 있다.

하지만 이대로 끝내기엔 아쉬움이 남는다.

퀵 소트에서 pivot은 아주 중요한데, 위와 같이 pivot을 head로 잡으면 이미 정렬 되어 있는 경우 

재귀호출될 때마다 왼쪽 값은 Nil, 오른쪽 값은 입력받은 리스트의 tail이 됨으로써 재귀 횟수가 많아져 N^2의 복잡도로 실행된다.

그래서 대부분의 경우 pivot은 입력받은 리스트의 중앙값을 사용한다고 한다.

그렇다면 위와 같은 알고리즘에서 피벗만 중앙값으로 설정해

def quickSortMid[A](lst: List[A])(implicit ord: A => Ordered[A]): List[A] = {
  if(lst.isEmpty || lst.length == 1) lst
  else {
    val pivot = lst(lst.length /2)
    val (lLst, rLst) = lst.filterNot(_ == pivot) // pivot과 같은 값을 모두 제거한 리스트
                          .partition(_ < pivot)
    quickSortHead(lLst) ::: pivot :: quickSortHead(rLst)
  }
}

이런 코드로 구현하면 될까?

안타깝게도 filter는 조건이 만족하는 모든 값을 모은 콜렉션을 리턴한다.

그래서 pivot과 같은 값이 리스트에 있으면 모두 제거되어 버린다.

비슷한 역할을 하면서 하나만 지우는 함수를 직접 구현해 사용해도 되지만 다른 방법을 생각해 봤다.

fold 콤비네이터를 이용해 값들을 모으는 방법이다.

def quickSort[A](lst: List[A])(implicit ord: A => Ordered[A]): List[A] = {
  if(lst.isEmpty || lst.length == 1) lst
  else {
    val pivot = lst(lst.length / 2)
    val (lLst, sLst, rLst) = lst.foldLeft{(List.empty[A], List.empty[A], List.empty[A])}{ (total, x) =>
      val (lessThan, same, greaterThan) = total
      if(x < pivot) (x::lessThan, same, greaterThan)
      else if(x > pivot) (lessThan, same, x::greaterThan)
      else (lessThan, x::same, greaterThan)
    }
    quickSort(lLst) ::: sLst ::: quickSort(rLst)
  }
}

콜렉션을 순회하며 새로운 리스트에 모아넣는 fold를 이용해

pivot보다 작은 값, pivot과 같은 값, pivot보다 큰 값을 모아 재귀호출하는 방법이다.

작동에는 문제가 없지만 코드가 훨씬 길고 복잡해지는게 마음에 걸린다.

더 좋은 방법은 없을까.