Sorting.cpp

#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <vector>
#include <map>
#include <ctime>
#include <string>
#include <math.h> 
#define Quick_Sort_Type int
#define ll long long
using namespace std;



enum Sorting{
    Insertion_Sort,
    Merge_Sort,
    Randomized_Quick_Sort_Lomuto_Partition,
    Randomized_Quick_Sort_Hoare_Partition,
    Randomized_Quick_Sort_3_Way_Partition,
    Counting_Sort,
    Quantity
};

class Sort_Methods{
private:
    map<int, vector<int>> numbers;
public:
    Sort_Methods(ll N){
        srand(time(NULL));
        for(int exp =  0; exp < 10; exp++){
            for(ll i = 0; i < N; i++){
                numbers[exp].push_back(rand() % 1000 + 1);
            }
        }
    }
    ~Sort_Methods(){
    }
    void print_arr(){
        for(auto& n: numbers){
            cout << n.first << ": ";
            for(auto& v: n.second){
                cout << v << " ";
            }
            cout <<  "\n";
        }
    }
    void Insertion_Sort(int);
    void Merge_Sort(int);
    void Randomized_Quick_Sort_Lomuto_Partition(int);
    void Randomized_Quick_Sort_Hoare_Partition(int);
    void Randomized_Quick_Sort_3_Way_Partition(int);
    void Counting_Sort(int);
private:
    void merge_sort_helper(vector<int>&, int, int);
    void merge(vector<int>&, int, int, int);
    void quick_sort(vector<int>&, int, int, Quick_Sort_Type);
    void three_way_helper(vector<int>&, int, int);
    void three_way(vector<int>&, int, int, int&, int&);
    void count_sort(vector<int>&);
    int lomuto_partition(vector<int>&, int, int);
    int hoare_partition(vector<int>&, int, int);
    
};


void Sort_Methods::Insertion_Sort(int exp){
    vector<int> arr = numbers[exp];
    for (int i = 1; i < (int)arr.size(); i++) {
        int key = arr[i];
        int j = i - 1;
        while (key < arr[j] && j >= 0) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

void Sort_Methods::Merge_Sort(int exp){
    vector<int> arr = numbers[exp];
    merge_sort_helper(arr, 0, (int)arr.size() - 1);
}
void Sort_Methods::merge_sort_helper(vector<int>& arr, int front, int back){
    if(front < back){
        int mid = (front + back) >> 1;
        merge_sort_helper(arr, front, mid);
        merge_sort_helper(arr, mid + 1, back);
        merge(arr, front, mid, back);
    }
}
void Sort_Methods::merge(vector<int>& arr, int front, int mid, int back){
    vector<int> left(arr.begin() + front, arr.begin() + mid + 1), right(arr.begin() + mid + 1, arr.begin() + back + 1);
    left.insert(left.end(), 1001);
    right.insert(right.end(), 1001);
    int leftidx = 0, rightidx = 0;
    for(int i = front; i <= back; i++){
        if(left[leftidx] <= right[rightidx]){
            arr[i] = left[leftidx];
            leftidx++;
        }else{
            arr[i] = right[rightidx];
            rightidx++;
        }
    }
}

void Sort_Methods::quick_sort(vector<int>& arr, int low, int high, Quick_Sort_Type sort_type){
    if(low < high){
        int idx = low;
        if(sort_type == Sorting::Randomized_Quick_Sort_Lomuto_Partition){
            int idx = lomuto_partition(arr, low, high);
        }else if(sort_type == Sorting::Randomized_Quick_Sort_Hoare_Partition){
            int idx = hoare_partition(arr, low, high);
        }
        quick_sort(arr, low, idx - 1, sort_type);
        quick_sort(arr, idx + 1, high, sort_type);
    }
}

void Sort_Methods::Randomized_Quick_Sort_Lomuto_Partition(int exp){
    vector<int> arr = numbers[exp];
    quick_sort(arr, 0, (int)arr.size() - 1, Sorting::Randomized_Quick_Sort_Lomuto_Partition);
}

int Sort_Methods::lomuto_partition(vector<int>& arr, int low, int high){
    int pivot = arr[high];
    int i = low - 1;
    for(int j = low; j < high; j++){
        if(arr[j] <= pivot){
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

void Sort_Methods::Randomized_Quick_Sort_Hoare_Partition(int exp){
    vector<int> arr = numbers[exp];
    quick_sort(arr, 0, arr.size() - 1, Sorting::Randomized_Quick_Sort_Hoare_Partition);
}

int Sort_Methods::hoare_partition(vector<int>& arr, int low, int high){
    int pivot = arr[low];
    int i = low - 1, j = high + 1;
    while(1){
        do{
            i++;
        }while(arr[i] < pivot);
        
        do{
            j--;
        }while(arr[j] > pivot);
        
        if(i >= j){
            return j;
        }
        swap(arr[i], arr[j]);
    }
}

void Sort_Methods::Randomized_Quick_Sort_3_Way_Partition(int exp){
    vector<int> arr = numbers[exp];
    three_way_helper(arr, 0, (int)arr.size() - 1);
}

void Sort_Methods::three_way_helper(vector<int>& arr, int low, int high){
    if(low < high){
        int begin, end;
        three_way(arr, low, high, begin, end);
        three_way_helper(arr, low, --begin);
        three_way_helper(arr, ++end, high);
    }
}

void Sort_Methods::three_way(vector<int>& arr, int low, int high, int& begin, int& end){
    int pivot = arr[low];
    begin = low, end = high;
    for(int i = begin + 1; i <= end; i++){
        if(arr[i] < pivot){
            swap(arr[i], arr[begin]);
            begin++;
        }else if(arr[i] > pivot){
            swap(arr[i], arr[end]);
            end--;
            i--;
        }
    }
}

void Sort_Methods::Counting_Sort(int exp){
    vector<int> arr = numbers[exp];
    count_sort(arr);
}

void Sort_Methods::count_sort(vector<int>& arr){
    int sz = arr.size();
    vector<int> tmp_arr(sz);
    vector<int> count_arr(sz);
    int x = arr[0];
    for(int i = 1; i < sz; i++){
        if(arr[i] > x){
            x = arr[i];
        }
    }
    for(int i = 0; i <= x; i++){
        count_arr[i] = 0;
    }
    for (int i = 0; i < sz; i++){
        count_arr[arr[i]]++;
    }
    for (int i = 1; i <= x; i++){
        count_arr[i] += count_arr[i - 1];
    }
    for (int i = sz - 1; i >= 0; i--) {
        tmp_arr[count_arr[arr[i]] - 1] = arr[i];
        count_arr[arr[i]]--;
    }
    arr = tmp_arr;
}

typedef void (Sort_Methods::*FP)(int);

int main(int argc, char *argv[]){
    ll Q = pow(2, stoi(argv[1]));
    Sort_Methods sm(Q);
    map<int, vector<double>> latency;
    vector<FP> fps(Sorting::Quantity);
    fps[Sorting::Insertion_Sort] = &Sort_Methods::Insertion_Sort;
    fps[Sorting::Merge_Sort] = &Sort_Methods::Merge_Sort;
    fps[Sorting::Randomized_Quick_Sort_Lomuto_Partition] = &Sort_Methods::Randomized_Quick_Sort_Lomuto_Partition;
    fps[Sorting::Randomized_Quick_Sort_Hoare_Partition] = &Sort_Methods::Randomized_Quick_Sort_Hoare_Partition;
    fps[Sorting::Randomized_Quick_Sort_3_Way_Partition] = &Sort_Methods::Randomized_Quick_Sort_3_Way_Partition;
    fps[Sorting::Counting_Sort] = &Sort_Methods::Counting_Sort;
    // sm.print_arr();
    clock_t start, end;
    map<int, string> log;
    log[0] = "Processing Insertion Sort";
    log[1] = "Processing Merge Sort";
    log[2] = "Processing Qsort with L partition";
    log[3] = "Processing Qsort with H partition";
    log[4] = "Processing Qsort with 3 partition";
    log[5] = "Processing Counting Sort";
    for(int method = 0; method < Sorting::Quantity; method++){
        // cout << log[method] << "...\n";
        for(int exp = 0; exp < 10; exp++){
            // cout << "Experments: " << exp + 1 << "\n";
            start = clock();
            (sm.*fps[method])(exp);
            end = clock();
            double diff = end - start;
            latency[method].push_back(diff);
        }
    }
    for(auto& l: latency){
        cout << l.first << ": ";
        for(auto& v: l.second){
            cout << v << " ";
        }
        cout << "\n";
    }
    // cout << "Sorted:\n";
    // sm.print_arr();
    return 0;
}