251124 언리얼엔진 본캠프 73일차 3정렬과 퀵 정렬

3 정렬과 퀵 정렬

프로그래머스 등의 코딩 테스트 문제들을  풀다 보면 심심찮게 숫자나 문자들을 정렬해야 하는 경우가 발생한다. 기본적인 sort 함수를 사용해서 정렬하는 것도 좋지만 시간복잡도나 여러 상황에 따라서 직접 정렬함수를 구현하여 사용해야 하는 경우도 있다. 오늘은 C++에서 구현할 수 있는 정렬방식에 대해서 알아보고자 한다.

 

 

버블 정렬(Bubble Sort)

바로 옆에 있는 두 수를 비교해서 순서가 틀렸으면 자리를 바꾸는 방식의 정렬이다. 이 과정을 끝까지 반복하면 가장 큰 수가 맨 뒤로 가게 된다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void BubleSort(vector<int> arr)
{
	int n = arr.size();

	for (int i = 0; i < n - 1; ++i)
	{
		for (int j = 0; j < n - i - 1; ++j)
		{
			if (arr[j] > arr[j + 1])
			{
				swap(arr[j], arr[j + 1]);
			}
		}
	}
}

 

위는 버블 정렬의 예시 코드이다 예를들어 {4, 6, 1, 3, 9}를 받았다 생각해 보자. n은 그럼 5가 되겠고 i는 0부터 4까지 j는 0부터 4-i까지 돌게 될 것이다. arr의 0과 1 인덱스의 값은 4와 6이고 4는 6보다 작기 때문에 스왑 하지 않고 넘어가게 된다. j의 값은 증가하고 1과 2 인덱스의 값은 6과 1, 6은 1보다 크기 때문에 if문의 조건에 충족되어 스왑 되어 {4, 1, 6, 3, 9}가 된다. 이후 j의 값은 증가하고 2와 3 인덱스를 비교 다시 스왑이 되어 {4, 1, 3, 6, 9}, 이후 j가 증가하여 {4, 1, 3, 6, 9}가 된다. j가 한 바퀴 돌았으니 i가 1 증가되게 되고 다시 j는 0부터 3까지 돌고 이 과정이 반복되어 결국 {1, 3, 4, 6, 9}의 결과를 얻게 된다.

이처럼 버블 정렬은 단순한 코드로 구현할 수 있는 정렬이지만 swap이 자주 일어나게 되어 가장 느리기에 실무에서 사용하지 않고 알고리즘 교육 등에서만 사용한다고 한다.

 

선택 정렬(Selection Sort)

전체를 훑어서 가장 작은 수를 찾아 맨 앞의 수와 자리를 바꾸는 방식으로 구현한다. 그 다음은 두 번째로 작은 수를 찾아 두 번째 자리와 바꾸게 된다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void SelectionSort(vector<int> arr)
{
	int n = arr.size();

	for (int i = 0; i < n - 1; ++i)
	{
		int min = i;
		for (int j = i + 1; j < n; ++j)
		{
			if (arr[j] < arr[min])
			{
				min = j;
			}
		}

		swap(arr[i], arr[min]);
	}
}

 

n은 arr의 크기로 정해주고 i를 0부터 n-1까지 for문을 돌려준다. 최소값은 i라고 가정한 상태에서 시작한다. j는 i+1부터 n까지 for문을 내부에 돌려주면서 비교를 시작한다 i+1에 해당하는 1번 인덱스가 최솟값으로 가정한 i 즉 0번 인덱스보다 작으면 최소인 min을 j인 1번 인덱스로 바꾸어준다. 이 과정을 반복하여 최솟값을 찾아주고 i번째와 최솟값을 스왑해준다음 i를 증가시켜 위의 과정을 반복한다.

 

이런 식으로 정렬을 해주면 버블 정렬보다 값을 교환하는 횟수가 적기 때문에 시간적으로 유리하다 하지만 데이터가 이미 정렬되어 있더라도 끝까지 검사를 시도하기에 역시 비효율적인 방법이다.

 

삽입 정렬(Insertion Sort)

삽입 정렬은 숫자를 하나씩 뽑아서 앞쪽의 이미 정렬된 부분 사이의 알맞은 위치에 끼워 넣는 과정을 갖는다. 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void InsertionSort(vector<int> arr)
{
	int n = arr.size();

	for (int i = 1; i < n; ++i)
	{
		int key = arr[i];
		int j = i - 1;

		while (j >= 0 && arr[j] > key)
		{
			arr[j + 1] = arr[j];
			j--;
		}

		arr[j + 1] = key;
	}
}

 

여기서는 key를 끼워 넣을 숫자로 정해둔다. 아까처럼 {4, 6, 1, 3, 9}를 받아 넣었다고 생각해 보면 key는 arr [1]인 6이 되고 j는 0이 된 상황에서 while이 돌아가게 된다. arr [0]인 4는 6인 key보다 작기 때문에 false로 반복하지 않는다. 그러면 arr [1]에 6이 들어가게 되어 상황은 그대로 i가 1 증가하게 된다. 이번엔 key값은 arr [2]인 1이 되고 j는 1이 되어 while문의 조건을 보게 되면 arr [1]인 6은 key의 값 1보다 크기 때문에 true로 인해 while이 작동하여 arr [2]에 arr [1]이 들어가게 되고(현재 : {4, 6, 6, 3, 9} ) j는 1 하게 되어 0이 된다. j는 0이고 arr [0]은 4이고 이는 key 1보다 크기 때문에 while이 작동하여 arr [1]에 arr [0]이 들어가게 되고( 현재 : {4, 4, 6, 3, 9} ) j의 값이 감소하여 -1이 되고 while의 조건문이 false가 되게 되어 while을 벗어나게 된다. 이제 arr [0]에 key값이 들어가게 되어 최종적으로 {1, 4, 6, 3, 9} 형식이 된다. 다시 i의 값이 증가하게 되고 앞에서 보았던 과정을 반복하여 정렬이 이루어지게 된다.

 

이러한 방식을 사용하는 삽입 정렬은 이미 어느정도 정렬된 데이터에 대해서는 매우 빠른 속도를 갖게 되지만 역순으로 정렬된 데이터에서는 매우 느리다는 특징을 갖게 된다.

 

퀵 정렬(Quick Sort)

퀵 정렬은 기준점이 될 피벗을 선택하여 피벗보다 작은 값은 왼쪽으로 큰 값은 오른쪽으로 옮기고 그 과정을 반복하여 정렬하는 방식을 사용한다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int Partition(vector<int>& arr, int low, int high)
{
	int pivot = arr[high];
	int i = (low - 1);

	for (int j = low; j < high; ++j)
	{
		if (arr[j] < pivot)
		{
			i++;
			swap(arr[i], arr[j]);
		}
	}

	swap(arr[i + 1], arr[high]);
	return(i + 1);
}

void QuickSort(vector<int>& arr, int low, int high)
{
	if (low < high)
	{
		int index = Partition(arr, low, high);

		QuickSort(arr, low, index - 1);

		QuickSort(arr, index + 1, high);
	}
}

 

퀵 정렬의 경우에는 Partition함수를 추가로 정의해 주어 구현할 수 있다. 예컨대 {5, 3, 7, 6, 2, 1, 4}를 받았다고 생각해 보자 파티션에서는 맨 뒤의 4를 피벗으로 잡고 정리하기 시작한다. 순차적으로 배열을 조회하며 피벗인 4보다 크면 그대로 두고 4보다 작으면 i를 하나 증가시킨 뒤 arr [i]와 arr [j]를 스왑 한다. 이때 i는 항상 피벗보다 작은 값을 모아둔 영역의 끝을 가리킨다. 이런 식으로 j를 모두 순회하면 피벗을 arr [i+1]와 교환해 준다. 이러면 4는 가운데에 있게 되고 왼쪽에는 작은 값이 오른쪽에는 큰 값이 위치하게 된다. 이제 작은 값의 영역과 큰 값의 영역을 다시 정렬해 주면 된다. 이때 QuickSort를 재귀하여 각 영역별로 정렬해 준다. 일반적으로 해당 방식을 사용하는 퀵 정렬이 다른 3가지 정렬보다 시간적인 비용이 저렴하기에 대부분의 일반적인 상황에서는 퀵정렬을 사용해 준다.