정렬알고리즘 정리

** SWAP(i, j);는 i, j 가 다를 경우 swap하는 함수 /////////////////////////////////////////////////// // 버블정렬 // 두값을 비교하여 큰 데이터를 뒤로 보내는 정렬 // O(n²) = n(n-1)/2 // 장점: 단순한 코드, 정렬완료시 즉시종료가능 // 단점: 역순정렬상태에서 SWAP이 많이 발생 /////////////////////////////////////////////////// void BubbleSort(keytype arr[]) {     int i=0, j=0;     for (i=1; i<arr.length; i++)     {         for (j=0; j<arr.length-i; j++)         {             if (arr[j+1] < arr[j])             {                 SWAP(j, j+1);             }         }     } } /////////////////////////////////////////////////// // 선택정렬 // 가장 작은 값을 찾아 앞으로 보내는 정렬 // O(n²) = n(n-1)/2 // 장점: SWAP이 적음 // 단점: 데이터의 순서가 바뀌는 불안정 정렬 /////////////////////////////////////////////////// void SelectionSort(keytype arr[]) {     int i=0, j=0, nMinIdx=0;     keytype minimum=0;     for (i=0; i<arr.length-1; i++)     {         minimum = arr[i];         nMinIdx = i;         for (j=i+1; j<arr.length; j++)         {             if (arr[j] < minimum)             {                 nMinIdx = j;                 minimum = arr[j];             }         }         SWAP(i, nMinIdx);     } } /////////////////////////////////////////////////// // 삽입정렬 // 앞의 값들을 확인하여 적절한 위치에 삽입하는 정렬 // O(n²) = n(n-1)/2 // 장점: 정렬완료시 즉시종료가능 // 단점: 삽입위치가 먼 경우 비효율 /////////////////////////////////////////////////// void InsertionSort(keytype arr[]) {     int i=0, j=0;     keytype data=0;     for (i=1; i<arr.length; i++)     {         data = arr[i];         j = i - 1;         while (data < arr[j])         {             arr[j+1] = arr[j];             if (0 == j--)             {                 break;             }         }         arr[j+1] = data;     } } /////////////////////////////////////////////////// // 빠른정렬 // 기준값을 기준으로 작은 값은 앞 큰값은 뒤로 정렬 // 평균 O(nlog₂n), 최악 O(n²) // 장점: 평균적으로 빠르다 // 단점: 정렬된 데이터에 대해 성능이 떨어진다 //                -> 중간값을 피봇값으로 사용 /////////////////////////////////////////////////// void QuickSort(keytype arr[], int nLeft, int nRight) {     if (nLeft < nRight)     {         if (1 == (nRight - nLeft))         {             if (arr[nRight] < arr[nLeft])             {                 SWAP(nLeft, nRight);             }             return;         }         else         {             int nLow=nLeft, nHigh=nRight+1;             keytype pivot=arr[left];             do             {                 do                 {                     nLow++;                 } while(arr[nLow] < pivot);                                  do                 {                     nHigh--;                 } while(pivot < arr[nHigh]);                 if (nLow < nHigh)                 {                     SWAP(nLow, nHigh);                 }             } while(nLow < nHigh);             SWAP(nLeft, nHigh);             QuickSort(arr, nLeft, nHigh-1);             QuickSort(arr, nHigh+1, nRight);         }     } } /////////////////////////////////////////////////// // 합병정렬 // 기준값을 기준으로 작은 값은 앞 큰값은 뒤로 정렬 // 평균 O(nlog₂n) // 장점: 수행시간이 동일 // 단점: 비제자리 정렬 (추가공간복잡도) /////////////////////////////////////////////////// void MergeSortRun(keytype arr[]) {     if (1 < arr.length)     {         keytype arr_copy[arr.length];         mergeSort(arr, 0, arr.length-1);     } } void MergeSort(keytype arr[], int nLeft, int nRight) {     if (1 < (nRight - nLeft))     {         int nMiddle = (nLeft + nRight) / 2;         MergeSort(arr, nLeft, nMiddle);         MergeSort(arr, nMiddle +1, nRight);         Merge(arr, nLeft, nMiddle, nRight);     } } void Merge(keytype arr[], int nLeft, int nMiddle, int nRight) {     int nIdx=0, nLow=nLeft, nHigh=nMiddle+1;     for (nIdx=nLeft; nIdx<=nRight; nIdx++)     {         arr_copy[nIdx] = arr[nIdx];     }     for (nIdx=nLeft; nIdx<=nRight; nIdx++)     {         if (arr_copy[nLow] < arr_copy[nHigh])         {             arr[nIdx] = arr_copy[nLow++];         }         else         {             arr[nIdx] = arr_copy[nHigh++];         }     } }