[C++] 13 - 기초 문법 공부 일지(Sort)

int main()
{
	vector<int> v;
	srand(static_cast<unsigned int>(time(NULL)));
	for (int i = 0; i < 10; i++)
		v.push_back(rand() % 100);

	BubbleSort(v);
	SelectionSort(v);
    
	InsertSort(v);
	ShellSort(v);
    
	HeapSort(v);
    
	MergeSort(v, 0, v.size() - 1);
	QuickSort(v, 0, v.size() - 1);
	
	std::sort(v.begin(), v.end(), [=](int a, int b) -> bool {return a > b; });
}

 

1. Bubble Sort

     - 서로 인접한 두 데이터를 비교하여 정렬하는 알고리즘

     - 코드 구현이 단순하고 쉽지만 느림

     - 시간 복잡도 : O(n²)

void BubbleSort(vector<int>& v)
{
	const int size = v.size();
	
	for (int i = 0; i < size - 1; i++)
		for (int j = 0; j < size - 1 - i; j++)
        	// j와 j + 1의 데이터 비교해서 큰 값이 나오면 교환
			if (v[j] > v[j + 1])
				std::swap(v[j], v[j + 1]);
}

 

2. Selection Sort

     - 가장 작은 값의 데이터들로 부터 차례대로 선택하여 위치를 교환하는 알고리즘

     - 코드 구현이 단순하고 버블 정렬 및 삽입 정렬보다 교환 횟수가 적음

     - 시간 복잡도 : O(n²)

void SelectionSort(vector<int>& v)
{
	const int size = v.size();
	for (int i = 0; i < size - 1; i++)
	{
		int idx = i;
		for (int j = i + 1; j < size; j++)
        	// idx와 j의 데이터를 비교하여 작은 값이 나오면 idx에 저장
			if (v[idx] > v[j]) idx = j;
		std::swap(v[i], v[idx]);
	}
}

 

3. Insert Sort

     - 배열의 앞에서부터 차례대로 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬하는 알고리즘

     - 코드 구현이 단순하고 대부분 이미 정렬이 되어있을 경우 매우 효율적임

     - 대부분 이미 정렬되어 있는 경우 시간 복잡도 : O(n)

     - 배열이 역순으로 정렬되어 있는 경우 시간 복잡도 : O(n²)

void InsertSort(vector<int>& v)
{
	const int size = v.size();
	for (int i = 1; i < size; i++)
		for (int j = i; j > 0; j--)
			if (v[j] < v[j - 1]) std::swap(v[j], v[j - 1]);
}

 

4. Shell Sort

     - 삽입정렬을 보완한 알고리즘

           - 데이터 삽입 위치가 현재 위치에 멀리 떨어진 곳이면 많은 이동을 해야함

           - 삽입 정렬과 다르게 셸 정렬은 전체의 리스트를 한 번에 정렬X

     - 삽입 정렬과 다르게 간격(gap)을 사용

           - 초기값은 간격의 절반, 간격은 홀수, 간격이 0이 되면 종료

     - 평균 시간 복잡도 : O(n^1.5)

void InsertGapSort(vector<int>& v, int gap)
{
	const int size = v.size();
	for (int i = gap; i < size; i = i + gap)
		for (int j = i; j > 0; j = j - gap)
			if (v[j] < v[j - gap]) std::swap(v[j], v[j - gap]);
}

void ShellSort(vector<int>& v)
{
	int gap = v.size();
	while (gap) // 0이 되면 종료
	{
		// gap - 홀수
		gap = (gap % 2 == 0) ? (gap / 2) + 1 : (gap / 2);

		// 부분 리스트의 개수는 gap과 같음
		for (int i = 0; i < gap; i++)
			InsertGapSort(v, gap); // 삽입 정렬 + gap
	}
}

 

5. Heap Sort

     - 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조

     - 시간 복잡도가 좋고, 전체 자료를 정렬하는 것이 아니라 가장 큰 값 몇개만 필요할 때 유용

           - 시간 복잡도 : O(nlog₂n)

void HeapSort(vector<int>& v)
{
	priority_queue<int, vector<int>, greater<int>> pq;
	for (auto number : v) pq.push(number);
	v.clear();

	while (pq.empty() == false) { v.push_back(pq.top()); pq.pop(); }
}

 

6. Merge Sort

     - 분할 정복 알고리즘

           - 문제를 작은 2개의 문제로 분리하고 각각을 해결, 결과를 모아서 원래의 문제를 해결하는 전략
           - 순환 호출 사용

     - 안정 정렬

           - 입력 데이터가 무엇이든 간에 정렬되는 시간은 동일

     - 시간 복잡도 : O(nlog₂n)

void Merge(vector<int>& v, int left, int mid, int right)
{
	int Left = left;
	int Right = mid + 1;
	vector<int> temp;

	while (Left <= mid && Right <= right)
	{
		// 크기 비교
		if (v[Left] <= v[Right]) temp.push_back(v[Left++]);
		else temp.push_back(v[Right++]);
	}
	while (Left <= mid) { temp.push_back(v[Left++]);} // 남은 left값 추가
	while (Right <= right) { temp.push_back(v[Right++]);} // 남은 right값 추가

	for (int i = 0; i < temp.size(); i++) v[left + i] = temp[i]; // vector 초기화
}

void MergeSort(vector<int>& v, int left, int right)
{
	if (left >= right) return;

	int mid = (left + right) / 2; // 분할

	MergeSort(v, left, mid); // 정복
	MergeSort(v, mid + 1, right); // 정복

	Merge(v, left, mid, right); // 합병
}

 

7. Quick Sort

     - 불안정 정렬 및 비교 정렬

     - 분할 정복 알고리즘

           - 매우 빠른 속도 및 비균등 분할

     - 추가 메모리 공간을 필요로 하지 않으나 정렬된 리스트에 대해 수행시간이 더 오래 걸림

           - 최선의 경우 시간 복잡도 : O(nlog₂n)

           - 최악의 경우 시간 복잡도 : O(n²)

     - 하나의 리스트를 pivot을 기준으로 두 개의 비균등한 크기로 분할

           - 정렬할 리스트의 가장 왼쪽 데이터 → pivot

     - low, high를 이용하여 리스트를 두 개의 부분 리스트로 나눔

           - low 값이 올라가면서 pivot보다 큰 데이터가 있으면 멈춤

           - high 값이 내려가면서 pivot보다 작은 데이터가 있으면 멈춤

           - low, high 값을 교환 → low < high 일때 까지 반복

int Partition(vector<int>& v, int left, int right)
{
	int pivot = v[left];
	int low = left + 1;
	int high = right;

	while (low <= high)
	{
		while (low <= right && pivot >= v[low]) { low++; }
		while (high >= left + 1 && pivot <= v[high]) { high--; }

		if (low < high) std::swap(v[low], v[high]);
	}
	std::swap(v[left], v[high]);
	return high;
}
void QuickSort(vector<int>& v, int left, int right)
{
	if (left >= right) return;

	int pivot = Partition(v, left, right); // 분할
	QuickSort(v, left, pivot - 1); // 정렬
	QuickSort(v, pivot + 1, right); // 정렬
}

 

8. Radix Sort

     - 낮은 자리수부터 비교하여 정렬하는 알고리즘

     - 비교 연산을 하지 않으며 정렬 속도가 빠르지만 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요

 

 

이름	최선	평균	최악	공간
버블 정렬	O(n2)	O(n2)	O(n2)	O(n)
선택 정렬	O(n2)	O(n2)	O(n2)	O(n2)
삽입 정렬	O(n2)	O(n)	O(n2)	O(n2)
셀 정렬	O(n1.5)	O(n1.5)	O(n1.5)	O(n)
힙 정렬	O(nlogn)	O(nlogn)	O(nlogn)	O(nlogn)
합병 정렬	O(nlogn)	O(nlogn)	O(nlogn)	O(nlogn)
퀵 정렬	O(nlogn)	O(nlogn)	O(n2)	O(nlogn)
기주 정렬	O(dn)	O(dn)	O(dn)	-