[알고리즘] 퀵정렬 / C++ (병합정렬 포함)

이번에는 퀵정렬입니다!

퀵정렬은 주어진 배열을에 대해 기준(피벗)값을 정하여 큰 숫자와 작은 숫자에 대한 정렬과 함께 정렬된 부분을 제외하고 나머지 부분을 분할하여 정렬하는것을 원칙으로 합니다(오름차순 기준)!

예를들어 4 5 2 3 1이 있다면 4가 피벗값이 되고 왼쪽을 기준으로 4보다 큰 값인 5를 찾고 오른쪽을 기준으로 4보다 작은값인 1을 찾아 두 숫자의 위치를 바꾸어 줍니다!('4 1 2 3 5' 가 되겠네요) 이후로 똑같이 수행해줍니다!

기준값 4를 기준으로 왼쪽부터 큰값을 찾습니다. 5뿐에 없네요? 그리고 왼편을 기준으로 찾으면 3이 됩니다! 큰 수의 인덱스는 '4'인데 작은수의 인덱스는 '3'이 됐네요? 이렇게 되면 엇갈림이 발생한다고 합니다.

큰 수의 인덱스는 항상 작은수의 인덱스보다 작을때만 수행되어야 하는 특성을 갖는 퀵정렬은 이때 작은값인 3과 기준값인 4의 위치를 바꾸어 주고 4의 위치는 고정이 됩니다! 좀 어렵게 느껴질 수 있지만, 엇갈림이 발생하면 작은값과 기준값의 위치를 바꾸어 준다 생각하면 편합니다..!

뭔가 조금 복잡한데 퀵정렬은 말그대로 빠른 정렬이라고 할 수 있습니다. 정렬에 필요로 하는 평균적인 속도는 O(N x logN)이기 때문이죠!(정말 운이 안좋으면 O(N^2)이 되지만요... 이런경우는 드뭅니다!)

다음은 예제를 통해서 조금 더 알아보도록 하죠~

배열 3 7 8 1 5 9 6 10 2 4에 대해 퀵정렬을 해보는 예제입니다!

#include <iostream>
int number = 10;
int data[10] = { 3,7,8,1,5,9,6,10,2,4 };

void quick_sort(int *data, int first_num, int last_num)
{
	if (first_num >= last_num)
	{
		return;
	}
	int key = first_num;
	int i = first_num + 1;
	int j = last_num;
	int temp;

	while (i <= j)
	{
		while (data[i] <= data[key])
		{
			i++;
		}
		while (data[j] >= data[key] && j > first_num)
		{
			j--;
		}
		if (i > j)
		{
			temp = data[j];
			data[j] = data[key];
			data[key] = temp;
		}
		else
		{
			temp = data[j];
			data[j] = data[i];
			data[i] = temp;
		}
	}
	quick_sort(data, first_num, j - 1);
	quick_sort(data, j + 1, last_num);
}

int main()
{
	quick_sort(data, 0, number - 1);
	for (int i = 0; i < number; i++)
	{
		std::cout << data[i] << " ";
	}
	return 0;
}

💡 이제 코드를 하나하나 뜯어 봅시다!

먼저 어떠한 동작방식으로 작동하는지에 대해 생각해 보면 다음과 같이 나타낼 수 있습니다.

---

동작방식

특정한 값(피벗 값)을 기준으로 큰 숫자와 작은 숫자를 나눔

왼쪽기준으로 기준값인 3보다 큰값을 찾고 오른쪽을 기준으로 작은값을 찾은 후 둘의 위치를 바꿈

1. 3 7 8 1 5 9 6 10 2 4 -> 기준값: 3 / 큰값: 7 / 작은값: 2

2. 3 2 8 1 5 9 6 10 7 4 -> 큰값: 8 / 작은값: 1

3. 3 2 1 8 5 9 6 10 7 4 -> 큰값: 8 / 작은값: 1 -> 엇갈림 발생 -> 작은값(1)과 기준값(3)의 위치를 바꿈

4. 1 2 3 8 5 9 6 10 7 4 -> 기준값(3) 정렬 완료 -> 3을 기준으로 왼편과 오른편의 맨앞의 숫자인 1과 8을 기준값으로 놓고 수행

왼편 기준값: 1 / 큰값: 2 / 작은값: 없음(자기자신 고름) --> 엇갈림 발생(기준값인 1과 작은값이 없어 고른 기준값 1의 위치를 바꿈) --> '1' 정렬완료!
1 2 3

오른편 기준값: 8 / 큰값: 9 / 작은값: 4
8 5 4 6 7 10 9

둘 합침 --> 1 2 3 8 5 4 6 10 7 9

5. 1 2 3 8 5 4 6 10 7 9 -> 기준값: 8 / 큰값: 10 / 작은값: 7

6. 1 2 3 8 5 4 6 7 10 9 -> 기준값: 8 / 큰값: 10 / 작은값: 7 --> 엇갈림 발생 -> 기준값과 작은값의 위치 바꿈

7. 1 2 3 7 5 4 6 8 10 9 -> 기준값(8) 정렬 완료 -> 8을 기준으로 왼편과 오른편의 맨앞숫자(정렬된 숫자 제외)를 기준값으로 놓고 재귀적 수행

왼편 기준값: 7 / 큰값: 없음(자기자신 고름) / 작은값: 6 --> 엇갈림 발생(기준값7과 작은값6의 위치 바꿈)
1 2 3 6 5 4 7 --> '7' 정렬완료!

오른편 기준값: 10 / 큰값: 없음(자기자신 고름) / 작은값: 9 --> 엇갈림 발생(기준값10과 작은값9의 위치 바꿈)
8 9 10 --> '10' 정렬완료!

... 계속해서 재귀수행!

---

quick sort는 기본적으로 재귀함수를 이용합니다. 재귀함수는 함수를 반복적으로 호출해 특정 조건이 완료되기 전까지 함수를 무한호출하는 함수를 말합니다!

이제 정말 코드를 한번 봐봅시다!

전역변수로 number를 10으로 선언해놓고, data배열에는 숫자들을 입력해 놓았습니다! 별 의문이 들지 않을테니 넘어가겠습니다~

quick_sort 함수를 먼저 한번 보겠습니다.

void quick_sort(int *data, int first_num, int last_num)

매개변수로 data를 포인터변수로 선언하였습니다. 보통 배열을 매개변수로 선언할때 포인터를 사용합니다. 이러한 이유로는 배열을 효율적으로 정렬하려는 목적과, 배열의 일부분을 정렬하는 데 포인터를 사용하기 위함입니다.(보통 배열을 매개변수로 받을때는 포인터 씁니다.)

안에 조건문들을 또 봐보죠! 먼저 if문 입니다

	if (first_num >= last_num)
	{
		return;
	}

(first_num >= last_num)

first_num은 왼쪽부터 찾는 큰수를 last_num은 오른쪽부터 찾는 작은수를 의미합니다! 생각해보면 왼쪽부터 찾는 큰수가 오른쪽부터 찾는 작은수보다 크거나 같은경우는 배열의 크기가 [1]일때 밖에 존재하지 않습니다. 그럴때는 바로 탈출하면 되겠죠?

변수

다음으로는 또 변수를 선언하였습니다.

	int key = first_num; // 배열 기준값
	int i = first_num + 1; // 큰값찾기(왼 -> 오)
	int j = last_num; // 작은값 찾기(오 -> 왼)
	int temp; // 교환

조건문을 원활히 돌 수 있게 할 수 있도록 해줍니다! 만약 first_num과 last_num에 대해서 새로 변수를 선언하지 않게된다면 조건을 제대로 돌 수 없게 됩니다. 이제 그 조건을 한번 봐봅시다!

while 문

	while (i <= j)
	{
		while (data[i] <= data[key])
		{
			i++;
		}
		while (data[j] >= data[key] && j > first_num)
		{
			j--;
		}
		if (i > j)
		{
			temp = data[j];
			data[j] = data[key];
			data[key] = temp;
		}
		else
		{
			temp = data[j];
			data[j] = data[i];
			data[i] = temp;
		}
	}

(i <= j)

i가 j보다 커질때까지 지속적인 정렬작업이 필요하며, 만약 등호가 없는 i < j의 조건문으로 사용하면 불필요한 교환작업을 통해 무한루프가 발생할 수 있기때문에 i <= j의 조건을 사용해 정확한 분할과 정렬을 가능하게 해줍니다! 다시말해 엇갈림이 발생할때 까지 while 루프를 실행하게됩니다!

(data[i] <= data[key])

배열을 왼쪽에서 오른쪽으로 이동(i++)하면서 기준값(data[key])보다 큰 값을 찾아 줍니다!

(data[j] >= data[key] && j > first_num)

배열을 오른쪽에서 왼쪽으로 이동하면서 기준값(data[key])보다 작은 값을 찾아 줍니다! 또한, and조건을 통해 j가 배열의 시작위치인 first_num보다 큰지를 확인하며 그 값이 존재하지 않을때만 검색을 진행하도록 하기위한 조건입니다!

if (i > j), else

if문의 조건은 i와 j가 엇갈린 경우, 정렬이 완료된 true조건이 되며 이때, data[key]와 j의 위치를 교환하여 정렬을 완료합니다!
else는 반대의 상황으로 i와 j가 엇갈리지 않았을때 data[i]와 data[j]를 교한해 정렬을 완료합니다!

재귀호출

	quick_sort(data, first_num, j - 1);
	quick_sort(data, j + 1, last_num);

이는 재귀를 위해 함수를 재호출하는 과정입니다!

quick_sort(data, first_num, j-1)

이는 재귀를 통해 배열의 왼쪽 부분의 정렬을 위해 quick_sort함수를 재귀적으로 호줄하여 first_num부터 j-1까지 정렬하는 작업을 수행합니다!

quick_sort(data, j+1, last_num)

이는 반대로 오른쪽 부분의 정렬을 위한 코드입니다!

마지막을 메인함수입니다!(거의 끝났어요~)

	quick_sort(data, 0, number - 1);
	for (int i = 0; i < number; i++)
	{
		std::cout << data[i] << " ";
	}
	return 0;

여기서 볼 부분은 number - 1부분 하나인것 같습니다!
number대신 number-1을 넣는 이유는 배열의 시작은 1이 아닌 0이기 때문입니다!(실제로 숫자9를 넣어도 문제가 없습니다.)

---

병합정렬(간략합니다!)

병합정렬은 O(N log N)의 시간복잡도를 보장하는 정렬 알고리즘입니다! N log N의 시간복잡도를 갖는다는 점에서 안정적인 알고리즘이라고 할 수 있습니다.

병합정렬은 퀵정렬 알고리즘과 마찬가지로 분할정복 알고리즘을 사용합니다!

병합정렬은 아래의 단계를 따라 동작하게됩니다!
1. 배열을 반으로 나눔
2. 각 하위 배열에 대해 병합정렬을 재귀적으로 호출
3. 정렬된 하위 배열을 병합하며, 생성하는데 더 큰 정렬된 배열을 생성합니다!

평균적으로 병합정렬은 퀵정렬보다 빠르지 않지만 항상 O(N * log N)의 시간복잡도를 갖기에 안정적인 시간복잡도를 갖는 알고리즘을 위해서는 병합정렬을 사용하는것이 좋습니다!