[알고리즘]#3_정렬 알고리즘

 

#1. 개념

 

1. 정렬 알고리즘

 

[정의] : 정렬 알고리즘은 데이터를 특정한 순서로 재배치하는 알고리즘입니다. 정렬 순서는 일반적으로 오름차순(ascending order/less) 또는 내림차순(descending order/greater)으로 정렬되며, 정렬된 데이터는 효율적인 검색, 삽입, 삭제 등의 연산을 가능케 합니다.

[종류]

1. 삽입 정렬 : 배열을 순회하며, 현재 원소를 이미 정렬된 부분 배열과 비교하며 적절한 위치에 삽입
2. 선택 정렬 : 배열에서 가장 작은 원소를 선택해, 정렬되지 않은 부분의 첫 번째 원소와 교환
3. 버블 정렬 : 배열의 인접한 두 원소를 비교하여 정렬
4. 병합 정렬 : 분할-정복을 기반으로 배열을 두 부분 배열로 분할하여 정렬하고, 병합
5. 퀵 정렬 : 분할-정복을 기반으로 기준 원소(Pivot)를 정해 이보다 작은 원소는 왼쪽, 큰 원소는 오른쪽
6. 힙 정렬 : 배열의 원소들을 토대로 힙을 구성하여 정렬

 

---

 

#2. 삽입 정렬

 

1. 개념

1. 정의 : 삽입 정렬은 배열의 각 요소를 "정렬된 부분(왼쪽)"과 비교하며 적절한 위치에 삽입하는 정렬 알고리즘입니다.
2. 안정성 : 삽입 정렬은 Stable Sort 알고리즘으로, 동일한 값에 대해서 상대적인 순서가 유지됩니다.
3. 효율성 : 삽입 정렬은 비교적 크기가 작은 배열이나 정렬된 배열에 대해서 효율적인 알고리즘입니다.
4. 공간 복잡도 : 더불어, 삽입 정렬 알고리즘은 In-place sorting이기 때문에 추가적인 메모리 공간이 필요하지 않습니다.
5. 시간 복잡도 : 삽입 정렬은 최선의 경우(이미 정렬된 배열) O(n)의 시간 복잡도를 가지며, 최악의 경우 O(n²)의 시간 복잡도를 갖습니다. 

 

2. 과정

1. 주어진 배열의 왼쪽은 "정렬된 부분 배열", 그리고 오른쪽은 "정렬되지 않은 부분 배열"로 나눕니다.
2. 먼저, 정렬되지 않은 부분 배열의 첫 번째 요소를 선택합니다.
3. 정렬되지 않은 부분 배열의 첫 번째 요소를 정렬된 부분 배열의 마지막 요소부터 차례대로 비교합니다.
4. 이 과정에서, 정렬된 부분 배열의 원소가 정렬되지 않은 부분 배열의 원소보다 클 경우, 해당 원소를 오른쪽으로 한 칸씩 이동시킵니다.
5. 최종적으로, 정렬되지 않은 부분 배열에서 선택한 원소는 자신보다 작은 값을 만나게 되어 해당 원소의 앞에 위치하도록 합니다.
6. 정렬되지 않은 부분 배열이 모두 정렬될 때까지 2~5번 작업을 반복합니다.

 

3. 코드

#include <iostream>
#include <vector>
using namespace std;

void InsertionSort(vector<int>& v)
{
	// #1. 정렬되지 않은 부분 배열을 순회
	for (int i = 1; i < v.size(); i++)
	{
		int Key = v[i];
		// #2. 정렬된 부분 배열의 마지막 원소
		int Idx = i - 1;
		// #3. 정렬되지 않은 부분 배열과 정렬된 부분 배열의 비교
		while (Idx >= 0 && v[Idx] > Key)
		{
			// #4. 오른쪽으로 한 칸 이동
			v[Idx + 1] = v[Idx];
			Idx--;
		}
		// 5. 정렬되지 않은 부분 배열의 원소가 삽입될 위치
		v[Idx + 1] = Key;
	}
}

 

---

 

#3. 선택 정렬

 

1.개념

• 정의 : 선택 정렬은 정렬 알고리즘 중 하나로, 주어진 배열에서 최솟값을 선택하여 정렬된 부분 배열과 교환하는 과정을 반복하는 알고리즘입니다. 
• 안정성 : 선택 정렬은 Stable Sort가 아닙니다.
• 효율성 : 그리고, 선택 정렬은  작은 규모의 배열 혹은 큰 규모의 배열에서 성능상 이점이 없으며, 다른 정렬 알고리즘이 더욱 선호됩니다.
• 공간 복잡도 : 선택 정렬은 In-place Sorting으로 추가적인 메모리 공간이 필요하지 않습니다.
• 시간 복잡도 : 최선, 최악의 경우 모두 시간 복잡도가 O(n²)입니다.

 

2. 과정

1. 주어진 배열을 순회하며 최솟값을 찾습니다.
2. 최솟값을 갖는 위치와 현재 위치의 원소 값을 바꿉니다.

 

3. 코드

#include <iostream>
#include <vector>
using namespace std;

void SelectionSort(vector<int>& v)
{
	for (int i = 0; i < v.size()-1; i++)
	{
		int Min = i;
		for (int j = i + 1; j < v.size(); j++)
		{
			// #1. 최솟값 찾기
			if (v[j] < v[Min])
			{
				Min = j;
			}
		}
		// #2. 현재 위치와 최솟값의 위치가 다르다면, 값을 바꿉니다.
		if (Min != i)
			swap(v[i], v[Min]);
	}
}

 

---

 

#4. 버블 정렬

 

1. 개념

1. 정의 : 버블 정렬은 배열의 인접한 두 개의 원소를 비교하고 필요한 경우 교환을 반복하여 정렬을 수행하는 알고리즘입니다.
2. 안정성 : 버블정렬은 Stable Sort 알고리즘으로, 동일한 값에 대해서 상대적인 순서가 유지됩니다.
3. 효율성 : 버블 정렬은 구현이 간단하고 이해하기 쉬우나, 큰 규모의 배열에 대해 비효율적입니다. 
4. 공간 복잡도 : 버블 정렬은 In-place Sorting으로 추가적인 메모리 공간이 필요하지 않습니다.
5. 시간 복잡도 : 버블 정렬의 최선 시간 복잡도(이미 정렬된 상태)는 O(n)이며, 최악의 경우 시간 복잡도는 O(n²)입니다.

 

2. 과정

1. 인접한 두 원소를 비교하고 필요할 경우 교환합니다.
2. 배열을 순회하며 1번 작업을 수행하면 가장 큰 원소가 배열의 마지막 위치로 이동합니다.
3. 정렬 범위를 하나씩 줄여가며 위 과정을 반복합니다.

 

3. 코드

#include <iostream>
#include <vector>
using namespace std;

void BubbleSort(vector<int>& v)
{
	for (int i = 0; i < v.size() - 1; i++)
	{
		for (int j = 0; j < v.size() - 1 - i; j++)
		{
			// #1. 인접한 두 원소 값을 비교하고 교환
			if (v[j] > v[j + 1])
				swap(v[j], v[j + 1]);
		}
	}
}

 

---

 

#5. 병합 정렬

 

1. 개념

1. 정의 : 병합 정렬은 분할 정복 알고리즘에 기반한 정렬 알고리즘입니다. 병합 정렬은 주어진 배열을 두 개의 작은 부분 배열로 분할하고, 각 부분 배열을 재귀적으로 정렬하여, 최종적으로 두 배열을 결합하여 하나의 정렬된 배열을 얻는 정렬 알고리즘입니다.
2. 안정성 : 병합 정렬은 동일한 값에 대해 상대적인 순서가 변하지 않는 Stable Sort(안정적인 정렬) 알고리즘입니다.
3. 효율성 : 병합 정렬은 최선, 평균, 그리고 최악의 경우 모두 O(n log n)의 시간 복잡도를 가집니다. 따라서, 대부분의 경우 병합 정렬은 효율적으로 동작합니다.
4. 공간 복잡도 : 병합 정렬 알고리즘은 추가적인 임시 배열을 통해 분할된 부분 배열을 정렬하고 병합하는 작업을 수행합니다. 따라서, 병합 정렬은 알고리즘 수행 과정에서 추가적인 메모리 공간이 필요하며, 공간 복잡도는 O(n)입니다.
5. 시간 복잡도 : 병합 정렬 알고리즘의 최선, 평균, 그리고 최악 시간 복잡도는 모두 O(n log n)입니다. 병합 정렬은 항상 주어진 배열을 절반으로 분할하여 정렬하는 작업을 수행합니다. 병합 정렬에서 분할 작업은 log n번 수행하며, 결합 단계에서 비교 연산의 횟수는 n번 수행합니다. 최종적으로, 모든 경우 O(n log n)의 시간 복잡도의 성능을 보여줍니다.

 

2. 과정

1. 먼저, 병합 정렬 알고리즘은 주어진 배열을 두 개의 부분 배열로 분할합니다. 이때, 배열의 중간 지점을 찾아 각각 왼쪽 부분 배열, 그리고 오른쪽 부분 배열로 나눕니다. 이 과정은 부분 배열의 크기가 충분히 작을 때까지(Base Case가 될 때까지)반복합니다.
2. 다음으로, 분할된 두 부분 배열을 재귀적으로 정렬합니다.
3. 마지막으로, 분할된 두 부분 배열을 하나의 배열로 병합합니다. 

 

3. 코드

#include <iostream>
#include <vector>
using namespace std;

void MergeSort(vector<int>& arr, int Left, int Right);
void Merge(vector<int>& arr, int Left, int Mid, int Right);

void MergeSort(vector<int>& arr, int Left, int Right)
{

	if (Left < Right)
	{
		int Mid = Left + (Right - Left) / 2;

		// #1. 두 부분 배열에 대해 재귀 호출
		MergeSort(arr, Left, Mid);
		MergeSort(arr, Mid+1, Right);

		// #2. 두 부분 배열을 병합하는 함수
		Merge(arr, Left, Mid, Right);
	}

}

void Merge(vector<int>& arr, int Left, int Mid, int Right)
{
	int LeftSize = Mid - Left + 1;
	int RightSize = Right - Mid;

	// #3. 두 부분 배열을 저장할 임시 배열
	vector<int> Left_Half(LeftSize);
	vector<int> Right_Half(RightSize);

	for (int i = 0; i < LeftSize; i++)
	{
		Left_Half[i] = arr[Left + i];
	}

	for (int i = 0; i < RightSize; i++)
	{
		Right_Half[i] = arr[Mid + i + 1];
	}

	int Left_Idx = 0;
	int Right_Idx = 0;
	int Res_Idx = Left;

	// #4. 왼쪽 부분 배열과 오른쪽 부분 배열의 원소들을 차례대로 비교하여, 하나의 배열로 병합 
	while (Left_Idx < LeftSize && Right_Idx < RightSize)
	{
		if (Left_Half[Left_Idx] <= Right_Half[Right_Idx])
		{
			arr[Res_Idx++] = Left_Half[Left_Idx++];
		}
		else
		{
			arr[Res_Idx++] = Right_Half[Right_Idx++];
		}
	}

	// #5. 위 작업 과정에서 남은 한 부분 배열의 원소들을 병합 배열 뒤에 추가
	while (Left_Idx < LeftSize)
	{
		arr[Res_Idx++] = Left_Half[Left_Idx++];
	}

	while (Right_Idx < RightSize)
	{
		arr[Res_Idx++] = Right_Half[Right_Idx++];
	}

}


int main()
{

	vector<int> arr = { 38, 27, 43, 3, 9, 82, 10 };

	MergeSort(arr, 0, arr.size() - 1);

	for (int i = 0; i < arr.size(); i++)
	{
		cout << arr[i] << '\n';
	}


	return 0;
}

 

---

 

#6. 퀵 정렬

 

1. 개념

1. 정의 : 퀵 소트는 분할 정복(Divide And Conquer) 알고리즘에 기반한 정렬 알고리즘입니다. 데이터 목록의 Pivot 원소를 기준으로 해당 원소보다 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 분할하여 각 부분 리스트에 대해 재귀적으로 정렬을 수행하는 정렬 방법입니다.
2. 안정성 : 퀵 정렬은 동일한 값에 대해 상대적인 순서가 변하므로, Stable Sort가 아닙니다.
3. 효율성 : 일반적으로, 퀵 정렬은 매우 효율적인 정렬 알고리즘입니다.
4. 공간 복잡도 : 퀵 정렬은 In-place sorting으로 추가적인 메모리 공간이 필요 없습니다.
5. 시간 복잡도 : 퀵 정렬은 최선의 경우 O(n log n)의 시간 복잡도를 가지며, 최악의 경우 O(n²)의 시간 복잡도를 갖습니다. 주어진 배열이 이미 정렬된 경우, 혹은 역순으로 정렬된 경우 퀵 정렬은 최악의 성능을 보여줍니다. 왜냐하면, Pivot 원소 선택 시 배열 분할에 불균형이 발생해 재귀 호출의 깊이가 n에 가까워져 비교 연산이 최대로 늘어나기 때문입니다.

 

2. 과정

1. 주어진 데이터 목록에서 Pivot 원소를 선택합니다.
2. 다음으로 Partition 작업을 수행합니다. Partition 작업은 데이터 목록을 순회하며 Pivot 원소보다 작은 값은 Pivot 원소의 왼쪽으로 이동하고, 반대로 큰 값은 오른쪽으로 이동시킵니다.
3. 분할된 두 개의 하위 배열에 대해 재귀적으로 퀵 정렬을 수행합니다.

 

3. 코드

#include <iostream>
#include <vector>
using namespace std;

void QuickSort(vector<int>& arr, int l, int r);
int partition(vector<int>& arr, int l, int r);

void QuickSort(vector<int>& arr, int l, int r)
{
	if (l < r)
	{
		int pivot = partition(arr, l, r);

		QuickSort(arr, l, pivot - 1);
		QuickSort(arr, pivot+1, r);
	}
}

int partition(vector<int>& arr, int l, int r)
{
	int pivot = arr[r];
	int i = l - 1;

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

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

int main()
{
	vector<int> arr = { 10, 7, 8, 9, 1, 5 };
	int n = arr.size();

	QuickSort(arr, 0, n - 1);

	for (const auto& val : arr)
	{
		cout << val << '\n';
	}

	return 0;
}

 

Details

 

1. 먼저, 퀵 정렬 알고리즘은 Partition 함수를 통해 주어진 배열의 가장 오른쪽에 위치한 값을 Pivot으로 설정해 왼쪽은 Pivot 값보다 작은 값, 반대로 오른쪽은 Pivot 값보다 큰 값으로 정렬합니다. 마지막으로, Parition 함수는 Pivot 값이 위치한 인덱스를 반환합니다.
2. 다음으로, 퀵 정렬 알고리즘은 Pivot 위치 기준 왼쪽 부분 배열과 오른쪽 부분 배열에 대해 퀵 정렬 알고리즘을 재귀적으로 호출합니다.

 

4. Median-of-three 방법

 

[정의] : "Median-of-three" 방법이란, 퀵 정렬에서 기준 원소(Pivot)를 선택하는 방법 중 하나로, 배열의 첫 번째, 중간, 마지막 원소 중 중간 값(median)을 선택하여 기준 원소로 활용하는 방법입니다.

[목적] : "Median-of-three" 방법은 이미 정렬된 배열에 대하여 퀵 정렬 수행 시 최악의 경우 O(n²)의 시간 복잡도를 갖기 때문에, Pivot 선택 과정에서 중앙 값을 선택하여 '분할' 작업의 최적화를 위해 활용됩니다. 

[동작 방식]

1. 배열의 첫 번째, 중간, 마지막 원소를 비교합니다.
2. 이 중에서 중간 값을 Pivot으로 설정합니다.
3. 피봇을 배열의 마지막 원소와 교환합니다.
4. 피봇을 기준으로 이보다 작은 값은 피봇의 왼쪽에, 큰 값은 피봇의 오른쪽에 위치시켜 분할합니다.
5. 왼쪽 부분 배열과 오른쪽 부분 배열에 대해 재귀적으로 퀵 정렬을 수행합니다.

 

4. Median-of-three 코드

#include <iostream>
#include <vector>
using namespace std;

int medianOfThree(vector<int>& arr, int l, int r) {
    int mid = l + (r - l) / 2;

    if (arr[l] > arr[mid]) {
        swap(arr[l], arr[mid]);
    }
    if (arr[l] > arr[r]) {
        swap(arr[l], arr[r]);
    }
    if (arr[mid] > arr[r]) {
        swap(arr[mid], arr[r]);
    }

    return mid;
}

int partition(vector<int>& arr, int l, int r) {
    int pivotIndex = medianOfThree(arr, l, r);
    swap(arr[pivotIndex], arr[r]);

    int pivot = arr[r];
    int i = l - 1;

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

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

void quickSort(vector<int>& arr, int l, int r) {
    if (l < r) {
        int pivotIndex = partition(arr, l, r);

        quickSort(arr, l, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, r);
    }
}

int main() {
    vector<int> arr = {10, 7, 8, 9, 1, 5};
    int n = arr.size();

    quickSort(arr, 0, n - 1);

    for (const auto& val : arr) {
        cout << val << '\n';
    }

    return 0;
}

 

---

 

#7. 힙 정렬

 

1. 개념

1. 정의 : 힙 정렬은 주어진 배열을 통해 힙을 구성하고, 이후 힙의 특성을 활용해 정렬을 수행하는 알고리즘입니다.
2. 안정성 : 힙 정렬은 동일한 값에 대해 상대적인 순서가 변하므로, Stable Sort가 아닙니다.
3. 효율성 : 힙 정렬은 비교 기반 정렬 알고리즘 중에서도 비교적 빠른 정렬 알고리즘으로 알려져 있습니다.
4. 공간 복잡도 : 힙 정렬 알고리즘 수행 과정에서 주어진 배열외에도 힙을 구성하기 위한 추가적인 공간이 필요합니다.
5. 시간 복잡도 : 힙 정렬은 최선의 경우 O(n log n)의 시간 복잡도를 갖습니다. 힙 정렬 알고리즘은 주어진 배열을 힙으로 구성하는 단계와 힙의 루트 노드를 추출하고 재구성하는 단계로 진행됩니다. 그리고, 각 단계는 평균적으로 O(log n)의 시간이 소요되며, 최종적으로 힙 정렬의 평균 시간 복잡도는 O(n log n)입니다. 힙 정렬은 최악의 경우 O(n log n)의 시간 복잡도를 갖습니다. 힙 정렬 알고리즘 수행 과정에서 주어진 배열이 역순으로 정렬되어 있을 경우 최악의 수행 성능을 보여줍니다. 힙 정렬 알고리즘의 평균 시간 복잡도와 최악 시간 복잡도가 같은 이유는 힙 정렬에 필요한 수행 시간은 항상 트리의 높이(log n)만큼입니다.

 

2. 과정(최대 힙)

1. 먼저, 주어진 배열을 힙으로 구성하는 Heapify 함수를 정의합니다. Heapify 함수는 배열과 현재 노드를 인자로 전달받아, 현재 노드를 부모 노드 혹은 최대 값을 갖는 노드로 가정하고 해당 노드의 왼쪽 자식 노드와 오른쪽 자식노드가 올바르게 위치하는지 확인합니다. "최대 힙"의 경우 부모 노드는 자식 노드들보다 값이 더 큽니다. 따라서, 부모 노드, 왼쪽 자식 노드, 그리고 오른쪽 자식 노드 중 가장 큰 값을 갖는 노드를 부모 노드로 변경하고, swap() 함수를 통해 그 위치를 변경합니다. 즉, Heapify 함수는 주어진 배열과 현재 노드를 전달받아 힙을 구성하거나, 재구성하기 위한 함수입니다.
2.  다음으로, HeapSort 함수는 주어진 배열의 중간 위치(Size/2 -1)부터 역순으로 Heapify 함수를 호출하여 힙을 구성합니다. "중간 위치"부터 호출하는 이유는 배열을 통해 힙을 구현할 때 일반적으로 부모 노드가 위치한 인덱스가 n이라면, 왼쪽 자식 노드의 위치는 2*n+1, 그리고 오른쪽 자식 노드의 위치는 2*n+1이기 때문입니다.
3. 이렇게 주어진 배열을 통해 최대 힙을 구성하여, 배열의 첫 번째 요소는 힙의 루트 노드를 의미하며, 이는 곧 배열의 가장 큰 값을 의미합니다. 따라서, 최종적으로 배열을 오름차순 정렬하기 위해 루트 노드(배열의 첫 번째 항목)를 배열의 마지막 위치로 변경합니다. 이미 정렬된 값들을 제외한 나머지 항목들에 대해 반복적으로 Heapify를 수행하며 최종적으로 배열을 오름차순 정렬 합니다.

 

3. 코드

#include <iostream>
#include <vector>
using namespace std;

void Heapify(vector<int>& arr, int size, int cur)
{
	int Largest = cur;
	int LeftChild = cur * 2 + 1;
	int RightChild = cur * 2 + 2;

	// #0. Largest 노드 vs Left Child 노드
	if (LeftChild < size && arr[LeftChild] > arr[Largest])
	{
		Largest = LeftChild;
	}
	// #1. Largest 노드 vs Right Child 노드
	if (RightChild < size && arr[RightChild] > arr[Largest])
	{
		Largest = RightChild;
	}
	// #2. 주어진 노드와 최대 값을 갖는 노드가 다르다면, Swap 진행 후 Heapify 함수 재귀 호출
	if (Largest != cur)
	{
		swap(arr[cur], arr[Largest]);
		Heapify(arr, size, Largest);
	}

}

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

	// #1. 배열의 중간부터 역순으로 Heapify 함수 수행
	for (int i = n/2-1; i >= 0; i--)
	{
		Heapify(arr, n, i);
	}

	// #2. 최대 값을 갖는 첫 번째 요소를 마지막으로 배치하고, 나머지 요소들에 대해 다시 Heapify 수행
	for (int i = n - 1; i > 0; i--)
	{
		swap(arr[0], arr[i]);

		Heapify(arr, i, 0);
	}

}

int main()
{
	vector<int> arr = { 10, 7, 8, 9, 1, 5 };
	int n = arr.size();

	HeapSort(arr);

	for (const auto& val : arr)
	{
		cout << val << '\n';
	}

	return 0;
}

 

Details

 

1. Heapify 함수를 정의합니다. Heapify 함수는 인자로 전달받은 배열과 현재 노드를 통해 Heap 자료구조가 수행하는 정렬 작업을 수행합니다. 현재 노드, 왼쪽 자식 노드, 그리고 오른쪽 자식 노드의 값을 비교해 가장 큰 값을 갖는 노드를 부모 노드로 위치를 변경합니다. 그리고, 인자로 전달 받은 현재 노드와 부모 노드가 다르다면, 부모 노드가 된 노드에 대해 Heapify를 재귀 호출합니다.
2. HeapSort 함수는 주어진 배열에 대해 중간 위치(n/2 -1)부터 역순으로 Heapify 함수를 호출합니다
3. 그리고, HeapSort 함수는 배열을 역순으로 순회하며 힙의 크기를 하나씩 줄여가며 정렬 작업을 수행합니다. 이때, 힙의 크기를 하나씩 줄여가는 이유는 가장 큰 값을 갖는 배열의 첫 번째 요소는 항상 배열의 가장 뒤로 위치를 변경되기 때문입니다. 정렬 작업을 수행하며 이미 정렬된 상태의 값들은 n, n-1, n-2... 0 위치에 차례대로 위치하기 때문입니다.