[Sorting] Chapter 01. 기본 정렬 (버블, 선택, 삽입)

GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commit/0a525688c3203b9ea67f96a493d765e55d7d8694

기본 정렬 (버블, 선택, 삽입) · developeSHG/Data_Structure-Algorithm@0a52568

 

 

---

 

 

C++이 아니라 C#이라고 잠시 생각보자.

참고로 이전에, A* 알고리즘에서 OpenList를 만들었는데 그것을 PQ(우선순위 큐)로 만들어 관리하고 있었다. 근데 고민해보면 왜 우선순위 큐를 사용하느냐? 란 생각이 들 수 있다.

C#에선 List가 C++에서 vector에 해당하는 자료구조인데, C# List안에는 내부적으로 Sort라는 기능이 있으니 데이터를 넣어 자동으로 정렬해주면 원하는 순서대로 조합할 수 있는 것 아닌지 란 생각이 들 수도 있다.

 

만약 자료구조 알고리즘을 학습하지 않는다고 하면 위처럼 Sort라는 기능 자체가 굉장히 빠르게 동작하는 걸로 오할 수 있다. 결론적으로 얘기하면 성능차이가 어마어마하게 많이 나기 때문이다. 

 

PQ(우선순위 큐)는 log N의 시간복잡도를 가진다.

또 최근에 학습한 Red-Black Tree도 log N의 시간복잡도를 가진다.

이진 트리 구조로 되어있는 자료구조들은 log N의 시간복잡도를 가진다고 생각하면 된다. 데이터가 아무리 많이 늘어나도 트리의 높이가 구조에 맞게 천천히 증가하기 때문에, 정렬처럼 하나씩 스캔하는 것에 비하면 천차만별로 성능이 확실히 좋다.

 

정렬도 종류가 다양하고, 그에 따라 성능 차이도 차이가 있다.

이번에 알아볼 정렬은 매우 느리고 무식하게 정렬하는 방식인 버블 정렬, 선택 정렬, 삽입 정렬이다.

이 정렬들은 비효율적이지만, 구현이 매우 간단하고 직관적이다.  

 

#include <iostream>
#include <vector>
#include <list>
#include <stack>
#include <queue>
using namespace std;
#include <thread>
// 오늘의 주제 : 정렬

// C# 자료구조/알고리즘
// -> A* OpenList (PQ)
// -> C# List = C++ vector

// PQ O(logN)
// Red-Black Tree O(logN)
// Sorting ?



// 1) 버블 정렬 (Bubble Sort)
// 순서대로 앞 뒤로 비교해서 조건에 부합하면 자리를 바꾸고(swap), 
// 가장 큰 값을 맨 뒤부터 채워넣는 방식
void BubbleSort(vector<int>& v)
{
	const int n = (int)v.size();

	// (N-1) + (N-2) + ... + 2 + 1
	// 등차수열의 합 = N * (N-1) / 2
	// O(N^2)
	for (int i = 0; i < n - 1; i++)
	{
		for (int j = 0; j < (n - 1 - i); j++)
		{
			if (v[j] > v[j + 1])
			{
				int temp = v[j];
				v[j] = v[j + 1];
				v[j + 1] = temp;
			}
		}
	}
}

// [3][5][9][J][K]

// 2) 선택 정렬 (Selection Sort)
// 버블 정렬과 둘둘씩 비교해서 승자를 뒤에서 채워넣은 것처럼 방식이 유사하지만,
// 선택 정렬은 눈대중으로 전체를 스캔해서 원하는 값을 선택해 앞에서부터 채운다.
// 버블 정렬은 라운드마다 둘둘씩 대결해서 승자를 가렸다면,
// 선택 정렬은 라운드마다 전체에서 승자를 골라낸다. 
void SelectionSort(vector<int>& v)
{
	const int n = (int)v.size();

	// O(N^2)
	for (int i = 0; i < n - 1; i++)
	{
		int bestIdx = i;

		for (int j = i + 1; j < n; j++)
		{
			if (v[j] < v[bestIdx])
				bestIdx = j;
		}

		// 교환
		int temp = v[i];
		v[i] = v[bestIdx];
		v[bestIdx] = temp;
	}
}

// 3) 삽입 정렬 (Insertion Sort)
// 삽입 정렬도 선택 정렬과 매 턴마다 비교를 하는 것이 유사하긴 하지만,
// 달라지는 부분이 선택 정렬은 매 턴마다 제일 좋은 후보를 찾아 원하는 위치에 배치했다하면
// 삽입 정렬은 실시간으로 정렬된 데이터를 만들어놨다라는 느낌으로 동작한다.
// 마치 카드를 하나씩 뽑아 완성된 손에 원하는 위치로 카드를 꽂아주는 형태로 동작.
// 
// i = 2
// insertData = [5]
// [4][5][9][K][3]
// 
void InsertionSort(vector<int>& v)
{
	const int n = (int)v.size();

	// O(N^2)
	for (int i = 1; i < n; i++)
	{
		int insertData = v[i];

		int j;
		for (j = i - 1; j >= 0; j--)
		{
			if (v[j] > insertData)
				v[j + 1] = v[j];
			else
				break;
		}

		v[j + 1] = insertData;
	}
}

int main()
{
	vector<int> v{ 1, 5, 3, 4, 2 };

	std::sort(v.begin(), v.end());

	//BubbleSort(v);
	//SelectionSort(v);
	InsertionSort(v);
}