퀵 정렬 (Quick Sort) - middle pivot

퀵 정렬 이란

퀵 정렬의 메커니즘은 크게 다음과 같다.

 

하나의 리스트를 피벗(pivot)을 기준으로 두 개의 부분리스트로 나누어 하나는 피벗보다 작은 값들의 부분리스트, 다른 하나는 피벗보다 큰 값들의 부분리스트로 정렬한 다음, 각 부분리스트에 대해 다시 위처럼 재귀적으로 수행하여 정렬하는 방법이다.

 

퀵 정렬방법

1. 피벗을 하나 선택한다.
2. 피벗을 기준으로 양쪽에서 피벗보다 큰 값, 혹은 작은 값을 찾는다. 왼쪽에서부터는 피벗보다 큰 값을 찾고, 오른쪽에서부터는 피벗보다 작은 값을 찾는다.
3. 양 방향에서 찾은 두 원소를 교환한다.
4. 왼쪽에서 탐색하는 위치와 오른쪽에서 탐색하는 위치가 교차할 때까지 2번으로 돌아가 위 과정을 반복한다.
5. 교차한 지점을 기준으로 두 개의 부분리스트로 나누어 1번으로 돌아가 해당 부분리스트의 길이가 1이 아닐 때까지 1번 과정을 반복한다.

피벗을 선택하는 과정은 여러 방법이 있는데, 대표적으로 세 가지가 있다.
현재 부분배열의 가장 왼쪽 원소가 피벗이 되는 방법, 중간 원소가 피벗이 되는 방법, 마지막 원소가 피벗이 되는 방법이다.

 

보통 중간 원소를 피벗으로 선택한다.

 

피벗이 중앙에 위치되어 리스트를 절반으로 나눈다고 할 때, N개의 데이터가 있는 리스트를 1개까지 쪼개어 트리로 나타내게 되면 이진트리(Binary Tree) 형태로 나온다는 것은 우리가 확인할 수 있다.

---

최악의 경우도 있다. 정렬된 상태의 배열을 정렬하고자 할 때다.

왼쪽을 기준으로 피벗을 잡을 때를 생각해 보자.

 

이 상태에서 1차 정렬을 진행하면

데이터가 전부 swap이 되었을 것이고, 또 가장 마지막에 위치해 있을 것입니다.

아래 그림과 같이 최악의 트리 구조가 나올 수 있다.

 

이는 왼쪽 피벗을 선택하건, 오른쪽 피벗을 선택하건 위와 같이 트리가 치중되는 건 마찬가지다.

 

중간 피벗이 선호되는 이유가 바로 이러한 이유 때문이다. 그러면 거의 정렬된 배열이더라도 거의 중간지점에 가까운 위치에서 왼쪽 리스트와 오른쪽 리스트가 균형에 가까운 트리를 얻어낼 수 있기 때문이다.

---

퀵 정렬 - JAVA

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class QuickSort {
    
    public static void sort(int[] numArr) {
        quickSort(numArr, 0, numArr.length - 1);
    }

    private static void quickSort(int[] numArr, int nStartIdx, int nEndIdx) {
        //더이상 정렬하지 않아도됨.
        if(nStartIdx >= nEndIdx) {
            return;
        }
        int nMidIdx = partitionSort(numArr, nStartIdx, nEndIdx);
        
        quickSort(numArr, nStartIdx, nMidIdx - 1);
        quickSort(numArr, nMidIdx, nEndIdx);
    }

    private static int partitionSort(int[] numArr, int nStartIdx, int nEndIdx) {
        //중간 요소를 피벗으로 설정
        //int nPivotIdx = (nStartIdx + nEndIdx) / 2;   //overflow 발생위험 
        int nPivotIdx = nStartIdx + (nEndIdx - nStartIdx) / 2;
        int nPivot = numArr[nPivotIdx];
        
        //교차할때까지 반복
        while(nStartIdx <= nEndIdx) {
            //compare pivot value
            while(numArr[nStartIdx] < nPivot) nStartIdx++;
            while(numArr[nEndIdx] > nPivot) nEndIdx--;
            
            if(nStartIdx <= nEndIdx) {
                swap(numArr, nStartIdx, nEndIdx);
                nStartIdx++;
                nEndIdx--;
            }
            
        }
        return nStartIdx;
    }

    private static void swap(int[] numArr, int nStartIdx, int nEndIdx) {
        int nTempVal = numArr[nStartIdx];
        numArr[nStartIdx] = numArr[nEndIdx];
        numArr[nEndIdx] = nTempVal;
    }

}

 

중간요소 선택

int nPivotIdx = nStartIdx + (nEndIdx - nStartIdx) / 2;

 

 

Pivot 값 비교

Pivot의 인덱스가 중요한 것이 아닌 Pivot의 값이 중요하다. 그 이유는 그림을 통해 확인해 보자.

• pivot값이 5이기 때문에 처음 left의 인덱스는 0번에서 pivot이 위치한 곳까지 오게 되고 right은 맨 끝에서 2가 위치한 곳까지 오게 된다.
• 왼쪽 인덱스와 오른쪽 인덱스가 아직 교차하지 않은 상태이므로 left와 right의 값을 바꿔준다.
• swap이후 교차할 때까지 반복 진행한다.
• left는 7을 만나 멈추고 right은 이미 pivot이기 때문에 그대로
• left와 right index가 아직 서로 교차하기 전이므로 left값과 right값을 swap