[정렬 알고리즘] #4. 퀵 정렬 (Quick Sort)

퀵 정렬

분할 정복 알고리즘 중 하나로 평균적으로 매우 빠른 속도를 가지고 있다. 퀵 정렬의 특징으로는 비 균등하게 분할을 한다.

알고리즘

퀵 정렬은 다음과 같이 진행된다.

 

• 입력된 배열을 pivot을 기준으로 비균등하게 2개의 배열로 나눈다. pivot을 중심으로 왼쪽에는 pivot보다 작은 요소, 오른쪽에는 pivot보다 큰 요소들로 나눈다.
• 분할된 배열들을 가지고 다시한번 새로운 pivot을 기준으로 비 균등하게 2개의 배열로 나눈다.
• 더 이상 분할이 안될때까지 반복적으로 진행한다.

// javascript 코드
const quickSort = (arr, left, right) => {
    if (left >= right) return;
    let low = left + 1;
    let high = right;

    let pivot = arr[left];

    if (left < right) {
        // 반복문을 돌면서 pivot보다 작은 요소들은 왼쪽에 큰 요소들은 오르쪽에 배치한다.
        while (low <= high) {
            while (arr[low] <= pivot && low <= right) {
            	low++;
            }
            while (arr[high] >= pivot && high > left) {
            	high--;
            }

            if (low < high) {
                const temp = arr[low];
                arr[low] = arr[high];
                arr[high] = temp;
            } else {
                // low 와 high가 엇갈리면 pivot값과 high를 바꾼다.
                // 그리고 반복문이 종료된다.
                const temp = arr[high];
                arr[high] = arr[left];
                arr[left] = temp;
            }
        }
        quickSort(arr, left, high - 1);
        quickSort(arr, low, right);
        }
    }
}

특징

• 속도가 빠르다. 평균적으로 시간 복잡도 O(nlog₂n)을 가지고 있다.
• 그러나 이미 정렬된 배열에 대해서는 O(n²) 의 시간 복잡도를 가진다.
• O(log n) 만큼의 메모리만 필요하다.

pivot

주로 배열의 맨 왼쪽 또는 오른쪽 요소를 pivot으로 선택하지만 배열의 중간 요소를 고르기도 한다. 또는 매번 랜덤 한 요소를 pivot으로 선택하기도 한다. 주로 배열의 왼쪽, 오른쪽, 가운데 요소 중에 크기가 중간이 값을 pivot으로 선택하는 경우가 많다.