퀵 정렬 (Quick Sort)

개념

• 퀵 정렬은 불안정 정렬에 속하며, 다른 원소와의 비교 만으로 정렬을 수행하는 비교 정렬에 속한다.
• 대표적인 분할 정복 알고리즘이다.
• 하나의 리스트를 피벗을 기준으로 두 개의 비 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법
• 과정 
  1. 리스트 가운데서 하나의 원소를 고른다 이렇게 고른 원소를 **피벗(pivot)**이라고 한다 
  2. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다.
  3. 이렇게 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다. 
  4. 분할된 두 개의 작은 리스트에 대해 재귀적으로 위 과정을 반복한다. 재귀는 리스트 크기가 0이나 1이 될 때까지 반복한다.

▶ 재귀 호출이 한 번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해진다.

예제

• 배열 { 5, 3, 8, 4, 9, 1, 6, 2, 7 }이 저장되어 있다고 가정

• 피벗 값을 입력 리스트의 첫 번째 데이터로 하자. (다름 임의의 값이어도 상관없다)

▶ PIVOT 계수는 임의로 선정할 수 있으나, 중간 크기의 숫자를 PIVOT 계수로 선정하는 것이 가장 효율적이기 때문에 대부분 3개의 임의의 숫자를 랜덤으로 선택한 후 3개 중 가운데 값을 PIVOT 계수로 정하는 방법도 있다.

• 2개의 인덱스 변수(low, high)를 이용해서 리스트를 두개의 부분 리스트로 나눈다.
• 1회전 : 피벗이 5인 경우
  1. low는 왼쪽에서 오른쪽으로 탐색해가다가 피벗보다 큰 데이터(8)를 찾으면 멈춘다.
  2. high는 오른쪽에서 왼쪽으로 탐색하다가 피벗보다 작은 데이터(2)를 찾으면 멈춘다.
  3. low와 high가 가리키는 두 데이터를 서로 교환한다.
  4. 이 탐색-교환 과정은 low와 high가 엇갈릴 대까지 반복한다.

• 2회전 : 피벗(1회전의 왼쪽 부분 리스트의 첫 번째 데이터)이 1인 경우, 위와 동일한 방법으로 반복한다.
• 3회전 : 피벗(1회전의 오른쪽 부분 리스트의 첫 번째 데이터)이 9인 경우, 위와 동일한 방법으로 반복한다.

코드

public void quickSort(int[] arr, int left, int right) {
    int i, j, pivot, tmp;
    if (left < right) {
        i = left;   j = right;
        pivot = arr[(left+right)/2];
        //분할 과정
        while (i < j) {
            while (arr[j] > pivot) j--;
            // 이 부분에서 arr[j-1]에 접근해서 익셉션 발생가능함.
            while (i < j && arr[i] < pivot) i++;

            tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
        //정렬 과정
        quickSort(arr, left, i - 1);
        quickSort(arr, i + 1, right);
    }
}

 

장점

• 속도가 빠르다.
• 시간 복잡도가 O(N * log(N))를 가지는 다른 정렬 알고리즘과 비교했을 때도 가장 빠르다.
• 추가 메모리 공간을 필요로 하지 않는다.
• 퀵 정렬 O(log(N)) 만큼의 메모리를 필요로 한다.

단점

• 정렬된 리스트에 대해서는 퀵 정렬의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸린다.
• 퀵 정렬의 불균형 분할 방지하기 위하여 피벗을 선택할 때 더욱 리스트를 균등하게 분할할 수 있는 데이터를 선택한다.
• ex) 리스트 내의 몇 개의 데이터 중에서 크기순으로 중간 값을 피벗으로 선택한다.

 

시간복잡도

최선의 경우

• 비교 횟수
  • 순환 호출의 깊이 * 각 순환 호출 단계의 비교 연산 = nlogn
• 교환 횟수
  • 비교 횟수보다 적으므로 무시할 수 있다.
• 따라서 T(n) = O(nlog₂n)

 

최악의 경우

• 비교 횟수
  • 정렬 되어 있다면 계속 불균형하게 나누어지는 경우
  • 순환 호출의 깊이 * 각 순환 호출 단계의 비교 연산 = n^2
• 교환 횟수
  • 비교 횟수보다 적으므로 무시할 수 있다.
• 따라서 T(n) = O(n^2)
• 평균은 T(n) = O(nlog₂n)

정리

• 퀵 정렬은 정렬중 가장 빠르다는 장점도 있지만 반대로 최악일 경우 O(n^2)도 되는 정렬이다.
• 퀵 정렬이 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환할 뿐만 아니라, 한 번 결정된 피벗들이 추후 연산에서 제외되는 특성이 있다.
• 또한 블록이 점점 줄어들면서 계속 퀵 소트를 할 경우 불필요한 부하를 낳을 수 있다. 하여 어느 정도 블록이 줄어들면 삽입 정렬 등으로 정렬 방식을 변환 하는 것도 좋다.
• 피벗을 선택했는데 가장 작은값이나 큰값이면?의 것도 랜덤 값 3개를 선택하여 중간값으로 하는 방법 또 한 존재 하였다. 그래서 피벗에 따라 시간복잡도가 크게 달리진다.
• 안정적인 시간 복잡도를 요구하는 곳(사용자에게 데이터베이스 쿼리 결과생성 등) 에서 사용할 수 없다.

 

 

출처

• m.blog.naver.com/PostView.nhn?blogId=ljy9378&logNo=221508655059&proxyReferer=https:%2F%2Fwww.google.com%2F
• gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html