병합정렬
아이디어
merge 우리 말로 융합이라는 의미이다.
쪼갠 후 병합하는 것(diveide and conquer)이 기본적인 아이디어이다.
어떤 배열을 1개가 될때까지 쪼개고 융합해서 정렬을 완성하는 것이다.
누구는 의문을 가질 것이다.
아니 쪼개고 합하는데 어떻게 정렬이 되느냐하고.
여기서 포인트는 정렬이 되도록 융합하는 것이다.
어떤 배열을 정렬할 때 두 개의 정렬된 subset을 합해서 정렬하는 것이 훨씬 더 쉽다라는 것에서 착안된 아이디어이다.
구현
추상적 설명
어떤 배열이 주어진다.
해당 배열을 반으로 나눈다.
1개의 element가 남을 때까지 반으로 나눈다.
그리고 그 element들이 정렬이 되도록 두 개씩 병합한다.
그리고 병합된 것들 두 개씩 다시 병합한다.
이를 반복하여 최종적으로 배열의 정렬이 완성된다.
구현
- 배열의 정렬이 목적이다. 헌데 그 최종 정렬이 작은 스케일의 정렬에 의존한다.
즉, 재귀적인 문제이다.
- 반환형: call by ref이기 때문에 반환받을 필요 없다.
- 재귀 호출부: 두 파트로 나누고 정렬된 결과를 보내라고 시킨다.
즉, 함수를 두번 호출하고 배열의 시작과 끝 index를 전달해주면 된다.
- 종결조건: 시작과 끝 index가 같다면 한 개의 데이터로 쪼갠 것이므로 아무것도 하지 않고 끝낸다.
void MergeSort(int arr[], int left, int right)
{
if(left >= right)
return;//종결조건
int mid;
mid = (left + right)/2;
MergeSort(arr, left, mid);//left부터 mid까지 정렬하라는 의미이다.
MergeSort(arr, mid+1, right);
MergeTwoArea(arr, left, mid, right);//두 정렬된 subArray를 병합해서 정렬시켜라
}- 정렬된 배열의 병합
기본적인 아이디어는 '한 배열의 최소값은 두 부분배열의 최소값끼리만 비교하면 된다'이다.
두 subArray의 최소값(가장 작은 인덱스) 중 더 작은 값을 임시 메모리(나중에 Array에 복사할 것)에 저장한다.
그리고 해당 subArray의 최소값의 인덱스는 1 증가한다.
그리고 위의 비교 후 저장을 반복한다.
한 subArray의 idx를 가리키는 변수가 해당 subArray의 경계를 넘어가면 다른 subArray를 idx 순서대로 저장한다.
void MergeTwoArea(int arr[], int left, int mid, int right)
{
//각 파트의 최소 데이터의 인덱스
int leftIdx = left;
int rightIdx = mid+1;
//임시 배열의 데이터가 들어갈 인덱스
int saveIdx = left;
//임시 배열 동적 할당
int * tempArr = (int *)malloc(sizeof(int)*(right+1));
//두 subArray 중 어떤 것도 모든 데이터를 넘겨주지 않았을 때
while(leftIdx <= mid && rightIdx <= right)
{
//비교를 해서 더 작은 값을 임시 메모리에 넣어라
if(arr[leftIdx] < arr[rightIdx])
tempArr[saveIdx++] = arr[leftIdx++];
else
tempArr[saveIdx++] = arr[rightIdx++];
}
if(leftIdx > mid)
for(; rightIdx <= right;)
tempArr[saveIdx++] = arr[rightIdx++];
if(rightIdx > right)
for(; leftIdx <= mid;)
tempArr[saveIdx++] = arr[leftIdx++];
//임시 메모리의 값 배열로 복사
int i;
for(i=left; i<=right; i++)
arr[i] = tempArr[i];
free(tempArr);
return;
}성능
지배적인 연산 판단
해당 알고리즘의 지배적인 부분은 MergeTwoArea의 실행에서 결정됨을 알 수 있다.
그리고 MergeTwoArea에서 연산량을 결정하는 것은 대입연산 혹은 비교연산이 된다.
계산
대입 연산의 경우, 최선의 경우나 최악의 경우나 차이 없이 모든 데이터가 임시 메모리에 대입되어야하고 임시 메모리에 있는 데이터가 통으로 원래의 배열로 대입되어야 한다.
그리고 이는 데이터의 수의 상수배에 해당함을 알 수 있다.
총 데이터의 수가 n개일 때, 이진 트리 구조를 하고 있는 MergeTwoArea 함수는 log_2_n의 level을 가진다.
그리고 대입은 각 레벨마다 2n의 scale을 가지므로 O(nlog_2_n)이 됨을 알 수 있다.
퀵정렬
아이디어
어떤 기준값이 있을 때, 그보다 작은 값은 왼쪽에 큰 값은 오른쪽에 나누어 위치시킨다.
그리고는 다시 작은 값들에 대해 기준값을 정한 후 그 기준값보다 작은 값들은 왼쪽에 큰 값들은 오른쪽에 위치시킨다.
이 분류를 반복하면 결국 최종적으로 정렬을 이룰 수 있을 것이다.
구현
추상적 설명
어떤 배열이 주어진다.
그 배열에 기준값을 정한다.
가장 왼쪽에 있는 값부터 기준값보다 작은지 판별하고 작으면 다음 idx로 증가한다. 크면 증가하지 않고 유지한다.
가장 오른쪽에 있는 값부터 기준값보다 큰지 판별하고 크면 다음 idx로 감소한다. 작으면 감소하지 않고 유지한다.
그리고 해당 idx의 값을 swap한다.
이 행위를 반복 후 증가하는 idx가 감소하는 idx를 넘기면 기준값을 가운데에 위치시킨다.
이 행위를 반복한다.
구현
- 기준값에 대한 좌우 정렬 후 왼쪽 부분을 재정렬, 우측 부분 재정렬한다.
재귀적이다.
- 반환형: call by ref이므로 반환하지 않는다.
- 재귀 호출부: 기준 idx보다 작은 idx를 보내서 호출하고 큰 idx를 보내서 총 두번 호출한다.
- 종결 조건: element가 한 개 남았을 때 종결하도록 했다.
우리는 idx를 매개변수로 넘겨주니까 양쪽 idx가 같으면 종결하도록 구성하면 된다.
void QuickSort(int arr[], int left, int right)
{
if(left >= right)
return;
...
QuickSort(arr, left, high-1);
QuickSort(arr, high+1, right);
return;
} - 나머지 부분
//pivot을 가장 왼쪽에 있는 원소로 정함
int pivot = left;
int low = left+1;
int high = right;
while(1)
{
while(arr[low] <= arr[pivot] && low <= right)
//경계를 정해주지 않으면 배열의 범위를 넘어서도 계속 증가한다.
//pivot값과 같을때 증가하지 않으면 무한 루프를 타게 된다.
low++;
while(arr[high] >= arr[pivot] && high >= pivot+1)
//이 조건의 경계조건에서 구현 실수를 했다.
//high는 결코 pivot보다 작아지면 안된다.
//그래서 나는 high>=pivot의 조건을 달았는데
//그렇게 하면 high--를 실행하게 되고
//pivot과 high를 swap할 때 잘못된다.
//즉, 루프타고 나오면 high는 pivot-1이 됨.
high--;
if(low <= high)
{
Swap(arr, low, high);
}
else
break;
}
Swap(arr, pivot, high);성능
퀵정렬을 생각해보면 하나의 pivot 값이 정해지면 해당 pivot 값과 subArray의 값들과 비교한다. low>high일 때까지.
즉, 해당 subArray의 모든 값을 pivot값과 비교한다는 말이다.
위의 병합정렬과 같다.
단 이때 병합정렬과의 차이점은 레벨의 깊이가 다를 수 있다는 것이다.
만일 pivot 값이 딱 중간값이라면 작은 값과 큰 값이 반반으로 나눠질 것이고 총 깊이는 log_2_n일 것이다.
헌데 pivot이 항상 최소값으로 정해지면 작은 값은 0개 큰 값은 n-1이 되어 최종적으로 1개의 원소를 정렬하기까지의 깊이가 n의 scale이 된다.
즉, 이상적으로 pivot이 중간값이라면 nlog_2_n이 되고 pivot이 항상 최소값이라면 n^2의 big-O를 가지게 된다.
