Mighty

Mighty의 나를 위한 공부블로그

정렬 알고리즘

Updated:

정렬 알고리즘?

CS공부를 하다가 정렬 알고리즘을 만났는데, 알고리즘 문제를 풀 때는 항상
C++의 STL로 해결했다 보니, 어떤 종류의 정렬 알고리즘이 있는지 정확히 알지 못했다.
면접 등을 대비하기 위해서라도 한번쯤 정리하고 구현해볼 필요가 있다고 생각했다.

1. 버블 정렬(Bubble Sort)

개념

서로 인접한 두 데이터를 비교해가면서 정렬을 진행한다.
가장 큰 값부터 차곡차곡 쌓을 수도 있고, 가장 작은 값부터 차곡차곡 쌓을 수도 있다.
n^2의 시간복잡도를 가진다.

코드

#include <iostream>

using namespace std;

int main()
{
	int arr[7] = { 5, 3, 1, 6, 2, 7, 4 };
	int arr_num = 7;
	int temp;
	int cnt = 0;

	 //cout << "초기 배열 : [ ";
	 //for (int i = 0; i < arr_num; i++)
	 //	cout << arr[i] << " ";
	 //cout << "]" << '\n';

	for (int i = arr_num - 1; i >= 0; i--)
		for (int j = 0; j < i; j++)
			if (arr[j] > arr[j + 1])
			{
				temp = arr[j + 1];
				arr[j + 1] = arr[j];
				arr[j] = temp;
				 //cout << ++cnt << "회 연산 : [ ";
				 //for (int k = 0; k < arr_num; k++)
				 //	cout << arr[k] << " ";
				 //cout << "]" << '\n';
			}

	return 0;
}

과정 및 결과

초기 배열 : [ 5 3 1 6 2 7 4 ]
1회 연산 : [ 3 5 1 6 2 7 4 ]
2회 연산 : [ 3 1 5 6 2 7 4 ]
3회 연산 : [ 3 1 5 2 6 7 4 ]
4회 연산 : [ 3 1 5 2 6 4 7 ]
5회 연산 : [ 1 3 5 2 6 4 7 ]
6회 연산 : [ 1 3 2 5 6 4 7 ]
7회 연산 : [ 1 3 2 5 4 6 7 ]
8회 연산 : [ 1 2 3 5 4 6 7 ]
9회 연산 : [ 1 2 3 4 5 6 7 ]

2. 선택 정렬(Selection Sort)

개념

Bubble Sort와 동일하다.
하지만, 인접한 값을 비교하고 그때그때 바꾸는 것이 아니라 필요한 인덱스만 저장했다가
정렬되지 않은 모든 값을 조사한 뒤에 한번만 값을 변경한다.
n^2의 시간복잡도를 가진다.

코드

#include <iostream>

using namespace std;

int main()
{
	int arr[7] = { 5, 3, 1, 6, 2, 7, 4 };
	int arr_num = 7;
	int temp;
	int cnt = 0;

	// cout << "초기 배열 : [ ";
	// for (int i = 0; i < arr_num; i++)
	// 	cout << arr[i] << " ";
	// cout << "]" << '\n';

	for (int i = 0; i < arr_num - 1; i++)
	{
		int smallidx = i;

		for (int j = i + 1; j < arr_num; j++)
			if (arr[smallidx] > arr[j])
				smallidx = j;

		temp = arr[smallidx];
		arr[smallidx] = arr[i];
		arr[i] = temp;

		// cout << ++cnt << "회 연산 : [ ";
		// for (int k = 0; k < arr_num; k++)
		// 	cout << arr[k] << " ";
		// cout << "]" << '\n';
	}
	return 0;
}

과정 및 결과

초기 배열 : [ 5 3 1 6 2 7 4 ]
1회 연산 : [ 1 3 5 6 2 7 4 ]
2회 연산 : [ 1 2 5 6 3 7 4 ]
3회 연산 : [ 1 2 3 6 5 7 4 ]
4회 연산 : [ 1 2 3 4 5 7 6 ]
5회 연산 : [ 1 2 3 4 5 7 6 ]
6회 연산 : [ 1 2 3 4 5 6 7 ]

3. 삽입 정렬(Insertion Sort)

개념

n개의 수를 정렬한다고 할 때, 0번째 부터 범위를 넓혀가며 정렬해 나간다.
i번째 수를 정렬할 차례라면, i-1번째 수까지 정렬되어있을 것이다. 이 때, i번째 수를 0번째 수부터 i-1번째 수까지 비교해가며 값의 크기가 올바르도록 계속해서 바꾼다.
n^2의 시간복잡도를 가진다.

코드

#include <iostream>

using namespace std;

int main()
{
	int arr[7] = { 5, 3, 1, 6, 2, 7, 4 };
	int arr_num = 7;
	int temp;
	int cnt = 0;

	// cout << "초기 배열 : [ ";
	// for (int i = 0; i < arr_num; i++)
	// 	cout << arr[i] << " ";
	// cout << "]" << '\n';

	for (int i = 1; i < arr_num; i++)
	{
		for (int j = 0; j < i ; j++)
			if (arr[i] < arr[j])
			{
				temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
				// cout << ++cnt << "회 연산 : [ ";
				// for (int k = 0; k < arr_num; k++)
				// 	cout << arr[k] << " ";
				// cout << "]" << '\n';
			}
	}
	return 0;
}

과정 및 결과

초기 배열 : [ 5 3 1 6 2 7 4 ]
1회 연산 : [ 3 5 1 6 2 7 4 ]
2회 연산 : [ 1 5 3 6 2 7 4 ]
3회 연산 : [ 1 3 5 6 2 7 4 ]
4회 연산 : [ 1 2 5 6 3 7 4 ]
5회 연산 : [ 1 2 3 6 5 7 4 ]
6회 연산 : [ 1 2 3 5 6 7 4 ]
7회 연산 : [ 1 2 3 4 6 7 5 ]
8회 연산 : [ 1 2 3 4 5 7 6 ]
9회 연산 : [ 1 2 3 4 5 6 7 ]

4. 합병 정렬(Merge Sort)

개념

Divide and Conquer기법을 활용한다.
배열을 반씩 쪼개가며 최종적으로 1개의 원소로 이루어진 n개의 가상 배열을 만든 뒤,
이를 다시 병합해나가는 과정에서 정렬을 실시한다.

두 배열을 병합 할 때, 두 배열의 가장 앞의 수 중 더 작은 값을 상위 배열의 앞부분부터 채워넣는다.
이 과정을 다시 하나의 배열로 병합될 때 까지 반복한다.
nlogn의 시간복잡도를 가진다.

코드

#include <iostream>

using namespace std;

int temp_arr[7];
int arr_num = 7;
int cnt = 0;

void merge(int arr[7], int left, int right)
{
	int mid = (left + right) / 2;

	int idx_a = left;
	int idx_b = mid + 1;
	int save_idx = left;
	while (idx_a <= mid && idx_b <= right)
	{
		if (arr[idx_a] < arr[idx_b])
			temp_arr[save_idx++] = arr[idx_a++];
		else
			temp_arr[save_idx++] = arr[idx_b++];
	}

	while (idx_a <= mid)
		temp_arr[save_idx++] = arr[idx_a++];

	while (idx_b <= right)
		temp_arr[save_idx++] = arr[idx_b++];

	for (int i = left; i <= right; i++)
		arr[i] = temp_arr[i];

	// cout << ++cnt << "회 연산 : [ ";
	// for (int k = 0; k < arr_num; k++)
	// 	cout << arr[k] << " ";
	// cout << "]" << '\n';
}

void merge_sort(int arr[7], int left, int right)
{
	int mid = (left + right) / 2;

	if (left < right)
	{
		merge_sort(arr, left, mid);
		merge_sort(arr, mid + 1, right);
		merge(arr, left, right);
	}
}

int main()
{
	int arr[7] = { 5, 3, 1, 6, 2, 7, 4 };

	// cout << "초기 배열 : [ ";
	// for (int i = 0; i < arr_num; i++)
	// 	cout << arr[i] << " ";
	// cout << "]" << '\n';

	merge_sort(arr, 0, arr_num - 1);
	return 0;
}

과정 및 결과

초기 배열 : [ 5 3 1 6 2 7 4 ]
1회 연산 : [ 3 5 1 6 2 7 4 ]
2회 연산 : [ 3 5 1 6 2 7 4 ]
3회 연산 : [ 1 3 5 6 2 7 4 ]
4회 연산 : [ 1 3 5 6 2 7 4 ]
5회 연산 : [ 1 3 5 6 2 4 7 ]
6회 연산 : [ 1 2 3 4 5 6 7 ]

5. 힙 정렬(Heap Sort)

개념

heap 자료구조를 사용한 정렬이다. heap은 이진트리로 구성되어 있는데, 느슨하게 정렬하여 최대힙의 경우 모든 부모는 자신의 자식보다 큰 값을 가지게 되고,
최소힙의 경우 모든 부모는 자신의 자식보다 작은 값을 가지게 된다.

이러한 힙 자료구조를 이용하여 정렬하는 방법은 다음과 같다.

  1. 1번 노드부터 n번 노드로 최대힙을 구성한다.
  2. 1번 노드가 가장 큰 값이므로, 이를 n번 노드와 바꾼다.
  3. 위 1~2 과정을 n이 1씩 작아지도록 하여 n-1회 반복한다.

nlogn의 시간복잡도를 가진다.

코드

#include <iostream>

using namespace std;

int arr_num = 7;
int cnt = 0;

int main()
{
	int arr[8] = {0, 5, 3, 1, 6, 2, 7, 4 }; // 0은 빈 값
	int temp;

	// cout << "초기 배열 : [ ";
	// for (int i = 1; i <= arr_num; i++)
	// 	cout << arr[i] << " ";
	// cout << "]" << '\n';

	for (int i = 0; i < arr_num - 1; i++)
	{
		for (int j = 1; j <= arr_num - i; j++)
		{
			int node = j;

			while (node / 2 >= 1)
			{
				if (arr[node] > arr[node / 2])
				{
					temp = arr[node];
					arr[node] = arr[node / 2];
					arr[node / 2] = temp;
					node /= 2;
				}
				else
					break;
			}
		}
		temp = arr[1];
		arr[1] = arr[arr_num - i];
		arr[arr_num - i] = temp;

		// cout << ++cnt << "회 연산 : [ ";
		// for (int k = 1; k <= arr_num; k++)
		// 	cout << arr[k] << " ";
		// cout << "]" << '\n';
	}

	return 0;
}

과정 및 결과

초기 배열 : [ 5 3 1 6 2 7 4 ]
1회 연산 : [ 4 5 6 3 2 1 7 ]
2회 연산 : [ 1 4 5 3 2 6 7 ]
3회 연산 : [ 2 3 4 1 5 6 7 ]
4회 연산 : [ 1 2 3 4 5 6 7 ]
5회 연산 : [ 2 1 3 4 5 6 7 ]
6회 연산 : [ 1 2 3 4 5 6 7 ]

6. 퀵 정렬(Quick Sort)

개념

다른 비교정렬에 비해 빠르다 하여 퀵 정렬이라고 부른다.
Divide and Conquer기법에 pivot이라는 개념을 합쳐 정렬한다. 부분 배열 내에서 임의의 수를 pivot으로 설정하고, 좌측에는 그보다 작은 수, 우측에는 그보다 큰 수를 두고
두 부분 배열에 대하여 다시금 pivot을 설정하고 과정을 반복하며 정렬한다.
nlogn의 시간복잡도를 가진다.

코드

#include <iostream>

using namespace std;

int arr_num = 7;
int cnt = 0;

void quick_sort(int arr[7], int left, int right)
{
	if (left >= right)
		return;

	int pivot = left;
	int new_left = left + 1;
	int new_right = right;
	int temp;

	while (new_left <= new_right)
	{
		if (arr[pivot] > arr[new_left])
			new_left++;
		else if (arr[pivot] < arr[new_right])
			new_right--;
		else
		{
			temp = arr[new_left];
			arr[new_left] = arr[new_right];
			arr[new_right] = temp;
			new_left++;
			new_right--;
		}
	}
	
	temp = arr[pivot];
	arr[pivot] = arr[new_right];
	arr[new_right] = temp;

	// cout << ++cnt << "회 연산 : [ ";
	// for (int k = 0; k < arr_num; k++)
	// 	cout << arr[k] << " ";
	// cout << "] pivot : " << arr[new_right] << '\n';

	if (left < right)
	{
		quick_sort(arr, left, new_right - 1);
		quick_sort(arr, new_left, right);
	}
}

int main()
{
	int arr[7] = {5, 3, 1, 6, 2, 7, 4 };
	int temp;

	// cout << "초기 배열 : [ ";
	// for (int i = 0; i < arr_num; i++)
	// 	cout << arr[i] << " ";
	// cout << "]" << '\n';

	quick_sort(arr, 0, arr_num - 1);

	
	return 0;
}

과정 및 결과

초기 배열 : [ 5 3 1 6 2 7 4 ]
1회 연산 : [ 2 3 1 4 5 7 6 ] pivot : 5
2회 연산 : [ 1 2 3 4 5 7 6 ] pivot : 2
3회 연산 : [ 1 2 3 4 5 7 6 ] pivot : 3
4회 연산 : [ 1 2 3 4 5 6 7 ] pivot : 7

마치며

평소 대강 이런거겠거니 생각했던 정렬 알고리즘들을 직접 구현해보는 과정은 굉장히 재밌었다.
뿐만 아니라 불확실했던 내용들이 머릿속에 착착 정리된 것 같다.

종종 확실하지 않고 어렴풋이 알고있는 개념들을 정리하는 습관을 갖는 것이 좋을 것 같다.

Leave a comment

You may also enjoy