Chap 07. 정렬

'시간 복잡도에 대한 빅-오' >> '비교의 횟수'

'동일한 빅-오의 복잡도 세밀한 비교' >>  '이동의 횟수'

---

<힙 정렬>

힙을 이용한 정렬
힙의 특성을 활용하여,(힙에 데이터를 저장하게되면 우선순위 순서대로 저장이된다.)
힙에 정렬할 대상을 모두 넣었다가 다시 꺼내어 정렬을 진행한다!

for( i = 0; i < n; i ++)
	HInsert(&heap,arr[i]);

for( i = 0; i < n; i ++)
	arr[i] = HDelete(&heap);

void HInsert(Heap * ph, HData data)
{								//마지막 인덱스에 data추가후 부모 노드와 비교하여 자리 정하기
	int idx = ph->numOfData+1;

	while(idx != 1)
	{
	//	if(pr < (ph->heapArr[GetParentIDX(idx)].pr))
		if(ph->comp(data, ph->heapArr[GetParentIDX(idx)]) > 0)
		{
			ph->heapArr[idx] = ph->heapArr[GetParentIDX(idx)];
			idx = GetParentIDX(idx);
		}
		else
		{
			break;
		}
	}
	
	ph->heapArr[idx] = data;
	ph->numOfData += 1;
}

HData HDelete(Heap * ph)
{		//루트노드 제거 후, 마지막 노드를 부모노드와 비교하며 위치 재정의한다.
	HData retData = ph->heapArr[1];
	HData lastElem = ph->heapArr[ph->numOfData];

	int parentIdx = 1;
	int childIdx;

	while(childIdx = GetHiPriChildIDX(ph, parentIdx))
	{
	//	if(lastElem.pr <= ph->heapArr[childIdx].pr)
		if(ph->comp(lastElem, ph->heapArr[childIdx]) >= 0)
			break;

		ph->heapArr[parentIdx] = ph->heapArr[childIdx];
		parentIdx = childIdx;
	}

	ph->heapArr[parentIdx] = lastElem;
	ph->numOfData -= 1;
	return retData;
}

- 힙의 데이터 저장(HInsert) 시간 복잡도 = O(log2(n))
- 힙의 데이터 삭제(HDelete) 시간 복잡도 = O(log2(n))
- 정렬 원소 갯수 = n

- 힙의 시간 복잡도 = O(n* log2(n))

---

<병합 정렬>

'해결이 용이한 단계'까지 문제를 '분할'한다.
'해결이 용이한 수준'까지 문제를 '해결'한다.
해결한 결과를 '결합'한다.

'해결이 용이한 단계' = 원소 한개 단위

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);	<< 재귀적

		MergeTwoArea(arr, left, mid, right);	<< 병합// 분할이 완료되면 병합
	}
}

void MergeTwoArea(int arr[], int left, int mid, int right)
{
	int fIdx = left;
	int rIdx = mid+1;
	int i ;
	
	int * sortArr = (int*)malloc(sizeof(int) * (right+1));
	int sIdx = left;

	while(fIdx <= mid && rIdx <= right)
	{
		if(arr[fIdx] <= arr[rIdx])		<< 분할된 두개 배열 비교
			sortArr[sIdx] = arr[fIdx++];	<< 작은 값을 먼저 sortArr에 넣기
		else
			sortArr[sIdx] = arr[rIdx++];

		sIdx++;
	}

	if(fIdx > mid)		<< 왼쪽 배열이 더 우선이여서 sortArr에 다 들어갔음
	{			<< 남은 오른쪽 배열을 sortArr에 넣어줘야함
		for(i = rIdx; i <= right; i++ sIdx++)
			sortArr[sIdx] = arr[i];
	}
	else			<< 오른쪽 배열이 더 우선이여서 sortArr에 다 들어갔음
	{			<< 남은 왼쪽 배열을 sortArr에 넣어줘야함
		for(i = fIdx; i <= mid; i++, sIdx++)
			sortArr[sIdx] = arr[i];
	}

	for(i = left; i <= right; i++)		<<sortArr에 정렬했던 배열을
		arr[i] = sortArr[i];		<<다시 arr에 넣어줌

	free(sortArr);
}

- '비교 횟수' 최대 N번 발생
- 총 병합하는데 필요한 단계 log2(n)
- 병합 정렬에서 필요한 분할 및 병합 O(n * log2(n))
- 임시메모리가 필요하다는 단점 존재

---

<퀵 정렬>

배열을 pivot을 기준으로 'pivot'보다 '우선인 배열'과 '우선이지 않은 배열'로 나눈다.
'우선인 배열'과 '우선이지 않은 배열' 두 개의 배열도 재귀적으로 나누어준다.

예시 : low는 pivot에서 출발해서 pivot보다 우선이지않은 값을 찾으면 멈추고
       high는 pivot 반대쪽에서 출발해서 pivot보다 우선인 값을 찾으면 멈춘다.
-----------------------------------------------
pivot : 5

5 1 3 7 9 2 4 6 8

low : 7, high : 4
-----------------
5 1 3 4 9 2 7 6 8

low : 9, high : 2
-----------------
5 1 3 4 2 9 7 6 8         => 여기서 low와 high가 교차한다. 이 때,교차하기 전 low와 pivot과 바꾼다.
-----------------
2 1 3 4 ) 5 ( 9 7 6 8
------------------------
pivot : 2

2 1 3 4                         => 여기서 low:1 high:3에서 교차한다. 교차하기전 low의 값과 pivot을 바꾼다.

1) 2 ( 3 4
------------------------
pivot : 9

9 7 6 8

low : 7, high : 8
low : 6, high : 8
low : 8, high : 8

8 7 6 ) 9
------------------------

pivot : 8

8 7 6

low : 7, high : 6
low : 8, high : 6

6 7 ) 8
----------------------------------------
1 2 3 4 5 6 7 8 9 완성

int Partition(int arr[], int left, int right)
{
	int pivot = arr[left];		<< pivot을 가장 왼쪽, 즉 left값을 pivot 선정
	int low = left + 1;		<< low는 left+1부터
	int high = right;		<< high는 맨 오른쪽부터

	while(low <= high)		<< low와 high가 교차되지않았다면 진행해라
	{
		while(pivot >= arr[low]
			&& low <= right)<< pivot 보다 큰값 찾을때까지 즉, 우선이지 않은 값
			low++;		<< 이동해라

		while(pivot <= arr[high]
		&& high >= (left+1))	<< pivot 보다 작은값 찾을때까지 즉, 우선인 값
			high--;		<< 이동해라

		if(low <= high)		<< 교차되지 않았다면
			swap(arr,low,high);	<< 두개 값을 바꾸자
	}

	Swap(arr,left,high);		<< pivot값과 high값을 바꾸자
	return high;			<< pivot의 위치
}

void QuickSort(int arr[], int left, int right)
{
	if(left <= right)
	{
		int pivot = Partition(arr,left,right);
		QuickSort(arr,left,pivot-1);	<< pivot보다 우선인 수 정렬
		QuickSort(arr,pivot+1,right);	<< pivot보다 우선이지 않은 수 정렬
	}
}

- 최선의 경우 O(n * log2(n))
- 최악의 경우 O(n^2)

- 중간의 가까운 피벗을 선택하는 방법 으로써 평균적으로 최선의 경우의 성능을 보인다.
- 또한, 최선의 경우임에도 다른 알고리즘 보다 빠르다
- 왜냐하면, 퀵 정렬은 데이터 이동횟수가 상대적으로 적기 때문이다.
- 또한, 추가적인 메모리 사용이 없다.

---

<기수 정렬>

정렬 순서를 비교하는 비교연산을 하지 않는다.
다른 정렬보다 성능면에서 월등하다.
기수 정렬을 적용할 수 있는 범위가 제한적이다.

기수란 주어진 데이터를 구성하는 기본 요소를 뜻한다.
예를들어, 2진수는 0과 1의 조합으로 데이터를 표현하니 2진수의 기수는 0과 1이다.

LSD 기수 정렬 : 일의 자리부터 십의 자리 ... 기수 정렬 하는 것
MSD 기수 정렬 : LSD 기수 정렬의 반대 방향으로 정렬 하는 것

기수 정렬을 일의 자리부터 시작하면 그 다음 십의 자리에서 기수 정렬을 진행하게 되면 일의 자리는 신경써주지 않아도 된다.
하지만 MSD 기수 정렬을 하게 되면 십의 자리에서 기수 정렬을 진행하고 나면 백의 자리에서 기수 정렬을 진행한게 남아있지 않아 순서가 고정적이지 않다.

하지만, MSD는 기수 정렬을 진행하면서 나누어서 기수 정렬을 진행하면 된다.
또, 중간에 정렬이 완료될 수도 있기 때문에 끝까지 정렬을 진행하지 않아도 된다.

void RadixSort(int arr[], int num, int maxLen)
{
	Queue buckets[BUCKET_NUM];
	int bi;
	int pos;
	int di;
	int divfac = 1;
	int radix;

	for(bi = 0; bi < BUCKET_NUM; bi++)
		QueueInit(&buckets[bi]);	<< 버킷 초기화

	for(pos = 0; pos<maxLen; pos++)
	{	<< 가장 긴 데이터 길이만큼 반복
		for(di = 0; di < num; di ++)
		{	<< 정렬대상의 수 만큼 반복
			radix = (arr[di]/divfac) % 10;		<< 자릿수 값 		
			Enqueue(&buckets[radix],arr[di]);	<< 버킷에 arr[di]값 넣기
		}

		for(bi = 0; di = 0; bi<BUCKET_NUM; bi++)
		{
			while(!QIsEmpty(&buckets[bi]))		<< bucket이 저장되어있으면 진행
				arr[di++] = Dequeue(&buckets[bi]);	<< bucket에 데이터가 있으면 꺼내서 arr에 넣기
		}

		divfac *= 10;
	}
}

비교연산이 없기 때문에 데이터'삽입'과 '추출'이 성능의 핵심이다.
O(maxLen * n) = O(n)