Sort - (3) Merge, Radix Sort

• Merge Sort
  • 여러 부분 집합으로 분할하고, 정렬한 후, 병합하는 방식
  • 종류
    • 2-way: 2개의 정렬된 자료 집합을 하나의 집합으로 병합
    • n-way: n개의 정렬된 자료 집합을 하나의 집합으로 병합

  void merge(int arr[], int begin, int middle, int end) {
     int *sorted = new int[end - begin + 1];
  
     int i = 0;
     int left = begin;
     int right = middle + 1;
     while(left <= middle && right <= end) {
        if(arr[left] < arr[right]) sorted[i++] = arr[left++];
        else sorted[i++] = arr[right++];
     }
  
     while(left <= middle)
        sorted[i++] = arr[left++];
     while(right <= end)
        sorted[i++] = arr[right++];      
     for(i = 0; i <= end - begin; i++)
        arr[begin + i] = sorted[i];
     delete sorted;
  }
  
  void sort(int arr[], int begin, int end) {
     if (end <= begin) return;
  
     int middle = (begin + end)/2;
     sort(arr, begin, middle);
     sort(arr, middle + 1, end);
  
     merge(arr, begin, middle, end);
  
  }
  

• RadixSort
  • 원소의 키 값을 나타내는 인덱스를 이용한 정렬 방법. 정렬할 원소의 키 값에 해당하는 bucket에 원소를 분배하였다가 버킷의 순서대로 원소를 꺼내는 방법

  class RadixSort {
  private:
      int length;
      vector<vector<int>> counter;
  
  public:
      RadixSort(int size) {
          length = size;
          counter.resize(10);
      }
  
     void sort(int arr[]) {
        int max = 0;
        for(int i = 0; i < length; i++)
           if(max < arr[i]) max = arr[i];
        string maxstr = max+"";
        int max_digit = maxstr.length();
        sort(arr, max_digit);
     }
  
     void sort(int arr[], int max_digit) {
         int mod = 10, div = 1;
  
         for(int i = 0; i < max_digit; i++, div *= 10, mod *= 10) {
             for(int j = 0; j < length; j++) {
                 int bucket = arr[j] % mod / div;
                 counter[bucket].push_back(arr[j]);
             }
             int pos = 0;
             for(vector<int> elem : counter){
                 for(int value : elem) arr[pos++] = value;
             }
         }
     }
  
  };