[알고리즘] 퀵 정렬 (quick sort)

퀵 정렬

퀵 정렬은 분할 정복 알고리즘으로 분류되나, 알고리즘이 수행되는 과정을 보면 정복 후 분할하는 알고리즘.

피봇이라는 배열의 원소를 기준으로 피봇보다 작은 숫자들은 왼편으로, 피봇보다 큰 숫자들은 오른편에 위치하도록 분할후, 피봇을 그 사이에 놓는 것.

분할된 부분문제들에 대해서도 동일한 과정을 순환적으로 수행한다.

수도코드 및 시간복잡도

Quicksort(A, left, right)
입력 : 배열 A[left] ~ A[right]
출력 : 정렬된 배열 A[left] ~ A[right]
if (left < right) //만약 그렇지 않으면, left == right으로 더이상 분할할 수 없는 크기
{
피봇을 A[left] ~ A[right] 중에 선택하고, 피봇을 A[left]와 자리를 바꾼 후, 
피봇과 배열의 각 원소를 비교하여 피봇보다 작은 숫자들은 A[left] ~ A[p-1]로 옮기고,
피봇보다 큰 숫자들은 A[p+1] ~ A[right]로 옮기며, 피봇은 A[p]에 놓는다.

Quicksort(A, left, p-1)
Quicksort(A, p+1, right)

코드를 짤 때 주어진 배열을 1,2,3,4 구역으로 분할

조금더 자세한 수도코드

quicksort(A[],p,r)
{
	if (p < r) then{
		q <- partition(A,p,r); //분할
		quicksort(A,p,q-1); //왼쪽 부분 배열 정렬
		quicksort(A,q+1,r); //오른쪽 부분 배열 정렬
	}
}

partition(A[],p,r)
{
	배열 A[p...r]의 원소들을 A[r]을 기준으로 양쪽으로 재배치하고
	A[r]이 자리한 위치를 리턴한다;
}

partition(A[], p, r)
{
	x<- A[r];//기준 원소
	i <- p-1;//i : 1구역의 끝지점
	for j <- i+1 to r-1 //j : 3구역 시작 지점
		if (A[j] =< x) then A[++i] <->  A[j]; //i값 증가후 A[i] <-> A[j] 교환
	A[i+1] <-> A[r]; //기준원소와 2구역 첫 원소 교환
return i+1;
}

/*
1구역 = 기준원소보다 작은 원소들
2구역 = 기준원소보다 큰 원소들
3구역 = 아직 정해지지 않은 원소들
for 루프가 한 바퀴 돌 때마다 3구역이 한 칸씩 줄어든다
for 루프가 한 바퀴 돌 때마다 1구역 또는 2구역 중 하나가 한 칸 늘어난다
2구역이 늘어날 때는 f만 1증가한다. for문 루프가 한 바퀴 돌 때마다 f는 1증가하므로
2구역을 늘리기 위해서는 아무 일도 할 필요가 없다
1구역이 늘어날 때는 i와 j가 동시에 1 증가한다
*/

• 퀵 정렬의 성능은 피봇 선택이 좌우.
  • 피봇으로 항상 가장 작은 수 가 선택되는 경우 （최악）
    • 1시행때 피봇은 n-1개의 원소들과 비교되므로 비교횟수는 n-1번 ,  2시행때 피봇은 n-2개의 원소들과 비교되므로 비교횟수는 n-2번. 따라서 시간복잡도는 (n-1) + (n-2) + (n-3) + ... + 2+1 = n(n-1)/2 = O(n^2)
  • 피봇으로 항상 가운데 수가 선택되는 경우（평균、최선） = 피봇을 기준으로 전체 배열이 1/2 로 나누어지는 경우
    • 각 층에선 각 원소가 각 부분의 피봇과 1회씩 비교된다. 따라서 각 층에서 비교횟수는 O(n) 이다. 총 비교 횟수는 O(n) x (층수) = O(n) x O(log2 n) = O(nlog2 n)

n/2^k = 1 이므로 k = log2 n 이다

• 피봇 선정 방법
  
  • 랜덤하게 선정
  • 3개의 숫자의 중앙값으로 선정 : 가장 왼쪽 숫자, 중간 숫자, 가장 오른쪽 숫자 중에서 중앙값으로 피봇 결정
  • 중앙값들 중의 중앙값 : 입력을 3등분하여 각 부분에서 3개의 중앙값을 찾아서 3개의 중앙값에서 중앙값을 피봇으로 결정
• 입력의 크기가 매우 클때, 퀵 정렬의 성능 향상을 위해 "삽입정렬"도 동시에 사용 / 입력 크기가 클때 가장 좋은 성능 보임.

---

• 본교재 문제 13）partition 알고리즘 작성하시오
  • "조금 더 자세한 수도코드" 참조
• 본교재 문제 14 ) 퀵 정렬 알고리즘의 피봇이 랜덤하게 정해진다고 가정하에 퀵 정렬의 알고리즘의 평균 시간복잡도가 O(nlog2 n)임을 보여라.

• 본교재 문제 13 ) 

 

 

코드 (c)

/*
Quicksort(A, left, right)
입력 : 배열 A[left] ~ A[right]
출력 : 정렬된 배열 A[left] ~ A[right]
if (left < right) //만약 그렇지 않으면, left == right으로 더이상 분할할 수 없는 크기
{
피봇을 A[left] ~ A[right] 중에 선택하고, 피봇을 A[left]와 자리를 바꾼 후, 
피봇과 배열의 각 원소를 비교하여 피봇보다 작은 숫자들은 A[left] ~ A[p-1]로 옮기고,
피봇보다 큰 숫자들은 A[p+1] ~ A[right]로 옮기며, 피봇은 A[p]에 놓는다.

Quicksort(A, left, p-1)
Quicksort(A, p+1, right)
*/
#include <stdio.h>
void swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
int partition(int a[], int left, int right)
{
	int x = a[right];//피봇
	int i = left - 1;//i = 1구역의 맨 오른쪽 지점, (2구역 맨 왼쪽 지점 = i+1)
	for (int f = i+1; f < right; f++)//f = 3구역의 맨 왼쪽 지점
	{
		if (a[f] <= x) {
			swap(&a[++i], &a[f]);
		}

	}
	swap(&a[right], &a[i+1]);//피봇과 2구역 첫 맨 왼쪽 원소 교환

	return i+1;
}
void Quicksort(int a[], int left, int right)
{
	int q;//피봇이 들어가는 인덱스
	if (left < right)
	{
		q = partition(a, left, right);
		Quicksort(a, left, q - 1);
		Quicksort(a, q + 1, right);
	}
}
int main() {
	int a[] = { 6,3,11,9,12,2,8,15,18,10,7,14 };
	int n = sizeof(a) / sizeof(int);
	int right = n - 1;
	int left = 0;
	Quicksort(a, left, right);
	//정렬 결과 출력
	for (int i = 0; i < right; i++)
	{
		printf("%d ", a[i]);
	}
	return 0;
}

 

---

 

BOJ

24091(c++)

https://www.acmicpc.net/problem/24091

24091번: 알고리즘 수업 - 퀵 정렬 2

1) 첫번째 시도

주어진 예시 입력에 대한 출력은 제시된 출력과 동일하게 나왔는데 판정 결과가 "틀렸습니다"로 떴다.

#include<iostream>
#include <vector>
using namespace std;
int global_count = 0;//전역변수
int K,N;

void swap(int* a, int* b)
{
	int tmp = *b;
	*b = *a;
	*a = tmp;
}
int partition(vector<int> a, int p, int r)
{

	int x = a[r]; //피봇 정하기
	int i = p - 1;//i : 1구역 맨 오른쪽 지점 , i+1 : 2구역 맨 왼쪽 지점
	for (int j = i + 1; j < r; j++)//j : 3구역 맨 왼쪽 지점
	{
		if (a[j] <= x) { //피봇보다 작은 원소인 경우->1구역으로 이동
			swap(&a[++i], &a[j]); //2구연 맨 왼쪽 원소와 3구역 맨 왼쪽 원소 교환
			global_count++;
			if (global_count == K) {
				for (int i = 0; i < N; i++)
				{
					cout << a[i]<<" ";
				}
				
			}
		}

	}

	if (i + 1 != r) {
		swap(&a[i + 1], &a[r]);// 피봇과 2구역 맨 왼쪽 지점 원소 교환
		global_count++;
		if (global_count == K) {
			for (int i = 0; i < N; i++)
			{
				cout << a[i]<<" ";
			}
			
		}
	}

	return i + 1;//피봇이 위치하게 된 인덱스 반환
}
void quicksort(vector<int> a, int p, int r)//K번 교환이 발생한 직후 시점 판별
{
	int q;
	if (p < r)
	{
		q = partition(a, p, r);
		quicksort(a, p, q-1);
		quicksort(a, q + 1, r);
		if (q == -5)
			return;
	}

}
int main() {
	//입력받기
	cin >> N;
	cin >> K;
	vector<int> a(N);
	for (int i = 0; i < N; i++)
	{
		cin >> a[i];
	}
	//결과 출력
	quicksort(a, 0, N - 1);
	if (global_count < K)
		cout << "-1";
	return 0;
}

2) 두번째 시도

앞선 코드에서 return -5 를 없애고, global_count라는 전역변수의 조건에 따라 출력이 되도록 하였다.

#include<iostream>
#include <vector>
using namespace std;
int global_count = 0;//전역변수
int K,N;

void swap(int* a, int* b)
{
	int tmp = *b;
	*b = *a;
	*a = tmp;
}
int partition(vector<int>& a, int p, int r)
{

	int x = a[r]; //피봇 정하기
	int i = p - 1;//i : 1구역 맨 오른쪽 지점 , i+1 : 2구역 맨 왼쪽 지점
	for (int j = i + 1; j < r; j++)//j : 3구역 맨 왼쪽 지점
	{
		if (a[j] <= x) { //피봇보다 작은 원소인 경우->1구역으로 이동
			swap(&a[++i], &a[j]); //2구연 맨 왼쪽 원소와 3구역 맨 왼쪽 원소 교환
			global_count++;
			if (global_count == K) {
				for (int i = 0; i < N; i++)
				{
					cout << a[i]<<" ";
				}
				cout << endl;
				
			}
		}

	}

	if (i + 1 != r) {
		swap(&a[i + 1], &a[r]);// 피봇과 2구역 맨 왼쪽 지점 원소 교환
		global_count++;
		if (global_count == K) {
			for (int i = 0; i < N; i++)
			{
				cout << a[i]<<" ";
			}
			cout << endl;
			
		}
	}

	return i + 1;//피봇이 위치하게 된 인덱스 반환
}
void quicksort(vector<int>& a, int p, int r)//K번 교환이 발생한 직후 시점 판별
{
	int q;
	if (p < r)
	{
		q = partition(a, p, r);
		quicksort(a, p, q-1);
		quicksort(a, q + 1, r);

	}

}
int main() {
	//입력받기
	cin >> N;
	cin >> K;
	vector<int> a(N);
	for (int i = 0; i < N; i++)
	{
		cin >> a[i];
	}
	//결과 출력
	quicksort(a, 0, N - 1);
	if (global_count < K)
		cout << "-1";
	return 0;
}