[Algorithm] Quick Sort

6720·2023년 7월 5일

이거 모르겠어요

목록 보기

25/38

퀵 정렬

불안정 정렬*에 속하며, 다른 원소와의 비교만으로 정렬를 수행하는 비교 정렬에 속함.

*불안정 정렬: 중복된 값이 입력 순서와 동일하지 않게 정렬되는 알고리즘.
EX) 퀵 정렬, 선택 정렬, 계수 정렬
(반대 - 안정 정렬) : 중복된 값을 입력 순서와 동일하게 정렬하는 정렬 알고리즘.
EX) 삽입 정렬, 병합 정렬, 버블 정렬

분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법
합병 정렬과는 달리 리스트를 비균등하게 분할함.

분할 정복 방법

문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이며, 대개 순환 호출을 이용하여 구현함.

1) 리스트 안에 있는 한 요소를 선택하며, 이를 피벗(pivot)이라고 지정함.
2) 피벗을 기준으로 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮겨짐.
3) 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬함.

분할된 부분 리스트에 대하여 순환 호출을 이용하여 정렬을 반복함.
부분 리스트에서도 다시 피벗을 정하고 피벗을 기준으로 2개의 부분 리스트로 나누는 과정을 반복함.
4) 부분 리스트들이 더 이상 분할이 불가능할 때까지 반복함.

특징

장점
- 속도가 빠름. - $O(n\log_2n)$ 보다 빠르다고 함.
- 추가 메모리 공간을 필요로 하지 않음. - $O(\log n)$ 만큼의 메모리를 필요로 함.
단점
- 정렬된 리스트에 대해서는 퀵 정렬의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸림.
퀵 정렬의 불균형 분할을 방지하기 위하여 피벗을 선택할 때 더욱 리스트를 균등하게 분할할 수 있는 데이터를 선택함.
- EX) 리스트 내의 몇 개의 데이터 중에서 크기 순으로 중간 값(medium)울 피벗으로 선택함.
피벗을 어느 곳을 기준으로 잡을 것인지가 관건이며, 이로 인해 구현하는 방식이 다양함.

코드

왼쪽 피벗 선택

private void sort(int[] arr, int lo, int hi) { // lo, hi: 현재 부분 배열의 끝
	if (lo >= hi) return;
	
	int pivot = partition(arr, lo, hi);
	sort(arr, lo, pivot - 1);
	sort(arr, pivot + 1, hi);
}

private int partition(int[] arr, int left, int right) {
	int lo = left;
	int hi = right;
	~~~~int pivot = arr[left]; // 왼쪽에서 피벗 선택

	while (lo < hi) {
		while (arr[hi] > pivot && lo < hi) {
			// hi의 요소가 pivot보다 작거나 같은 원소를 찾을 때까지 감소
			hi--;
		}
		
		while (arr[lo] <= pivot && lo < hi) {
			// lo의 요소가 pivot보다 큰 원소를 찾을 때까지 증가
			lo++;
		}
		swap(arr, lo, hi); // 요소 교환
	}
	swap(arr, left, lo); // 처음에 pivot으로 설정했던 위치의 원소와 lo의 요소 교환
	
	return lo; // 최종적으로 위치한 피벗의 위치
}

private void swap(int[] arr, int i, int j) {
	int temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
}

오른쪽 피벗 선택

private void sort(int[] arr, int lo, int hi) { // lo, hi: 현재 부분 배열의 끝
	if (lo >= hi) return;
	
	int pivot = partition(arr, lo, hi);
	sort(arr, lo, pivot - 1);
	sort(arr, pivot + 1, hi);
}

private int partition(int[] arr, int left, int right) {
	int lo = left;
	int hi = right;
	int pivot = arr[right]; // 오른쪽에서 피벗 선택

	while (lo < hi) {
		while (arr[lo] < pivot && lo < hi) {
			// lo의 요소가 pivot보다 크거나 같은 원소를 찾을 때까지 증가
			lo++;
		}
		
		while (arr[hi] >= pivot && lo < hi) {
			// lo의 요소가 pivot보다 작은 원소를 찾을 때까지 감소
			hi--;
		}
		swap(arr, lo, hi); // 요소 교환
	}
	swap(arr, right, hi); // 처음에 pivot으로 설정했던 위치의 원소와 hi의 요소 교환
	
	return hi; // 최종적으로 위치한 피벗의 위치
}

private void swap(int[] arr, int i, int j) {
	int temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
}

중간 피벗 선택

private void sort(int[] arr, int lo, int hi) { // lo, hi: 현재 부분 배열의 끝
	if (lo >= hi) return;
	
	int pivot = partition(arr, lo, hi);
	sort(arr, lo, pivot);
	sort(arr, pivot + 1, hi);
}

private int partition(int[] arr, int left, int right) {
	int lo = left - 1;
	int hi = right + 1;
	int pivot = arr[(left + right) / 2]; // 중간에서 피벗 선택

	while (true) {
		// lo 요소가 pivot보다 크거나 같은 요소를 찾을 때까지 증가
		do {
			lo++;
		} while (arr[lo] < pivot);

		// hi 요소가 pivot보다 작거나 같은 요소를 찾을 때까지 감소
		do {
			hi--;
		} while (arr[hi] > pivot && lo <= hi);

		// 값이 엇갈렸다면 요소 교환을 하지 않음.
		if (lo >= hi) return hi;

		swap(arr, lo, hi);
	}
}

private void swap(int[] arr, int i, int j) {
	int temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
}

내림차순(왼쪽 피벗 선택)

private void sort(int[] arr, int lo, int hi) { // lo, hi: 현재 부분 배열의 끝
	if (lo >= hi) return;
	
	int pivot = partition(arr, lo, hi);
	sort(arr, lo, pivot - 1);
	sort(arr, pivot + 1, hi);
}

private int partition(int[] arr, int left, int right) {
	int lo = left;
	int hi = right;
	~~~~int pivot = arr[left]; // 왼쪽에서 피벗 선택

	while (lo < hi) {
		while (arr[hi] < pivot && lo < hi) {
			// hi의 요소가 pivot보다 크거나 같은 원소를 찾을 때까지 감소
			hi--;
		}
		
		while (arr[lo] >= pivot && lo < hi) {
			// lo의 요소가 pivot보다 작은 원소를 찾을 때까지 증가
			lo++;
		}
		swap(arr, lo, hi); // 요소 교환
	}
	swap(arr, left, lo); // 처음에 pivot으로 설정했던 위치의 원소와 lo의 요소 교환
	
	return lo; // 최종적으로 위치한 피벗의 위치
}

private void swap(int[] arr, int i, int j) {
	int temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
}