[C++] 정렬(Sort)

1. 기본적인 정렬 알고리즘

• 시간 복잡도 O(n^2)

 

1) 선택 정렬

배열 안에서 가장 큰 원소를 찾아 배열의 맨 끝 자리와 바꾸는 방식이다.

선택 정렬

for (int i = 0; i < MaxSize - 1; i++) {
	Least = i;
	for (int j = i + 1; j < MaxSize - 1; j++)
		if (Array[j] < Array[Least])
			Least = j;

	if (i != Least) {
		int Temp = Array[i];
		Array[i] = Array[Least];
		Array[Least] = Temp;
	}
}

 

2) 버블 정렬

왼쪽부터 이웃한 수를 비교하며 순서가 제대로 되어 있지 않으면 서로 바꾸는 방식이다.

버블 정렬

for (int i = MaxSize - 1; i > 0; i--)
	for (int j = 0; j < i; j++)
		if (Array[j] > Array[j + 1]) {
			int Temp = Array[j];
			Array[j] = Array[j + 1];
			Array[j + 1] = Temp;
		}

 

3) 삽입 정렬

두 번째 숫자부터 차례대로 앞의 숫자들과 비교하며 자기 자리를 찾는 방식이다.

삽입 정렬

for (int i = 1; i < MaxSize; i++) {
	int Target = Array[i];
	for (int j = i - 1; j >= 0 && Array[j] > Target; j--)
		Array[j + 1] = Array[j];
	Array[j + 1] = Target;
}

 

2. 고급 정렬 알고리즘

• 시간 복잡도 O(nlogn)

 

1) 병합 정렬

반으로 나눈 뒤 전반부와 후반부를 각각 독립적으로 정렬하고 정렬된 두 부분을 다시 합친다. 여기서 나눈 전반부와 후반부를 정렬할 때도 재귀적으로 나눠서 정렬한다.

• 순차적인 비교로 정렬을 진행하므로 연결 리스트 정렬 시 사용하면 효율적이다.

void MergeSort(int* Array, int start, int end)
{
	if (start >= end)
		return;

	int mid = (start + end) / 2;
	MergeSort(Array, start, mid);
	MergeSort(Array, mid + 1, end);

	int tmp[1000] = {};
	int i = start, j = mid + 1, k = start;
	while (i <= mid && j <= end) {
		if (Array[i] < Array[j])
			tmp[k++] = Array[i++];
		else
			tmp[k++] = Array[j++];
	}

	while (i <= mid)
		tmp[k++] = Array[i++];
	while (j <= end)
		tmp[k++] = Array[j++];

	for (i = start; i <= end; ++i)
		Array[i] = tmp[i];
}

 

2) 퀵 정렬

기준 원소(Pivot)를 삼아 작은 수는 왼쪽, 큰 수는 오른쪽으로 재배치한다. 재배치가 끝나면 또 기준 원소를 삼아 재귀적 반복하여 정렬한다.

• C++의 Sort 내 정렬 알고리즘이다.

퀵 정렬

void QuickSort(int* Array, int Left, int Right)
{
	int Pivot = Left;
	int LeftPivot = Left;
	int RightPivot = Right;

	while (LeftPivot < RightPivot)
	{
		while (Array[LeftPivot] <= Array[Pivot] && LeftPivot < Right)
			LeftPivot++;

		while (Array[RightPivot] >= Array[Pivot] && RightPivot > Left)
			RightPivot--;

		if (LeftPivot < RightPivot) {
			swap(Array[LeftPivot], Array[RightPivot]);
			continue;
		}

		swap(Array[Pivot], Array[RightPivot]);
		QuickSort(Array, Left, RightPivot - 1);
		QuickSort(Array, RightPivot + 1, Right);
	}
}

 

3) 힙 정렬

배열을 힙으로 만들고 루프 노드부터 하나씩 힙에서 제거함으로써 정렬한다.

• 가장 크거나 가장 작은 값을 구할 때 유용하다.

 

3. 특수 정렬 알고리즘

• 시간 복잡도 O(n)

 

1) 계수(Counting) 정렬

항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업이다.

• 정수로 표현하는 자료형에 대해서만 적용한다.
• 집합 내 가장 큰 정수를 알아야 사용 가능하다.

// N개의 수가 주어졌을 때, 이를 오름차순으로 정렬
// 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다.
// 둘째 줄부터 N개의 줄에는 숫자가 주어지고 10,000보다 작거나 같은 자연수이다.
    
int arr[10001] = {};
for (int i = 0; i < n; i++) {
	int num;
	scanf("%d", &num);
	arr[num]++;
}

for (int i = 1; i <= 10000; i++)
	while (arr[i]-- != 0)
		printf("%d\n", i);

 

2) 기수(Radix) 정렬

데이터를 구성하는 기본 요소(Radix)를 이용하여 정렬을 진행하는 방식이다.

 

4. Stable Sort(안정성 있는 정렬)

같은 값을 가진 데이터의 순서가 정렬 후에도 바뀌지 않는 정렬로 버블 정렬, 삽입 정렬, 병합 정렬, 기수 정렬, 계수 정렬이 있다.

 

5. 정렬 알고리즘 선택

• 시간 복잡도에 따라 선택
• 공간 복잡도에 따라 선택: 병합 정렬 같은 경우 추가 메모리 공간을 사용해야 한다.
• Stable에 따라 선택

 

시간 복잡도