[알고리즘] Quick Sort 퀵정렬 : 필수 기본 정리 - 로무토 분할, 호어, 효율적인 피봇값 정하기

목차

 

퀵 정렬은 비교 연산을 이용한 정렬 알고리즘입니다. 이전 포스트에서도 많은 정렬 알고리즘을 다뤘는데요, 아래 정렬 알고리즘들을(버블 정렬, 삽입 정렬, 선택 정렬, 병합 정렬, 힙 정렬) 모르신다면 보고 오시는 것을 추천드립니다. 

[알고리즘] O(n2) 3가지 기본 정렬 알고리즘 : 버블 정렬, 선택정렬, 삽입정렬 Kotlin 구현

 

[알고리즘] Merge Sort 병합정렬 : 필수 기본 정리 - 구현, split, merge 코드 설명 - Kotlin

 

[알고리즘] Heapsort 힙정렬: 필수 기본정리 - 힙정렬 원리, 구현

퀵 정렬

피봇(Pivot)이란

우선 퀵 정렬은 병합 정렬과 비슷한 구조를 하고 있습니다. 

두 정렬은 똑같이 1. 비교 연산을 사용하고, 2. 나누고 합치는 전략을 사용합니다. 

퀵 정렬의 핵심 요소는 피봇(Pivot)입니다. 피봇은 리스트 안에 있는 한 요소를 뜻합니다. 

그리고 피봇은 데이터를 3개의 파티션으로 나눕니다. 나누는 기준은 아래와 같습니다.  

[ elements < pivot | pivot | elements > pivot ]

피봇보다 작은 수가 모여있는 파티션 피봇과 같은 수가 모여있는 파티션 , 피봇보다 큰 수가 모여있는 파티션

 

우선 피봇을 통해 3개의 파티션을 나누도록 도와주는 quicksortNaive라는 함수를 구현해주겠습니다. 

quicksortNaive

fun<T: Comparable<T>> List<T>.quicksortNaive(): List<T> {
    if(this.size < 2) return this//1
    
    val pivot = this[this.size /2 ]//2
    val less = this.filter { it < pivot }//3
    val equal = this.filter { it == pivot}
    val greater = this.filter { it > pivot }
    return less.quicksortNaive() + equal +
    greater.quicksortNaive() //4
}

1. 리스트에 2개 이상 element가 없다면, 정렬되었다고 정의할 수 있습니다. 

2. 리스트에 가운데 값을 pivot으로 지정합니다. 

3. 위에서 지정하 피봇을 이용해 3 등분합니다. 

4. 반복문으로 정렬한 후, 합칩니다. 

 

파티션으로 나눠지는 과정

위 코드만 봤을 때 아직 어떻게 3개의 파티션으로 나눠지는지 헷갈릴 수 있습니다. 아래 리스트를 위 함수를 통해 3개의 파티션으로 나눠보겠습니다. 

[12, 0, 3, 9, 2, 18, 8, 27, 1, 5, 8, -1, 21]

pivot으로 3개의 파티션을 분리한 후입니다. 

less: [0, 3, 2, 1, 5, -1]
equal: [8, 8]
greater: [12, 9, 18, 27, 21]

하지만 전체 리스트가 정렬돼있다고 할 수 없습니다. 그럼 여기서 어떻게 더 정렬할 수 있을까요? 바로, 가운데 값이 나오지 않을 때까지 나누게 됩니다. 아래 다이어그램을 살펴보겠습니다. 

3개의 파티션으로 나눈 후 나눠진 각각의 파디션들은 다시 3개로 나눠지게 됩니다. 그럼 트리 모양이 돼가고 있는 것을 확인할 수 있습니다. 위와 같이 더 이상 나눌 수 없을 때까지 반복하면 그 파티션은 정리가 되었다고 할 수 있습니다. 그리고 나눌 수 없게 된 단말 노드를 모두 모으면, 아래와 같은 정렬된 리스트가 만들어집니다. 

[-1, 1, 2, 3, 5, 8, 8, 9, 12, 18, 21, 27]

피봇을 이용한 퀵 정렬은 정말 이해하기 쉽지만 3가지 의문점이 듭니다.

# 중간에 위치한 element를 pivot으로 설정하는 게 가장 효율적인 방법일까요?

# 파티션마다 리스트를 3개씩 생성해주면 메모리로서 비효율적이지 않을까요?

# 파티션으로 나눌 때 한 파티션당 3번의 과정을 거쳐서 나눠야 하는 게 비효율적이지 않을까요?

 

다음 3개의 소문단을 통해서, 이 3개의 의문점을 해결해줄 수 있는 해결책을 알아보도록 하겠습니다. 

 

로무토 분할을 활용한 퀵 정렬

로무토 분할(Lomuto partitioning) 알고리즘은 항상 피봇 값으로 중간값이 아닌 마지막 element를 선택합니다.

 

로무토 분할 작동 방식

구현하기 전로 무토가 어떻게 작동하는지 먼저 알아볼 필요가 있습니다. 

다이어그램	설명
	#초기상태 우리가 정렬할 리스트의 초기 상태입니다. Pivot : 가장 마지막 element i : 맨 왼쪽 element의 index 값 -1 j : 맨 왼쪽 element의 index 값
	# j 값이 피봇보다 작거나 같을때 이제부터 아래 while문을 반복하게됩니다.  while( j =초기값 until 피봇 index ){     if( j 값이 피봇보다 작거나 같다면 ) {         i ++         i가 가르키는 값과 j가 가르키는 값 swap     j ++     } } i + 1 값과 피봇값을 swap 이 상황에서는 j가 가르키는 값이 연속적으로 pivot값보다 작아서 i값과 j값이 같이 동하면서 제자리에서 swap되고 있습니다.
	# j 값이 피봇보다 클때 while( j =초기값 until 피봇 index ){     if( j 값이 피봇보다 작거나 같다면 ) {         i ++         i가 가르키는 값과 j가 가르키는 값 swap     j ++     } } i + 1 값과 피봇값을 swap 반복문을 진행 하던중 처음으로 j값이 피봇보다 큰상황을 마주하게 됩니다. 그러면 위반복문에서 if가 true일때 실행되는  i ++  i가 가르키는 값과 j가 가르키는 값 swap 이 두가지가 스킵되고 j값만 늘어나게 됩니다.  그리고 다시 j 값과 피봇 값을 비교를 이어나갑니다. 그리고 다시 j값이 pivot보다 작거나 같아질때 i위치에 있는element와 j위치에 있는 element를 swap합니다.
	# j 가 피봇까지 도달했을때 while( j =초기값 until 피봇 index ){     if( j 값이 피봇보다 작거나 같다면 ) {         i ++         i가 가르키는 값과 j가 가르키는 값 swap     j ++     } } i + 1 값과 피봇값을 swap 끝까지 도달했을때 while문이 끝나고  i + 1 값과 피봇값을 swap이 실행되게됩니다.  옆에 다이어그램을 확인해보면 i+1값인9와 피봇이swap된걸 확인할수잇습니다.
	# 모두 정렬될때까지 3개의 리스트로 나눠서 반복 왼쪽에 위치한 리스트 3142는 2를 피봇으로 지정하여 다시 while문을 실행하고 5는 하나이기때문에 정렬되었다고 확정합니다. 오른쪽에 위치한 6879또한 While문을 실행하여 다시 정렬을 시작합니다.

 

로무토 분할 구현

위 과정을 바탕으로 루 모토 알고리즘을 코드로 구현해보겠습니다. 먼저 로무토 파티션 생성을 위한 함수를 만들어주겠습니다. 

로무토 분할 생성

fun<T: Comparable<T>> MutableList<T>.partitionLomuto(
	low: Int,
    high: Int): Int{
    
}

우선 3가지로 구성되어있습니다. 파티션으로 사용될 리스트와 피봇보다 작은 값(low) 피봇보다 큰 값(high)입니다. 

피봇보다 작은 값은 리스트에서 왼쪽에 위치하게 되고 큰 값은 오른쪽으로 위치하게 됩니다. 

 

위에서 했던 while반복문과 같은 형태를 가진 반복문을 만들어주겠습니다. 

 

val pivot = this[high]//1

var i = low //2
for(j in low until high) { //3
	if(this[j] <= pivot) { //4
    	this.swapAt(i, j) //5
        i += 1
    }
}
this.swapAt(i,high)//6
return i //7

위 코드를 설명해보겠습니다. 

1. 피봇 값을 설정합니다. 피봇 값은 항상 마지막 element입니다. 

2. i는 pivot보다 작은 element의 개수입니다. i는 우리가 피봇 값보다 작은 값을 찾았을 때 i위치와 자리를 바꿔주고 i를 1 증가시킵니다. 

3. 처음부터 피봇을 제외한 마지막 까지(until을 쓴 이유) 반복하여 element에 접근합니다. 

4. 현재 element가 pivot과 같은지 확인합니다. 

5. 같다면 i와 현재 element의 위치를 바꿔줍니다. 그리고 i 값을 1 증가시킵니다. 

6. 반복문이 끝났다면, i 위치와 pivot의 위치를 바꿔줍니다. 

7. 피봇의 index를 반환합니다. 

 

 

호어 분할을(Hoarse partitioning) 활용한 퀵 정렬 

호어 분할은 피봇 값보다 클 때 오른쪽, 작은 값들은 왼쪽에 위치시킵니다. 그리고 피봇 값이 오른쪽 끝에 위치합니다. 

 

호어 분할 작동 방식

과정을 먼저 살펴보겠습니다. 

 

다이어그램	설명
	#초기상태 우리가 정렬할 리스트의 초기 상태입니다. Pivot : 맨 왼쪽 값 i : Pivot의 바로 다음 값 j : 맨 오른쪽 값
	# j 값과i 값이 피봇보다 클때 (i만 만족) 이제부터 아래 반복문을 반복하게 됩니다.  while( i 가 j보다 작거나 같을때까지){     i 위치 값이 Pivot 값보다 같거나 큰값인지 확인     j 위치 값이 Pivot 값보다 같거나 작은값인지 확인          if( i , j 모두 찾는 값을 찾았다면)     두 값을 서로 swap     i++, j++          else if( i 만 원하는 값을 찾았다면)     j--     else if( j 만 원하는 값을 찾았다면)     i++ } 피봇값과 j가 가르키는 값을 swap
	# j값이 피봇보다 작고 i값은 피봇보다 클때 (i j둘다 만족) while( i 가 j보다 작거나 같을때까지){     i 위치 값이 Pivot 값보다 같거나 큰값인지 확인     j 위치 값이 Pivot 값보다 같거나 작은값인지 확인          if( i , j 모두 찾는 값을 찾았다면)     두 값을 서로 swap     i++, j++          else if( i 만 원하는 값을 찾았다면)     j--     else if( j 만 원하는 값을 찾았다면)     i++ } 피봇값과 j가 가르키는 값을 swap i와 j가 모두 만족하게 되어 i j 위치에있는 값을 swap하게됩니다.  그리고 i j 둘다 1씩 증가합니다.
	# i 와 j 가 교차할때 while( i 가 j보다 작거나 같을때까지){     i 위치 값이 Pivot 값보다 같거나 큰값인지 확인     j 위치 값이 Pivot 값보다 같거나 작은값인지 확인          if( i , j 모두 찾는 값을 찾았다면)     두 값을 서로 swap     i++, j++          else if( i 만 원하는 값을 찾았다면)     j--     else if( j 만 원하는 값을 찾았다면)     i++ } 피봇값과 j가 가르키는 값을 swap 이제 j값이 i 보다 작게되어 while문이 끝나고 피봇값과 j값을 swap하게됩니다.
	# 파티션이어 가기 이제 새로운 파티션들이 생기게 됩니다.  [2,1] : 이 파티션에는 element가 두개만 있기때문에 피봇지정으로 정렬후 정렬이끝납니다.  [3] : element가 하나기때문에 정렬이 끝납니다.  [6, 9, 4, 8, 7, 5] : 피봇값을 새로 지정하며 정렬을 시작합니다. 피봇값이 또 바뀌면 거기서 나오는 3개의 리스트를 같은방식으로 다시 정렬하여 정렬을 완성시킵니다.

 

호어 분할 구현

fun<T: Comparable<T>> MutableList<T>.partitionHoare(low: Int, 
high: Int): Int {
    val pivot = this[low] // 1
    var i = low - 1 // 2
    var j = high + 1
    while (true) {
        do { // 3
        j -= 1
        } while (this[j] > pivot)
        do { // 4
            i += 1
        } while (this[i] < pivot)
        if (i < j) { // 5
            this.swapAt(i, j)
        } else {
            return j // 6
        }
    }
}

코드를 설명해보겠습니다. 

1. 첫 값을 pivot으로 설정합니다. 

2. i와 j값을 지정

3. 피봇보다 작은 값이 나올 때까지 j 값을 1씩 감소시킵니다. 

4. 피봇보다 큰 값이 나올 때까지 i 값을 1씩 증가시킵니다.

5. i와 j가 겹쳐있지 않다면 swap 합니다.

6. 이제 두 부분으로 나눠주는 j값을 리턴합니다.

 

이제 위 호어 분할 함수를 사용하는 호어 퀵 정렬을 구현해보겠습니다.

fun<T: Comparable<T>>MutableList<T>.quicksortHoare(low: Int, high: Int) {
	if(low < high) {
    	val p = this.partitionHoare(low,high)
        this.quicksortHoare(low,p)
        this.quicksortHoare(p+1, high)
    }
}

 

피봇 값에 따른 퀵 정렬 성능 비교

퀵 정렬을 구현하기 위해 위에 3가지 방법으로 피봇을 설정하였습니다. 

1. 중간값을 피봇으로 설정하기

2. 로무토: 마지막 값을 피봇으로 설정하기 

3. 호어: 첫 번째 값을 피봇으로 설정하기

 

그럼 이 3가지 방법 중 어떤 상황에 어떤 값을 피봇으로 설정해야 사장 효율적일까요?

 

중간값(Median) 이용하기

 

먼저 다음 정렬되지 않은 리스트를 살펴보겠습니다. 

[8, 7, 6, 5, 4, 3, 2, 1]

정렬되지 않은 리스트를 루 모토로 분할한다고 가정해봅시다. 그러면 피봇 값은 1로 설정됩니다.

less: [ ]
equal: [1]
greater: [8, 7, 6, 5, 4, 3, 2]

가장 이상적인 피봇 값은 피봇 값이 정확하게 반으로 한쪽은 작은 값만 한쪽은 큰 값만 놓도록 파티션을 나누는 위치에 있어야 합니다. 만약 정렬된 리스트를 다시 정렬하려 하고 리스트에 가장 앞이나 끝에 가장 큰 값이 있게 되면, 루 모토와 호어 같은 분할 방식은 O(n^2) 최악의 속도가 나오게 됩니다. 

 

이렇게 리스트에서 가장 큰 값이나 작은 값이 리스트 앞뒤에 위치할 때 느려지는 것을 방지하기 위해 중간값을 이용할 수 있습니다. 가장 첫 번째 값, 중간값, 마지막 값의 중간값을 구합니다. 그리고 그것을 피봇으로 사용합니다. 그러면 가장 큰 값과 작은 값을 선택을 피하게 되면서 최악의 속도를 방지할 수 있습니다. 

 

코드로 나타내 보겠습니다. 

fun<T: Comparable<T>> MutableList<T>.medianOfThree(low: Int, 
high: Int): Int {
    val center = (low + high) / 2
    if (this[low] > this[center]) {
    this.swapAt(low, center)
    }
    if (this[low] > this[high]) {
    this.swapAt(low, high)
    }
    if (this[center] > this[high]) {
    this.swapAt(center, high) 
    }
    return center
 }

이제 3개의 element 중간값을 이용한 퀵 정렬을 구현해보겠습니다.  

fun<T: Comparable<T>> MutableList<T>.quickSortMedian(low: Int, 
high: Int) {
    if (low < high) {
    val pivotIndex = medianOfThree(low, high)
    this.swapAt(pivotIndex, high)
    val pivot = partitionLomuto(low, high)
    this.quicksortLomuto(low, pivot - 1)
    this.quicksortLomuto(pivot + 1, high)
    }
}

 

중복 값 다루기(Dutch national flag partitioning)

 

루투오와 호어 알고리즘은 중복 값을 다루는데 효율적이지 않습니다. 이렇게 중복 값을 다룰 때 네덜란드 국기 문제(Dutch national flag partitioning)를 통해 해결할 수 있습니다. 이 분할 방법은, 네덜란드 국기의 색깔인 붉은색(위), 흰색(중앙), 파란색(아래)을 세 부분으로 대입해 분할을 하게 됩니다. 

 

fun<T: Comparable<T>> MutableList<T>.partitionDutchFlag(low: 
Int, high: Int, pivotIndex: Int): Pair<Int, Int> {
    val pivot = this[pivotIndex]
    var smaller = low // 1
    var equal = low // 2
    var larger = high // 3
    while (equal <= larger) { // 4
        if (this[equal] < pivot) {
        this.swapAt(smaller, equal)
        smaller += 1
        equal += 1
      } else if (this[equal] == pivot) {
        equal += 1
      } else {
        this.swapAt(equal, larger)
        larger -= 1
    }
  }
  return Pair(smaller, larger) // 5
}