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

고지훈·2021년 12월 11일

Quick Sort 알고리즘 자료구조 정렬 알고리즘 퀵 정렬

LearningRecord

목록 보기

6/17

Goal

퀵 정렬에 대해 설명할 수 있다.
퀵 정렬 과정에 대해 설명할 수 있다.
퀵 정렬을 구현할 수 있다.
퀵 정렬의 시간복잡도와 공간복잡도를 계산할 수 있다.

Abstract

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

[분할 정복 방법]
문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다.

Quick Sort는 불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다. Merge Sort와 달리 Quick Sort는 배열을 비균등하게 분할한다.

Process

배열 가운데서 하나의 원소를 선택한다. 이렇게 선택한 원소는 피벗이라고 불린다.
피벗 앞에는 피벗보다 작은 값의 원소들이 오고, 피벗 뒤에는 피벗보다 큰 값의 원소들이 오도롯 피벗을 기준으로 배열을 둘로 나눈다. 이렇게 배열을 두 개로 나누는 작업을 분할이라고 한다.
분할된 두 개의 작은 배열에 대해 재귀적으로 이 과정을 반복한다.
재귀 호출이 한 번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.

Code

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

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

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

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

시간복잡도

비교 횟수(log₂n)
레코드의 개수 n이 2의 거듭제곱이라고 가정했을 때, n=2^3의 경우 2^3 -> 2^2 -> 2^1 순으로 줄어들어 순환 호출의 깊이가 3임을 알 수 있다.
위 공식을 일반화하면 n=2^k일 경우, k(k=log₂n)임을 알 수 있다.
최악의 경우
최악의 경우는 정렬하고자 하는 배열이 오름차순 정렬되어있거나 내림차순 정렬 되어있는 경우다.

따라서 최악의 시간복잡도는 순환 호출의 깊이 * 각 순환 호출 단계의 비교 연산 = n^2다. 이동 횟수는 비교 횟수보다 적으므로 무시할 수 없다.

공간복잡도

주어진 배열 안에서 교환을 통해, 정렬이 수행되므로 O(n)이다.

장점

불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환할 뿐만 아니라 한 번 결정된 피벗들이 추후 연산에서 제외되는 특성 때문에, 시간 복잡도가 다른 정렬 알고리즘과 비교했을때 보다 가장 빠르다.
정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다.