퀵 정렬(Quick Sort) 이란

퀵 정렬

기준 데이터를 설정하고, 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 정렬 알고리즘이다.

퀵 정렬에서 선택한 기준 데이터를 피봇 데이터라고 한다.

 

다양한 상황에서 이용되는 표준 정렬 알고리즘이며,
Merge Sort(병합 정렬)과 마찬가지로 정렬 라이브러리의 근간이 되곤 하는 알고리즘이다.

 

퀵 정렬의 과정은 다음과 같다.

 

1. 기준(피봇) 데이터를 설정한다.(기본적인 형태에서는 첫번째 데이터를 피봇으로 삼는다.)
2.1. 배열 처음부터 오른쪽으로 순회하며 피봇보다 큰 데이터의 인덱스를 찾는다.
2.2. 배열 마지막부터 왼쪽으로 역순회하며 피봇보다 작은 데이터의 인덱스를 찾는다.
2.3. 작은 데이터와 큰 데이터를 기준으로, 두 인덱스에 위치한 데이터를 swap 할 때 두 데이터가 오름차순으로 정렬된다면 swap을 수행한다.
2.4. 그렇지 않다면 피봇과 작은 데이터의 위치를 swap한다.

3. 2.4의 과정이 일어날 때 까지 스왑을 반복하며, 피봇이 이동하면 피봇 왼쪽과 오른쪽 배열에 대해서 퀵 정렬을 수행한다.

 

피봇 왼쪽 배열은 작은 데이터들의 집합이며 오른쪽은 큰 데이터들의 집합이다.

두 배열 모두 정렬되어있지 않으므로 각각 퀵 정렬을 수행해줘야 한다.

 

이와 같이 배열에 재귀적으로 퀵정렬을 수행하며, 정렬을 위한 범위를 점점 좁혀가는 방식으로 동작하게 된다.

 

gif를 통해 이해해보자.

출처 : https://velog.io/@yaincoding/퀵-정렬Quick-Sort

 

 

퀵정렬을 JS 코드로 구현해보았다.

const arr = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8];

function quickSort(arr, start, end){
    if( start >= end) return;
    const pivot = start;
    let left = start + 1;
    let right = end;

    while(left <= right){
        while(left <= end && arr[left] <= arr[pivot]){
            left +=1;
        }
        while(right > start && arr[right] >= arr[pivot]){
            right -= 1;
        }
        if(left > right){
            [arr[right], arr[pivot]] = [arr[pivot], arr[right]];
        } else {
            [arr[left], arr[right]] = [arr[right], arr[left]];
        }
    }
    quickSort(arr, start, right-1);
    quickSort(arr, right+1, end);
}

quickSort(arr, 0, arr.length - 1);

해당 코드에서는 피봇을 첫번째 인덱스 원소로 설정했다.

 

left 변수에는 피봇보다 큰 인덱스, right 변수에는 피봇보다 작은 인덱스의 위치를 기억한다.

left > right 이면(left와 right 인덱스 변수를 스왑했을 때 오름차순이 아니면), 피봇과 right 인덱스(작은 데이터)를 교환한다.
left <= right 이면 스왑 시 오름차순으로 정렬되므로, 두 데이터를 스왑한다.

 

바깥 while문이 종료되면 피봇을 기준으로 왼쪽에는 작은 데이터들, 오른쪽에는 큰 데이터들이 위치하므로 각각 퀵정렬을 수행한다.

---

퀵 정렬의 시간복잡도

이상적으로는 O(NlogN), 최악의 경우에는 O(N^2)의 시간복잡도를 기대할 수 있다.

 

이상적인 경우에서는, 모든 분할이 절반 씩 일어난다는 가정을 하면 된다.

분할시마다 데이터가 절반씩 줄어드므로, 순환 호출의 깊이가 log2 N을 보인다.
각 분할시 수행하는 비교 연산은 동일하게 N번이 이루어진다.

 

그러므로 log2 N * N = Nlog2 N 의 시간복잡도를 보인다.

 

최악의 경우에서는, 이미 정렬된 배열에 대해 퀵정렬을 수행하는 경우이다.

퀵정렬의 수행 결과로는 항상 피봇 오른쪽에만 배열이 존재하게 된다.

그렇다면 N회의 분할(순환 호출)이 일어나게 되고, 비교 연산 또한 평균 N번을 수행한다.

 

그러므로 N * N = N^2의 시간복잡도를 보인다.

---

장점

평균적으로 매우 빠른 수행속도를 자랑한다. o(NlogN)
주어진 배열 안에서 인덱스끼리 Swap을 통해 정렬이 수행되므로 공간 효율적이다. (= 제자리 정렬)

---

단점

불안정 정렬이다.(=중복 값이 입력순서와 동일하게 정렬됨을 보장하지 않는다.)

정렬된 리스트에 대해서는 O(N^2)의 수행시간을 요구한다.

• 퀵 정렬의 O(N^2) 시간복잡도 문제를 해결하기 위해서는..?
  • 현재 알고리즘에서는 첫번째 원소를 피봇으로 선택하고 있기 때문에, 이미 정렬된 배열에서 O(N^2) 문제를 보인다.
  • 그러므로 첫번째 원소가 아닌 다른 원소를 선택하도록 알고리즘을 설계하면 되겠다.