Sorting 손풀기 연습

sort.cc

#include <iostream>
using namespace std;

int* testCaseGenerator(int n) {
    int* result = new int[n];

    for(int i = 0; i < n; ++i) {
        result[i] = std::rand() % 99;
    }
    
    return result;
}


void printArray(int arr[], int n) {
    for(int i = 0; i < n; ++i) {
        std::cout << arr[i] << " ";
    }

    std::cout << std::endl;
}


bool checkSorted(int arr[], int n) {

    for(int i = 0; i < n - 1; ++i) {

        if (arr[i] > arr[i + 1]) {
            return false;
        }
    }

    return true;
}

void swap(int arr[], int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

void selectionSort(int arr[], int size) {
    int selection;

    for(int i = 0; i < size - 1; ++i) {

        // selection -> min
        selection = i;

        for (int j = i + 1; j < size; ++j) {

            if (arr[selection] > arr[j]) {
                selection = j;
            }

        }

        swap(arr, i, selection);
    }
}

void bubbleSort(int arr[], int size) {
    bool is_swapped = false;
    for(int i = 0; i < size; ++i) {
        for (int j = 0; j < size - 1; ++j) {
            if(arr[j] <= arr[j + 1])
                continue;
            else {
                swap(arr, j, j + 1);
                is_swapped = true;
            }
        }

        if (!is_swapped)
            break;
    }
}

void insertionSort(int array[], int size) {
  for (int i = 1; i < size; ++i) {
    int j = i - 1;
    int temp = array[i];
    
    while(j >= 0 && array[j] > temp) {
      array[j + 1] = array[j];
      --j;
    }
    array[j + 1] = temp;
  }
}

void merge(int array[], int left, int m, int right) {
  int size = right - left + 1;
  int* temp = new int[size];
  
  int i = left;
  int j = m + 1;
  int k = 0;
  
  while(i <= m && j <= right) {
    if (array[i] <= array[j]) {
      temp[k++] = array[i++];
    } else {
      temp[k++] = array[j++];
    }
  }
  
  while(i <= m) {
    temp[k++] = array[i++];
  }
  
  while(j <= right) {
    temp[k++] = array[j++];
  }
  
  k--;
  while(k >= 0) {
    array[left + k] = temp[k];
    k--;
  }
  
  delete[] temp;
}

void mergePartition(int array[], int left, int right) {
  if (left < right) {
    int m = (left + right) / 2;
    
    mergePartition(array, left, m);
    mergePartition(array, m + 1, right);
    merge(array, left, m, right);
  }
}

void mergeSort(int array[], int size) {
  mergePartition(array, 0, size - 1);
}

void testRun(int N, void (*f)(int arr[], int size)) {
  int* temp = new int[N];
  temp = testCaseGenerator(N);
  
  cout << "Given: " << endl;
  printArray(temp, N);
  
  f(temp, N);
  if (checkSorted(temp, N)) {
    cout << "Success" << endl;
  } else {
    cout << "Fail" << endl;
  }
  printArray(temp, N);
  cout << endl;
  
  delete[] temp;
}

int getPivot(int arr[], int left, int right) {
  int pivot = arr[right];
  int i = left;
  int j = right - 1;
  
  while(i < j) {
    while(arr[i] <= pivot && i < right) {
      //good
      ++i;
    }
    while(arr[j] > pivot && j > 0) {
      //good
      --j;
    }
    
    if (i < j) {
      swap(arr, i, j);
      ++i;
      --j;
    }
  }
  if (arr[i] > arr[right]){
    swap(arr, i, right);  
  }
  

  return i;
}

void quickPartition(int arr[], int left, int right) {
  int i = left;
  int j = right;
  
  int pivot = arr[(left + right) / 2];
  
  while (i <= j) {
    while (arr[i] < pivot) {
      ++i;
    }
    
    while (pivot < arr[j]) {
      --j;
    }
    
    if (i <= j) {
      swap(arr, i, j);
      ++i;
      --j;
    }
  }
  
  if (left < j) {
    quickPartition(arr, left, j);
  }
  
  if (i < right) {
    quickPartition(arr, i, right);
  }
  
}

void quickSort(int arr[], int size) {
  quickPartition(arr, 0, size - 1);
}


int main() {
  int N = 555;
  
  testRun(N, selectionSort);
  testRun(N, bubbleSort);
  testRun(N, insertionSort);
  testRun(N, mergeSort);
  testRun(N, quickSort);

}