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

0. 목차(클릭시 이동)

 

1. 퀵정렬의 개념
2. 퀵정렬의 과정 정리
3. 퀵정렬의 시간복잡도
4. 퀵정렬 코드

---

1. 퀵정렬의 개념

 

• 퀵정렬은 이름 그대로, 다른 정렬보다 빠른 수행속도로 데이터를 정렬하는 기법이다.
• 퀵정렬은 버블정렬, 삽입정렬, 선택정렬과 같이 다른원소와 비교를 하며 정렬을 하는 비교정렬이다
• 한 문제를 작은 문제로 나눈뒤, 각각의 작은 문제들을 해결하고, 그 결과를 종합하여 본 문제를 해결하는 분할정복 알고리즘이다.
• 피봇(Pivot) = 분할된 배열을 정렬할 기준원소
• left = 분할된 배열에서 피봇값보다 작은 원소들을 판별해주는 포인터
• right = 분할된 배열에서 피봇값보다 큰 원소들을 판별해주는 포인터

먼저 초기값으로 배열에 5 1 4 7 2 3 8 6 9 가 있다고 가정을 해보자.

 

1. 피봇을 설정을 해주는데, 피봇의 인덱스는 랜덤으로 해도되고, 편하게 처음원소 또는 마지막 원소를 피봇으로 잡아도 된다. 여기서는 피봇을 분할된 배열의 제일 처음 원소로 설정을 하겠다. 피봇을 설정한 뒤, 피봇을 제외한 배열의 첫 원소를 left로, 맨 마지막 원소를 right로 포인터 설정을 해준다.

 

2. left를 우측으로 이동을 시키며, 피봇보다 큰 값에 도착하면 잠시 멈추고, right를 좌측으로 이동시키며 피봇보다 작은 값이 있다면 잠시 멈춘다. (노란색으로 색칠된곳은 해당 단계에서 분할이 완료된 원소를 말한다.)

 

3. left와 right가 교차되지 않았을 때, 현재 left값에는 Pivot 보다 큰 값이, right에는 Pivot보다 작은 값이 있다. 이 둘을 바꾸어 준다.

 

4. 그런뒤, 2번, 3번을 left와 right가 교차될때까지 반복해준다.

 

5. 교차가 됐다면, Pivot의 값과 right포인터가 가리키고있는 값을 교환해준다. 그러면 완벽히 right의 좌측으로는 Pivot값보다 작은값들이, right의 우측으로는 Pivot값보다 큰 값들이 모여있는 부분리스트가 완성이 됐을것이다. 따라서 Pivot의 값은 자신의 자리를 완벽하게 찾았다고 할 수 있게된다. (파란색으로 색칠된곳은 정렬이 완료된 원소를 의미한다.

 

6. right위치에 있는 원소는 정렬이 된 원소이므로, right의 좌측에 있는 부분리스트와 right의 우측에 있는 부분리스트를 각각 1~6번 과정을 거쳐 각각의 부분문제를 해결하면 된다.

 

 

 

다음은 위의 좌측 부분리스트를 정렬하는 그림이다.

해당 부분리스트는, 2~3번 과정이 없는 경우이다. 이 경우에서도 2는 자신의 자리를 찾아간 것이다. 2를 기준으로 좌측과 우측을 부분리스트로 본 뒤, 위의 과정을 반복해주면 된다. 단 부분리스트의 원소가 1개라면, 이미 정렬이 된 상태라고 보면된다.

 

 

1은 부분리스트의 원소개수가 1개이므로, 정렬이 완료된상태이고, 4,3의 부분리스트를 보면, Pivot을 설정해준뒤 , left와right를 설정했을때, 바로 교차하는 상태이므로, 바로 바꾸어주면 정렬이 완료된다.

 

부분리스트들을 모두 정렬한 결과는 아래와 같다.

 

우측 부분리스트 또한 위의 좌측 부분리스트를 정렬하는 방법과 같이 분할, 정복을 하며 정렬을 완성하면 된다.

 

---

2. 퀵정렬의 과정 정리

 

1. 분할된 배열에서 Pivot과 Left, Right를 설정해준다.
2. Left를 오른쪽 방향으로 탐색하며, Pivot값보다 큰 값을 만나면 잠시 멈춘다.
3. Right를 왼쪽 방향으로 탐색하며, Pivot값보다 작은 값을 만나면 잠시 멈춘다.
4. Left와 Right가 교차하지 않았다면, Left가 가리키고있는 값과 Right가 가리키고있는 값을 교환해준다.
5. Left와 Right가 교차할때까지, 2~4번 과정을 반복해준뒤, 교차했다면 Right값과 Pivot값을 교환해준다.
6. Right인덱스를 기준으로 좌 우측으로 서브 리스트를 설정해준뒤, 각각 1~6번 과정을 실행해준다.
7. 만약 서브리스트의 길이가 1이라면, 정렬된 상태이므로, 과정을 생략하고 끝내도된다

---

3. 퀵정렬의 시간복잡도

 

퀵정렬은 최선의 경우와 최악의 경우가 있다.

서브리스트가 이상적으로 반반씩 쪼개지는 경우, 정렬해야 하는 리스트의 길이를 N이라고 한다면

Log N번의 분할,정복을 하고, 각각 분할,정복에서의 비교연산은 평균 N번의 비교를 하므로, 최선의 경우 시간복잡도는 O(NlogN)시간이 걸린다.

 

하지만 최악의 경우를 알아보자. 

위와 같이, 매번 분할 단계에서 부분리스트가 1개와 나머지로 나뉘어질때, 최악의 경우가 된다. 꼭 1개가 아니라도, 불균등하게 두 서브리스트개수의 차이가 많이난다면 시간이 O(NlogN)보다 오래걸린다.

왜냐하면, 제일 최악의 경우인 서브리스트가 1개, 나머지로 나눠지는경우를 보면, 분할정복을 호출하는 횟수가 총 N번이 되고, 각 분할정복단계에서 비교하는 연산이 평균 N회 이루어지므로 , 최악의 경우 O(N²)이 된다.

 

하지만 평균적으로는 O(NlogN)의 시간복잡도를 가진다.

이때, 다른 O(NlogN)의 시간복잡도를 가지는 다른 정렬 알고리즘도 많은데, 왜 이 알고리즘이 Quick 이란 이름이 붙었을까? 그 이유는, 해당 정렬을 할때, 피봇은 정렬에 포함시키지 않기때문에, N의 값이 커지면 커질수록 Quick Sort의 속도가 다른 정렬에 비해 더욱더 빨라지기 때문이다.

---

4. 퀵정렬 코드 (C++)

 

#include <iostream>
#include<algorithm>
using namespace std;

int arr[] = { 5,1,4,7,2,3,8,6,9 };//편의를 위해 전역변수로 설정

//배열을 전역변수로 설정해서 인덱스를 가지고 스왑하는 함수
void change(int a, int b) {
	int temp = arr[a];
	arr[a] = arr[b];
	arr[b] = temp;
}

void quick_sort(int start, int end) {
	if (start >= end) {
		return;
	}
	cout << "\nSub List before quick_sort:\n";
	for (int i = start; i <= end; i++) {
		cout << arr[i] << " ";
	}
	cout << "\n";
	int pivot = start;
	cout << "Pivot = " << arr[pivot] << "\n";
	int left = start;
	int right = end+1;
	do {
		//범위안에서 pivot보다 큰 원소를 보면 멈춤
		do {
			left++;
		} while (left <= end && arr[left] < arr[pivot]);


		//범위안에서 pivot보다 작은 원소를 보면 멈춤
		do {
			right--;
		} while (right >= start && arr[right] > arr[pivot]);

		//left와 right가 교차된 상태가 아니면 스왑
		if (left < right) {
			change(left, right);
		}
	} while (left<right);
	//피봇값과 right위치의 값을 교환
	change(pivot, right);

	cout << "SubList after quick_sort:\n";
	for (int i = start; i <= end; i++) {
		cout << arr[i] << " ";
	}
	cout << "\n";

	//서브리스트를 각각 재귀호출을 통해 분할정복
	quick_sort(start, right - 1);
	quick_sort(right + 1, end);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	quick_sort(0, 8);
	for (int i = 0; i < 9; i++) {
		cout << arr[i] << " ";
	}
	
}