카테고리 없음

병합 정렬

OKOK 2017. 8. 12. 19:01

 


분할 정복이라는 알고리즘 디자인 기법에 근거하여 만들어진 정렬 방법입니다. 분할 정복이란, 말 그대로 복잡한 문제를 복잡하지 않은 문제로 분할하여 정복하는 방법입니다. 단 분할해서 정복했으니 정복한 후에는 결합의 과정을 거쳐야 합니다. 해결이 용이한 단계까지 문제를 분할해 나갑니다. 해결이 용이한 수준까지 분할된 문제를 해결합니다. 분할해서 해결한 결과를 결합하여 마무리 합니다. 8개의 데이터를 동시에 정렬하는 것보다, 이를 둘로 나눠서 4개의 데이터를 정렬하는 것이 쉽고, 또 이들 각각을 다시 한번 둘로 나눠서 2개의 데이터를 정렬하는 것이 더 쉽다. 


오름차순 정렬을 기준으로 병합 정렬으 기본 원리를 설명하고 있습니다. 8개의 데이터를 둘로 나눈 것이 전부이지만, 실제로는 훨씬 더 작게 분할을 해야 합니다. 2개의 데이터만 남을 때까지 분할을 하면,  if문 하나로 간단히 정렬할 수 있을 테니말입니다. 병합 정렬은 데이터가 1개만 남을 떄까지 분할을 해나갑니다. 데이터가 2개만 남아도 정렬을 할 필요가 있지만, 데이터가 1개만 남으면 그 조차 불필요해지기 때문입니다. 


전체 데이터를 둘로 나누는 과정을, 데이터가 하나씩 구분이 될 떄까지 진행을 합니다. 총 8개의 데이터가 존재하므로 둘로 나누는 과정을 데이터가 하나씩 구분이 될 때까지 진행을 합니다. 재귀적 구현을 위한 것입니다. 첫 번째 인자로 정렬대상이 담긴 배열의 주소 값을 전달하고, 두 번째 인자와 세 번째 인자로 정렬대상의 범위정보를 인덱스 값의 형태로 전달합니다. 정렬대상이 배열 전체라면 배열의 첫 번째 요소와 마지막 요소의 인덱스 값을 두 번째 인자와 세 번째 인자로 각각 전달합니다. 이전에 소개한 정렬 함수들과는 원형의 선언 형태에서 좀 차이가 납니다. 


#include <stdio.h>

#include <stdlib.h>


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++];

else

 sortArr[sIdx] = arr[rIdx++];

sIdx++;

}


if(fIdx > mid)

{

for(i=rIdx; i<=right; i++, sIdx++)

   sortArr[sIdx] = arr[i];

}

else

{

for(i=fIdx; i<=mid; i++, sIdx++)

   sortArr[sIdx] = arr[i];

}


for(i=left; i<=right; i++)

arr[i] = sortArr[i];

free(sortArr);

}


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);

        }

}


int main(void)

{

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

int i;


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

for(i=0; i<7; i++)

printf("%d ", arr[i]);

printf("\n");

return 0;

}



병합 정렬 성능 평가

병합 정렬의 성능 평가를 위해서, 비교연산의 횟수와 이동연산의 대입연산의 횟수를 계산해 보겠습니다. 정렬의 대상인 데이터의 수가 n개 일 떄, 각 병합의 단계마다 최대 n번의 비교연산이 진행됩니다. 따라서 데이터의 수가 n개 일 때, 병합 정렬에서 진행되는 최대 비교연산의 횟수는 다음과 같습니다. 


임시 배열에 데이터를 병합하는 과정에서 한 번, 임시 배열에 저장된 데이터 전부를 원위치로 옮기는 과정에서 한 번, 참고로 병합 정렬에는 임시 메모리가 필요하다는 단점이 있습니다. 하지만 이는 정렬의 대상이 배열이 아닌 연결 리스트일 경우 단점이 되지 않기 떄문에, 연결 리스트의 경우에는 병합 정렬에서 그만큼 더 좋은 성능을 기대할 수 있습니다.


퀵 정렬

#include <stdio.h>


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];

int low = left+1;

int high = right;


while(low <= high)

{

while(pivot>arr[low])

low++;

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);

}

}


int main(void)

{

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

int len = sizeof(arr)/sizeof(int);

int i;

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

for(i=0; i<len; i++)

printf("%d ", arr[i]);

printf("\n");

return 0;

} 


피벗의 선택에 대해서 논의해봅니다. 가장 왼쪽에 위치한 데이터를 피벗으로 결정하였는데, 실은 전테 데이터를 기준으로 중간에 해당하는 값을 피벗으로 결정할 때 좋은 성능을 보입니다. 피벗이 중간에 해당하는 값일 경우, 정렬대상은 균등하게 나뉩니다. 정렬대상에서 세 개의 데이터를 추출합니다. 그리고 그 중에서 중간 값에 해당하는 것을 피벗으로 선택합니다. 단순히 생각해도 이 방법을 사용하면 중간에 가까운 값을 선택할 확률이 높아짐을 알 수 있습니다.  


퀵 정렬 성능 평가

최선의 경우에 대한 빅오입니다. 최악의 경우에 대한 빅오를 구해야 하는 것 아닌가요. 중간에 가까운 피벗을 선택하는 방법을 적용함으로써, 늘 최선의 경우를 보이는 것은 아니지만 최선의 겨웅에 가까운 성능을 평균적으로 보이기 때문입니다. 


기수 정렬 이해1

기수 정렬은 정렬순서상 앞서고 뒤섬의 판다을 위한 비교연산을 하지 않습니다. 비교 연산은 정렬 알고리즘의 핵심이라 할 수 있습니다. 


#include <stdio.h>

#include "ListBaseQueue.h"


#define BUCKET_NUM 10


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]);

}


for(bi=0, di=0; bi<BUCKET_NUM; bi++)

{

while(!QIsEmpty(&buckets[bi]))

arr[di++] = Dequeue(&buckets[bi]);

}

divfac *= 10;

}

}


int main(void)

{

int arr[7] = {13, 212, 14, 7141, 10987, 6, 15};

int len = sizeof(arr) / sizeof(int);

int i;


RadixSort(arr, len, 5);

for(i=0; i<len; i++)

printf("%d ", arr[i];

printf("\n");

return 0;

} 



저작자표시 (새창열림)