Data Structure - Sort

main.cpp

#include <iostream>
#include <stdlib.h>
using namespace std;

#define RAND_MAX_CAPACITY 100
#define LIST_SIZE 8

inline int getRandNumber() { return (rand() % RAND_MAX_CAPACITY) + 1; }

class List {
 private:
  int* datas;
  int size;
  int capacity;

  void generateNumber() {
    for (int i = 0; i < size; i++) {
      int randNumber = getRandNumber();
      if (!isExist(randNumber))
        append(randNumber);
      else
        append(getRandNumber());
    }
  }

 public:
  List(int size, bool autoGenerated = false) {
    this->datas = new int[size];
    this->size = size;
    this->capacity = 0;

    if (autoGenerated) {
      generateNumber();
    }
  }

  void append(int data) { datas[capacity++] = data; }

  bool isExist(int data) {
    for (int i = 0; i < size; i++) {
      if (datas[i] == data) return true;
    }
    return false;
  }

  const int* getDatas() { return datas; }

  int getCapacity() { return capacity; }

  ~List() { delete[] datas; }

  /*
        버블 정렬
*/
  void bubble_sort() {
    for (int i = 0; i < capacity - 1; i++) {
      for (int j = capacity - 1; j > i; j--) {
        if (datas[j - 1] > datas[j]) swap(datas[j - 1], datas[j]);
      }
    }
  }

  /*
        삽입 정렬
*/
  void insert(int data, int size, int* otherDatas) {
    bool isInserted = false;
    for (int i = 0; i < size; i++) {
      if (otherDatas[i] >= data) {
        for (int j = size - 1; j >= i; j--) otherDatas[j] = otherDatas[j - 1];
        otherDatas[i] = data;
        isInserted = true;
        break;
      }
    }
    if (!isInserted) {
      for (int i = 0; i < size; i++) {
        if (otherDatas[i] == -1) {
          otherDatas[i] = data;
          break;
        }
      }
    }
  }

  void insertion_sort() {
    int* otherDatas = new int[size];

    // 부분배열 초기화
    // (0번째를 제외하고 모든 내용을 -1으로 초기화,
    //  0번째에는 현재 리스트의 첫번째 값을 대입)
    otherDatas[0] = datas[0];
    for (int i = 1; i < size; i++) {
      otherDatas[i] = -1;
    }

    for (int i = 1; i < size; i++) {
      insert(datas[i], size, otherDatas);
    }

    // 현재 리스트에 다른 데이터 값을 복사
    for (int i = 0; i < size; i++) datas[i] = otherDatas[i];
    delete[] otherDatas;
  }

  /*
        선택 정렬
*/
  void selection_sort() {
    for (int i = 0; i < size - 1; i++) {
      int min_index = select_min(i, size - 1);
      swap(datas[i], datas[min_index]);
    }
  }

  int select_min(int start, int end) {
    // start부터, end까지의 최소값을 찾아 최소값의 위치를 반환
    int min_index = start;
    for (int i = start + 1; i <= end; i++) {
      if (datas[i] < datas[min_index]) {
        min_index = i;
      }
    }
    return min_index;
  }

  void merge_sort() { merge_sort(0, size - 1, datas); }

  /*
        합병 정렬
*/
  void merge_sort(int start, int end, int* datas) {
    // 리스트의 원소가 한개인 경우
    if (start == end) return;

    int mid = (start + end) / 2;

    merge_sort(start, mid, datas);
    merge_sort(mid + 1, end, datas);

    merge(start, mid, mid + 1, end, datas);
  }

  /*
        Merge array
        @param f_s : first_start
        @param f_e : first_end
        @param s_s : second_start
        @param s_e : second_end
        @param source : source array
*/
  void merge(int f_s, int f_e, int s_s, int s_e, int* source) {
    int size = (s_e - f_s) + 1;  // Merged array capacity
    int* temp = new int[size];

    int temp_index, first_index, second_index;
    for (temp_index = 0, first_index = f_s, second_index = s_s;
         first_index <= f_e && second_index <= s_e;) {
      if (source[first_index] < source[second_index]) {
        temp[temp_index] = source[first_index];
        first_index++;
      } else {
        temp[temp_index] = source[second_index];
        second_index++;
      }
      temp_index++;  // Pointed next array index
    }

    while (first_index <= f_e) {
      temp[temp_index] = source[first_index];
      first_index++;
      temp_index++;
    }

    while (second_index <= s_e) {
      temp[temp_index] = source[second_index];
      second_index++;
      temp_index++;
    }

    for (int source_index = f_s, temp_index = 0; source_index <= s_e;
         source_index++, temp_index++) {
      source[source_index] = temp[temp_index];
    }
    delete[] temp;
  }

  void swap(int& a, int& b) {
    int tmp = a;
    a = b;
    b = tmp;
  }

  void print() {
    for (int i = 0; i < capacity; i++) cout << "[" << datas[i] << "] ";
    cout << endl;
  }
};

void main() {
  List list1(LIST_SIZE, true);
  List list2(LIST_SIZE, true);
  List list3(LIST_SIZE, true);
  List list4(LIST_SIZE, true);

  cout << "--- Bubble Sort (Time complexity : O(n^2)) ---" << endl;
  list1.print();
  list1.bubble_sort();
  list1.print();

  cout << endl << "--- Insertion Sort (Time complexity : O(n^2)) ---" << endl;
  list2.print();
  list2.insertion_sort();
  list2.print();

  cout << endl << "--- Selection Sort (Time complexity : O(n^2)) ---" << endl;
  list3.print();
  list3.selection_sort();
  list3.print();

  cout << endl << "--- Merge Sort (Time complexity : O(nlogn)) ---" << endl;
  list4.print();
  list4.merge_sort();
  list4.print();
}