정렬(Sorting)

1. 버블 정렬(Bubble Sort)

배열 처음부터 시작해서, 바로 옆에 있는 값과 비교하고 우선 순위에 맞게 위치를 바꾸거나 그대로 둔다.

정리하자면, "우선 순위가 낮은 걸 뒤로 보내는 방법"이라고 할 수 있다.

 

step1) 값이 제일 큰 걸 우선 순위가 낮다고 할 때, '4'가 제일 뒤에 위치하게 된다. 

step2) 그 다음 큰 값인 '3'이 '4'앞에 위치한다.

step3) 그 다음 큰 값인 '2'가 '3'앞에 위치하여 결과적으로 오름차순 정렬이 끝난다.

 

- 성능 = O($n^{2}$)

 

 

2. 선택 정렬(Selection Sort)

아직 정렬되지 않은 배열 부분을 모두 차례대로 읽어가면서, 최솟값(우선순위가 높은 것)을 찾아 앞으로 위치시킨다.

- 성능 = O($n^{2}$)

 

 

3. 삽입 정렬(Insertion Sort)

정렬된 배열에 새로운 데이터의 적절한 위치를 찾아 넣는 방식이라고 볼 수 있다.

 

step1) 주황색 박스가 정렬된 배열이다.

step2)

step3)

 

- 성능 = O($n^{2}$)

 

 

4. 힙 정렬(Heap Sort)

데이터를 차례대로 힙에 모두 넣은 후, 다시 하나씩 빼면서 차례대로 배열에 담으면 정렬이 끝난다.

힙에 대한 자세한 설명은 아래 게시글을 참고하길 바란다.

우선순위 큐(Priority Queue)

 

- 성능 = O(n$log_{2}$n)

*$log_{2}$n(삽입&삭제) * n(개의 데이터를 연산 수행)

 

 

5. 병합 정렬(Merge Sort)

[1단계] 분할하기 (Divide)

한번에 완전히 분해하지 않는 이유는 분할과 결합이 재귀적으로 이루어지기 때문이다.

 

[2단계] 정복하기 (Conquer)

: 분할하여 작은 범위에서 문제 해결하기

[3단계] 결합하기 (Combine)

 

- 소스코드

#include <stdio.h>
#include <stdlib.h>

void Merge();
void MergeSort();

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

	MergeSort(arr, 0, sizeof(arr) / sizeof(int) - 1);

	for (i = 0; i < 5; i++)
		printf("%d ", arr[i]);

	printf("\n");
	return 0;
}

//두 개 정렬하면서 합치기 (2,3단계)
void Merge(int arr[], int left, int mid, int right) {
	int frontarr = left;
	int reararr = mid + 1;
	int i;

	int* resultArr = (int*)malloc(sizeof(int)*(right + 1));
	int now = left;

	while (frontarr <= mid && reararr <= right) {
		if (arr[frontarr] <= arr[reararr])
			resultArr[now] = arr[frontarr++];
		else
			resultArr[now] = arr[reararr++];
		now++;
	}

	if (frontarr > mid) {
		for (i = reararr; i <= right; i++, now++)
			resultArr[now] = arr[i];
	}
	else {
		for (i = frontarr; i <= mid; i++, now++)
			resultArr[now] = arr[i];
	}

	//합친 배열을 우리가 사용하는 배열로 복사하기
	for (i = left; i <= right; i++)
		arr[i] = resultArr[i];

	free(resultArr);
}

void MergeSort(int arr[], int left, int right) {
	int mid;

	if (left < right) {
		mid = (left + right) / 2;

		//반씩 나눠가면서 재귀 호출
		MergeSort(arr, left, mid);
		MergeSort(arr, mid + 1, right);

		//합치면서 정렬
		Merge(arr, left, mid, right);
	}
}

- 성능 = O(n$log_{2}$n)

 

 

6. 퀵 정렬(Quick Sort) 

퀵 정렬에서 핵심 용어인 'pivot'은 정렬을 진행하는데 필요한 기준이라고 생각하면 된다.

추가로 사용할 변수의 역할을 살펴보자

• low = pivot을 제외하고 볼 때, 배열에서 가장 왼쪽 값
• high = pivot을 제외하고 볼 때, 배열에서 가장 오른쪽 값
• left = 정렬할 배열의 가장 왼쪽 값
• right = 정렬할 배열의 가장 오른쪽 값

 

step1) 배열의 가장 왼쪽을 pivot이라고 정하겠다. 다른 값을 정해도 된다. 

low는 pivot보다 큰 값을 만날 때까지 오른쪽으로 이동하고, high는 pivot보다 작은 값을 만날 때까지 왼쪽으로 이동한다. 서로 몇 칸 움직이는지는 신경쓰지 않는다. low가 3칸 이동해도, high는 2칸만 이동할 수 있다.

 

아래는, low는 7에서, high는 4에서 멈추었다. 그리고 이 두 값의 위치를 바꿔준다.

step2) 4&7의 자리가 바뀐 것을 볼 수 있고, 계속해서 low는 이동해서 9를 찾고, high는 2를 찾아 두 값의 위치를 바꿔준다.

step3) 이렇게 진행하다보면, 아래와 같이 low & high 가 교차되는 때가 온다. 그러면, 진행을 멈추고 pivot과 high에 있는 값을 바꿔준다.

step4) pivot '5'를 기준으로 좌&우가 나뉘어진 것을 볼 수 있다. 나뉘어진 범위 각각 step1부터 똑같은 과정을 반복한다.

 

- 소스코드

#include <stdio.h>

void Swap();
int Partition();
void QuickSort();

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

	QuickSort(arr, 0, sizeof(arr) / sizeof(int) - 1);
	for (i = 0; i < 7; i++) {
		printf("%d ", arr[i]);
	}
	printf("\n");
	return 0;
}

void Swap(int arr[], int idx1, int idx2) {
	int temp = arr[idx1];
	arr[idx1] = arr[idx2];
	arr[idx2] = temp;
}

int Partition(int arr[], int left, int right) {
	int pivot = arr[left];//pivot은 arr의 제일 왼쪽 값으로 하겠다.
	int low = left + 1;
	int high = right;

	while (low <= high) {
		//low를 오른쪽으로 이동
		while (pivot > arr[low])
			low++;
		//high를 왼쪽으로 이동
		while (pivot < arr[high])
			high--;

		if (low <= high)
			Swap(arr, low, high);
	}

	Swap(arr, left, high);
	return high;
}

void QuickSort(int arr[], int left, int right) {
	if (left <= right) {
		int pivot = Partition(arr, left, right);
		QuickSort(arr, left, pivot - 1);
		QuickSort(arr, pivot + 1, right);
	}
}

 

- 성능 = O(n$log_{2}$n)

*정렬되어 있는 배열일 때 = O($n^{2}$)

=> pivot을 기준으로 좌우로 나뉘어지지 않아서 n번의 재귀호출이 불린다.

 

 

7. 기수 정렬(Radix Sort)

기수 정렬의 장점은 비교연산을 하지 않고 앞에서 본 정렬 알고리즘의 성능보다 더 좋게 낼 수 있다는 점이다.

반면에, 단점은 배열에 있는 데이터 값들의 길이가 모두 같아야만 사용할 수 있다는 것이다.

 

방법1) LSD = Least Significant Digit의 약자로, 작은 자릿수(숫자의 경우, 1의 자리)부터 보고 정렬

방법2) MSD = Most Significant Digit의 약자, 큰 자릿수부터 보고 정렬하되 중간에 점검하는 연산이 필요

수의 대소비교에 있어서 낮은 자릿수보다 큰 자릿수의 영향력이 큰데, 큰 자릿수부터 비교하면 낮은 자릿수가 큰 자릿수에게 영향을 주게 되어있기 때문이다.

 

- 성능 = O(n)

*데이터의 길이 l * 데이터 수 n = ln