[정렬 알고리즘]Quick Sort

퀵 정렬(Quick Sort)

퀵 정렬은 합병 정렬과 같은 가정으로 작동한다. 재귀를 통해 해결하기 가장 쉬운 방식 중 하나이다. 기본적으로 데이터를 분할하여 배열에 0개 또는 1개의 항목이 남을 때까지 분할하여 개별적으로 정렬되는 방식이다.

피벗(pivot) 포인트라 부르는 단일 요소를 선택하고 정렬된 배열에서 피벗이 끝날 인덱스를 찾는 방식으로 작동한다.

피벗이 적절하게 배치되면 피벗 양쪽에 퀵 정렬을 적용할 수 있다. 

 

이 설명이 어렵게 들리겠지만 천천히 하나씩 살펴보자. 그림으로 이해해보자.

정렬되지 않은 8개의 요소를 가진 배열이 있다.

첫 번째인 5를 피벗 포인트로 잡고 5보다 작은 숫자를 모두 왼쪽으로, 큰 숫자를 오른쪽으로 옮긴다.

5는 올바른 위치에 있게 되며 이 과정을 왼쪽과 오른쪽에서 재귀적으로 반복한다. 무엇을 골라도 작동하기에 선택은 중요하지 않다. 첫 번째 요소인 3을 피벗 포인트로 잡고 올바른 곳에 위치시킨다. 오른쪽은 4로 단일 요소가 되었다. 왼쪽은 첫 번째 요소인 1을 선택하고 어디에 두어야 할지 확인한다. 남은 것은 이 값보다 더 큰 다른 요소 하나이다. 오른쪽은 2가 되고 단일 요소이니 왼쪽은 모두 정렬된 상태가 된다. 이제 5의 오른쪽 첫 번째 요소인 7을 피벗 포인트로 잡고 6을 왼쪽으로 8을 오른쪽으로 옮긴다. 모두 단일 요소 배열이기에 정렬이 끝난다. 그림으로 대략적인 작동 원리를 보여주었기에 이해가 쉬웠다. 합병 정렬을 올바르게 이해하고 있다면 퀵 정렬이 조금 더 쉽게 다가올 수 있다.

애니메이션

 

주황색- 올바른 위치에 있는 요소

노란색- 피벗 포인트

초록색 - 피벗 포인트보다 작은 값

보라색 - 피벗 포인트보다 큰 값

 

 

 

그림을 보고 이해될 수 있지만 코드로 작성하는 건 쉽지 않다.

 

Pivot helper -  피벗 헬퍼 함수 작성

• 배열이 주어지면 요소를 피벗 포인트로 지정하여 배열 속 요소를 재배치하는 함수를 작성한다.
• 그런 다음 피벗보다 작은 값은 모두 왼쪽으로 이동하며 큰 값은 오른쪽으로 이동시킨다.
• 피벗보다 작거나 커야 할 뿐, 양쪽 안에 있는 요소의 순서는 중요하지 않다.
• helper 함수는 제자리에서 수행해야 한다. 즉, 새 배열을 생성하면 안 된다.
• 완료되면 helper함수는 피벗의 인덱스를 반환해야 한다.

Picking a pivot - 피벗 선택

• 퀵 정렬의 실행 시간은 선택 위치(피벗 포인트)에 따라 달라질 수 있다.
• 이상적으로는 데이터 집합의 중간 값이 되도록 선택해야 한다. 즉, 중간 값을 선택해서 왼쪽과 오른쪽의 크기가 같도록 한다. 하지만 데이터가 무엇인지, 순서가 어떻게 되어 있는지 모른다면 쉽지 않다. 
• 간단하게, 항상 첫 번째 요소를 피벗 포인트로 선택하도록 한다. 

Pivot Helper Example

let arr = [5, 2, 1 ,8, 4, 7, 6, 3]

pivot(arr); // 4
arr;
// any one of these is an acceptable mutation:
// [2, 1, 4, 3, 5, 8 ,7, 6]
// [1, 4, 3, 2, 5, 7, 6, 8]
// [3, 2, 1, 4, 5, 7, 6, 8]
// there are other acceptable mutations too!

배열이 있고 배열에서 피벗 함수를 호출한다면, 4 인덱스를 반환한다. 배열을 반환하지 않는 점을 주의하자.

하지만 배열을 살펴보면 바뀌었다. 첫 번째 요소를 골라서 피벗으로 선택하였다. 올바른 위치에 5가 있어서 왼쪽과 오른쪽의 요소가 재배치되었다. 순서는 중요하지 않다. 

 

Pivot 의사코드

• 이 함수는 세 가지 인수로 배열, 시작 인덱스(start index), 끝 인덱스(end index)를 받는다. 기본 값으로 시작 인덱스는 0, 끝 인덱스는 배열 길이의 -1 이다. 
• 배열 시작 부분에서 피벗을 선택한다. 피벗을 선택하는 것은 중간이나 마지막, 무작위 위치가 될 수 있다.
• 현재의 피벗 인덱스를 변수에 저장한다. 이렇게 하여 마지막에 피벗을 바꿀 위치를 계속 확인한다.
• 시작부터 끝까지 배열에 루프를 실행한다.
  • 살펴보는 요소보다 피벗이 더 클 경우 피벗 인덱스 변수를 증가시킨 다음 현재 요소와 피벗 인덱스의 요소를 교환한다. 
• 시작 요소(즉, 피벗)를 피벗 인덱스와 맞춘다. 

function pivot(arr, start=0, end=arr.length-1) {
    const swap = (arr, idx1, idx2) => {
        [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
    };
    
    let pivot = arr[start];
    let swapIdx = start;

    for (let i = start+1; i < arr.length; i++){
        if(pivot > arr[i]) {
            swapIdx++;
            swap(arr, swapIdx, i);
            console.log(arr)
        }
    }
    swap(arr, start, swapIdx);
    // arr: [3, 2, 1, 4, 5, 7, 6, 8]
    return swapIdx;
}

pivot([4,8,2,1,5,7,6,3]) // 3

let pivot = arr[start]로 해당 배열의 4 값이 들어온다.

let swapIdx = start로 0으로 시작한다.

배열의 첫 번째 요소는 pivot임으로 비교할 필요 없이 나머지 요소를 반복 수행한다.

pivot 값(현재 4)이 arr[i]보다 클 때 swapIdx를 증감시키고, swap 한다. 여기서 swap 하는 요소들은 arr[swapidx]와 arr[i]의 스왑이다. 위 배열로 예를 들면 i가 1일 때 arr[1] = 8이다. 해당 조건에 맞지 않으므로 다음 루프를 실행한다. 

i가 2일 때 arr[2] = 2이다. 조건에 부합하므로 swapIdx는 1이 되고 swap(arr, 1, 2)가 실행된다. 

arr[1]과 arr[2]의 위치를 바꾸는 것이다. 그렇게 되면 [4,2,8,1,...] 이런 식으로 2와 8의 자리가 바뀌게 된다.

배열의 끝까지 위와 같은 행동을 반복하게 되고 해당 루프는 [4, 2, 1, 3, 5, 7, 6, 8] 배열을 반환하게 된다.

마지막으로 pivot 값인 4를 올바른 위치에 두기 위해 스왑이 발생한다. 4보다 작은 수는 3개 있으므로 swapIdx는 3 값을 가질 테고 스왑 된다. 여기서 중요한 점은 숫자 4가 올바른 위치에 있으며 해당 index 값을 반환한다는 것이다. 

 

Quicksort 의사코드

• 전체 배열의 가장 앞에서 피벗 헬퍼를 호출한다.
• 업데이트된 피벗 인덱스를 헬퍼가 반환하면 피펏 헬퍼를 재귀적으로 왼쪽과 오른쪽에 호출한다. 새로운 배열을 만드는 것이 아니다. 
• 하위 배열에 2개 미만의 요소가 있을 때 수행된다. 

function quickSort(arr, left = 0, right = arr.length -1) {
    let pivotIndex = pivot(arr, left, right) // 3
}

quickSort([4,6,9,1,2,5,3])

먼저 앞서 작성한 pivot함수를 이용하여 피벗의 인덱스 값을 받고, 정렬해준다. 피벗 4의 index는 3이며 3을 리턴한다.

해당 배열은 [3,2,1,4,6,9,5]의 형태가 될 수 있다. 중요한 것은 4가 올바른 위치에 있다는 것이다. 4를 기준으로 왼쪽과 오른쪽에 재귀 호출한다. 왼쪽은 start로 left를 가지고, end로 prvotIndex-1을 가짐으로써 [3,2,1]에 대한 pivot함수가 발생하는 것이다. 

function quickSort(arr, left = 0, right = arr.length -1) {
    let pivotIndex = pivot(arr, left, right)
    // left
    quickSort(arr, left, pivotIndex-1);
    // right
    quickSort(arr, pivotIndex+1, right);
}

quickSort([4,6,9,1,2,5,3])

첫 quickSort가 실행되면서 pivotIndex는 3을 가지고 있었다. 재귀적으로 quickSort를 실행하며 quickSort(arr, 0, 2)가 실행되는 것이다. 오른쪽도 비슷하다. 하지만 위 코드는 base case가 없기에 영원히 동작한다. 어떻게 중단해야 할까? 하위 배열이 하나의 요소 길이에 도달했을 때 멈추려고 한다. 하지만 어떤 시점이든 이 배열은 전체 배열이다. 그렇기에 배열에 조건을 걸 순 없다. 바뀌는 것은 왼쪽과 오른쪽이다. 왼쪽과 오른쪽은 퀵 정렬을 호출할 때 재귀적으로 계속 바뀌고 있다. 하위 배열이 작아질수록 왼쪽과 오른쪽은 서로 가까워진다. 왼쪽이 0, 오른쪽이 6이었다가 왼쪽이 0, 오른쪽이 2가 된다. 따라서 왼쪽이 오른쪽보다 작을 때 코드를 계속 실행하려 하자. 

function quickSort(arr, left = 0, right = arr.length -1) {
  if(left < right) {
    let pivotIndex = pivot(arr, left, right) // 3
    // left
    quickSort(arr, left, pivotIndex-1);
    // right
    quickSort(arr, pivotIndex+1, right);
  }
    return arr;
}

오른쪽과 왼쪽이 같다면 한 요소를 살펴보고 있다는 의미이다. 정상적으로 동작한다.

 

Big O of Quicksort

Time Complexity (Best)	Time Complexity (Average)	Time Complexity (Worst)	Space Complexity
O(n log n)	O(n log n)	O(n^2)	O(log n)

 

Best Case, 합병 정렬처럼, n이 늘어나면 밑이 2인 log n의 분해가 수행되는 패턴을 보인다. 예를 들어 요소가 32개가 있을 때는 다섯 번 분해해야 한다. 64개의 요소가 있다면 여섯 번 분해해야 한다(log n). 하지만 각각 분해하는 단계마다 O(n)번의 비교를 수행해야 한다. 이렇게 해서 n log n이 된다. 합병 정렬과 같은 이유이다. 

 

Worst Case, 위의 알고리즘에서 피벗 함수는 언제나 첫 번째 항목을 피벗으로 선택한다. 데이터가 이미 정렬되어 있을 경우 문제가 된다. 현재의 퀵 정렬에 가장 나쁜 케이스를 이야기하는 것이다. 정렬이 되어 있다면 분해를 거칠 때마다 피벗으로 정한 항목 하나만 해당된다. 오른쪽 그림처럼 항목의 수만큼 계속 진행한다. Best Case에서 32개의 요소에 5번의 분해가 발생했다면, Worst 경우 32개의 요소에서 32번의 분해가 발생했다. O(n)의 분해와 O(n)의 비교를 수행해야 하므로 O(n^2) 시간이라는 결과가 나온다. 따라서 기본적으로 피벗을 고를 때 매번 가장 작은 요소, 가장 큰 요소가 선택되면 문제가 발생한다. 이러한 문제를 피하기 위해서 최선을 다할 수 있는 방법은 무작위 수나 중간 값을 선택할 수 있다. 하지만 최악의 케이스를 완전히 피할 수는 없다.