Sort - (2) Quick, Heap Sort

• Quick Sort
  • 배열을 부분 집합을 나눈 후, 특정 키 값 (pivot)을 정해서 피봇보다 작은 값은 피봇의 왼쪽 집합으로, 큰 값은 오른쪽 집합으로 교환하며 정렬해가는 방식

  void QuickSort(int arr[], int begin, int end) {
      if(begin >= end) return;
      
      int pivot = (begin + end) / 2;
      
      int left = begin, right = end;
      while(left <= right) {
          while(arr[left] < arr[pivot]) left++;
          while(arr[right] > arr[pivot]) right--;
          if(left <= right){
              swap(&arr[left], &arr[right]);
              left++; right--;
          }
      }
      quickSort(arr, begin, right);
      quickSort(arr, left, end);
  }
  

• Heap Sort
  • 최대 힙 트리나 최소 힙 트리를 이용해 정렬하는 방식

  class Heap {
  private:
     int *arr;
     int count;
  
  public:
      Heap(int sz) {
        count = 0;
        arr = new int[sz+1];
        arr[0] = 0;
     }
  
     void insert(int value) {
        int pos;
        for(pos = ++count; pos/2 > 0 && arr[pos/2] > value; pos /= 2)
           arr[pos] = arr[pos/2];
        arr[pos] = value;
     }
  
     void print() {
        while(count > 0) 
           cout << deleteItem() << " ";
  
     }
  
     int deleteItem() {
        int item = arr[1];
        int temp = arr[count--];
        int parent = 1;
        int child = 2;
  
        while(child <= count) {
           if(child < count && arr[child] > arr[child+1]) child++;
           if(temp < arr[child]) break;
  
           arr[parent] = arr[child];
           parent = child;
           child *= 2;
        }
  
        arr[parent] = temp;
        return item;
     }
  
  };
  
  void sort(int arr[], int length) {
     Heap *heap = new Heap(length);
  
     for(int i = 0; i<length;i++)
        heap->insert(arr[i]);
  
     heap->print();
  }