퀵 정렬(Quick Sort)

개념

퀵 정렬은 분할 정복(divide and conquer) 방법을 통해 주어진 배열을 정렬한다.

퀵 정렬은 불안정 정렬이며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬이다.

( * 분할 정복 알고리즘(Divide and conquer algorithm)은 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이나 알고리즘이다.)

 

과정

1. 리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다.
2. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.
3. 분할된 두 개의 작은 리스트에 대해 재귀적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다.

 

구현(Java)

• 정복 (Conquer)

       부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 방법을 적용한다.

public void quickSort(int[] array, int left, int right) {
    if(left >= right) return;
    
    // 분할 
    int pivot = partition(); 
    
    // 피벗은 제외한 2개의 부분 배열을 대상으로 순환 호출
    quickSort(array, left, pivot-1);  // 정복(Conquer)
    quickSort(array, pivot+1, right); // 정복(Conquer)
}

 

 

• 분할 (Divide)

       배열을 피벗을 기준으로 비균등하게 2개의 부분 배열 (왼쪽 : 피벗보다 작은 요소들, 오른쪽 : 피벗보다 큰 요소들) 로 분할한다.

public int partition(int[] array, int left, int right) {
    
    int pivot = array[left]; // 가장 왼쪽값을 피벗으로 설정
    int i = left, j = right;
    
    while(i < j) {
        while(pivot < array[j]) {
            j--;
        }
        while(i < j && pivot >= array[i]){
            i++;
        }
        swap(array, i, j);
    }
    array[left] = array[i];
    array[i] = pivot;
    
    return i;
}

 

시간복잡도

최악의 경우(Worst cases) : T(n) = O(n^2)

최선의 경우(Best cases) : T(n) = O(nlog₂n)

평균의 경우(Average cases) : T(n) = O(nlog₂n)

 

비교

시간 복잡도가 O(nlog₂n)를 가지는 다른 정렬 알고리즘과 비교했을 때 가장 빠르다.

JAVA에서 Arrays.sort() 로 구현되어 있다.

 

 

 

 

 

 

 

---

 

참고 

https://gyoogle.dev/blog/algorithm/Quick%20Sort.html