4강 - 퀵 정렬 (Quick Sort)

다양한 퀵 정렬 중에서 보편화된 방법 하나를 다루겠습니다.

 

1. 퀵 정렬

1) 정의

 

2) 특징

1> 분할 정복 알고리즘(divide and conquer)의 하나

2> 시간 복잡도: O(nlogn ~ n^2)

3> 불안정 정렬

4> 비교 정렬 (다른 원소와의 비교만으로 정렬을 수행)

 

cf> pivot: 기준 (정도로 생각하면 된다.)

농구에서 pivot이 한 발만 땅에 대고 움직이는 것을 연상하면 이해가 쉽습니다.

- pivot을 무엇으로 하느냐에 따라 퀵 정렬 종류도 다양합니다.

 

2. 구체적인 과정

(오름차순을 기준)

1) 구체적인 순서

1> 맨 앞의 element를 pivot으로 설정

2> pivot을 제외하고

- 맨 왼쪽부터 pivot보다 큰 숫자를 찾고 

- 맨 오른쪽부터 pivot보다 작은 숫자를 찾는다.

(엇갈리는 경우가 생긴다.

3> 2>에서 찾은 두 수를 교체한다.

- 큰 수와 작은 수를 잘 찾았다면 해당 두 수를 교체하고

- 큰 수와 작은 수를 엇갈리게 (큰 수가 right에 있고 작은 수가 left에 있는) 되면 pivot과 right를 교체

4> 이제 pivot으로 인해 분할된 부분 각각에서 퀵 정렬을 진행한다.

5> 각 분할에서 가장 첫 번째 원소를 pivot으로 설정 (이후 2>~4>를 반복적으로 진행

 

2) 재귀를 이용해서 퀵 정렬을 수행하는 함수를 따로 만든다.

1> parameter로 받을 것들

- array 

- 퀵소트를 진행하려는 시작 점 

- 퀵소트를 진행하려는 끝 점

2> 예외 상황

- 퀵소트를 진행하려는 부분의 원소가 하나일 때 (재귀함수 탈출 조건 만드는 곳)

 

 

3. 구현

 

#include <iostream>
using namespace std;
const int MAX = 1000000;

void swap(int &a, int &b)
{
	int temp = a;
	a = b;
	b = temp;
}

void quickSort(int *arr, int start, int end)
{
	if (start >= end) return; // 원소가 1개 남은 경우 재귀의 탈출 조건
	int pivot = start;
	int left = start + 1;
	int right = end;

	while (left <= right) // 엇갈릴 때까지 반복
	{
		while (arr[left] <= arr[pivot]) // pivot보다 큰 값을 만날 때까지 left 이동
		{
			left++;
		}
		while (arr[right] >= arr[pivot] && right > start) // pivot보다 작은 값을 만날 때까지 right 이동
		{
			right--;
		}
		if (left > right)
		{
			swap(arr[pivot], arr[right]);
		}
		else
		{
			swap(arr[left], arr[right]);
		}
	}
	quickSort(arr, start, right - 1);
	quickSort(arr, right + 1, end);
}

int main()
{
	int N;
	cin >> N;
	int arr[MAX];
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
	quickSort(arr, 0, N - 1);
	for (int i = 0; i < N; i++)
	{
		cout << arr[i] << '\n';
	}
}