Sort

1. 선택 정렬 (Selection Sort)

n개의 요소를 가지고 있는 배열을 돌며,

가장 작은 요소의 인덱스를 찾아서 타겟 인덱스의 요소와 바꿔줌.

n-1, n-2, ... , 1 까지 반복하므로 시간 복잡도 O(n^2),

배열 하나 써서 공간 복잡도 O(n)

[그림 1] 선택 정렬

int arr[] = { 6, 5, 3, 1, 8, 7, 2, 4 };

for(int i = 0; i < sizeof(arr)/sizeof(int); i++)
{
	int min_idx = i;
	for(int j = i + 1; j < sizeof(arr)/sizeof(int); j++)
	{
		if(arr[min_idx] > arr[j])
			min_idx = j;
	}
		
	int temp = arr[min_idx];
	arr[min_idx] = arr[i];
	arr[i] = temp;
}

2. 삽입 정렬 (Insertion Sort)

요소를 순회하며, 그보다 앞에 있는 요소들과 비교하여 작은 값 앞으로 이동한다.

최악의 경우는 역으로 정렬돼있을 때, n-1, n-2, ... 1개까지 모두 비교하므로 시간 복잡도 O(n^2)

최선의 경우 정렬돼있을 때, 1번씩 비교하므로 시간 복잡도 O(n)

공간 복잡도는 선택 정렬과 마찬가지로 O(n)

[그림 2] 삽입 정렬

int arr[] = { 6, 5, 3, 1, 8, 7, 2, 4 };

for(int i = 1; i < sizeof(arr)/sizeof(int); i++)
{
	int j = i - 1, key = arr[i];
	while(j >= 0 && key < arr[j])
	{
		arr[j + 1] = arr[j];
		j--;
	}
	arr[j + 1] = key;
}

위 코드를 보면 비교할 요소보다 큰 요소들을 단순히 뒤로 당기고, 작은 요소를 찾았을 때 key에 저장한 값을 삽입한다.

3. 병합 정렬 (Merge Sort)

분할 정복(Divide and Conquer) 방식으로 설계됨. 아래 그림처럼 반씩 쪼개서 모두 나눈 다음, 합칠 때 정렬한다.

이 정렬은 분할, 합병 두 과정으로 나뉜다.

1) 분할

- (시작 + 끝) / 2 기준으로 배열을 반으로 나눈다.

- 배열 크기가 1이 될때까지 반복한다.

2) 병합

- 합칠 두 배열(A, B)의 시작 인덱스를 각각 i, j에 저장하자. 그리고 합칠 배열 C를 선언하자.

- A[i] < B[j]이면, A[i]를 C에 집어넣고 i++, 반대의 경우 B[j]를 C에 집어넣고 j++. 이를 계속 반복한다.

- i, j 둘 중 하나라도 끝에 도달하면 반복을 중단한다.

- A, B 중 끝까지 도달 못한 배열의 값을 모두 C에 저장한다.

- C를 원래의 배열에 저장한다.

합병의 시간 복잡도: O(N), 분할의 시간 복잡도 (logN), 따라서 병합 정렬의 시간 복잡도는 O(NlogN)이다.

공간 복잡도는 O(N): 배열 두개 사용해서 2N이다.

[그림 3] 병합 정렬

int arr[] = { 6, 5, 3, 1, 8, 7, 2, 4 };

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

...

void merge(int* arr, int start, int end, int middle)
{
	vector ret;
	int i = start, j = middle + 1, copy = 0;

	// 비교
	while(i <= middle && j <= end)
	{
		if(arr[i] < arr[j]) ret.push_back(arr[i++]);
		else if(arr[i] > arr[j]) ret.push_back(arr[j++]);
	}

	// 남은 값 채워주기
	while(i <= middle) ret.push_back(arr[i++]);
	while(j <= end) ret.push_back(arr[j++]);

	// 원래 배열에 복사
	for(int k = start; k <= end; k++)
		arr[k] = ret[copy++];
}

void mergeSort(int* arr, int start, int end)
{
	if(start < end)
	{
		int middle = (start + end) / 2;
		// 분할
		mergeSort(arr, start, middle);
		mergeSort(arr, middle + 1, end);
		// 병합
		merge(arr, start, end, middle);
	}
}

4. 퀵 정렬 (Quick Sort)

병합 정렬처럼 분할 정복(Divide and Conquer) 방식을 사용하지만, 병합 정렬과 다르게 분할 단계에서 중요한 작업이 많이 일어남.

pivot이라고 불리는 기준을 하나 두고, 그 기준보다 작은 값을 왼쪽, 큰 값을 오른 쪽으로 두는 식으로 정렬한다.

정렬 방법은 아래와 같다.

1) pivot을 선택한다. 인덱스 0의 값, 랜덤 등으로 선택한다.

2) 배열의 가장 왼쪽 인덱스를 left, 가장 오른쪽 인덱스를 right에 저장한다.

3) right를 1씩 감소시키다 arr[right] < pivot이면 멈춘다. 그 후 left를 1씩 증가시키다 arr[left] > pivot이면 멈춘다. 이 때 left < right 일때만 동작한다.

4) 둘 다 멈추면 left와 right 위치의 값을 바꾼다.

5) left < right가 될 때까지 위 3), 4)를 반복한다.

6) 위 과정이 끝나면 배열의 첫 번째 값과 pivot의 값을 바꿔준다.

7) 배열 처음 ~ left - 1, left + 1 ~ 배열 끝, 두 배열로 나누어 위 과정을 반복한다.

평균 시간 복잡도는 O(NlogN)이지만, 이미 정렬돼있는 경우 O(N^2)이 된다. 이를 방지하기 위해선 pivot을 중간값이나 랜덤으로 해야한다.

병합정렬보다 느리다고 생각하겠지만 병합정렬보다 빠르다고 한다. (병합 과정보다 파티셔닝이 빠르다고 한다.)

[그림 4] 퀵 정렬

int arr[] = { 6, 5, 3, 1, 8, 7, 2, 4 };

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

...

void quickSort(int* arr, int start, int end)
{
	int pivot = arr[start];
	int left = start, right = end;

	while(left < right)
	{
		while(pivot <= arr[right] && left < right) right--;
		while(pivot >= arr[left] && left < right) left++;
		if(left < right)
			swap(arr[left], arr[right]);
	}
	// 피봇 기준으로 작은거 왼쪽 큰거 오른쪽으로 만들어야 해서 바꿈
	swap(arr[left], arr[start]);
    // partitioning
	if(start < left)
		quickSort(arr, start, left - 1);
	if(end > right)
		quickSort(arr, left + 1, end);
}

* 참고

정렬 종류 및 코드

http://hsp1116.tistory.com/33

정렬 및 알고리즘 자세히

https://ko.khanacademy.org/computing/computer-science/algorithms/