LAB 2

#include <iostream>
#include <time.h>
#include <algorithm>
#include <bits/stdc++.h>

using namespace std;

//-----------------------------------------------SORTS-------------------------------------------------------------

void insertion_sort(int tab[], int n) //insertion srt starts at 2_nd element
{
    int i, key, j;
    for (i = 1; i <= n - 1; i++) {
        key = i;

        while (key >= 0 && tab[key - 1] > tab[key]) {
            j = tab[key];
            tab[key] = tab[key - 1];
            tab[key - 1] = j;
            key--;
        }

    }
}

void merge(int tab[], int l, int m, int r)
{
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;
    //create temp arrays
    int L[n1], R[n2];
    //put copy data to arrays L & R
    for (i = 0; i < n1; i++) {
        L[i] = tab[l + i];
    }
    for (j = 0; j < n2; j++) {
        R[j] = tab[m + 1 + j];
    }
    i = 0;
    j = 0;
    k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            tab[k] = L[i];
            i++;
        } else {
            tab[k] = R[j];
            j++;
        }
        k++;
    }
    //copy the remaining elements of L[]
    while (i < n1) {
        tab[k] = L[i];
        i++;
        k++;
    }
    //copy the remaining elements of R[]
    while (j < n2) {
        tab[k] = R[j];
        j++;
        k++;
    }
}

//bottom- up merge sort = iterative merge sort
void merge_sort(int tab[], int l, int r)
{
    if (l < r) {
        int m = (l + r) / 2;
        merge_sort(tab, l, m);
        merge_sort(tab, m + 1, r);
        merge(tab, l, m, r);
    }
}
//tiled bottom-up merge sort = merge + insertion

void tiled_bottom_up_merge_sort(int tab[], int l, int r, int threshold)
{


    if (l < r) {
        if ((r - l) <= threshold) {
            insertion_sort(tab, threshold);
        } else {
            int m = (l + r) / 2;
            merge_sort(tab, l, m);
            merge_sort(tab, m + 1, r);
            merge(tab, l, m, r);
        }
    }
}

int compare(const void *a, const void *b)
{
    return (*(int *) a - *(int *) b);
}

//---------------------------------printing the array-------------------------------------------------------------

void print_tab(int tab[], int n) {
    int i;
    for (i = 0; i < n; i++)
        printf("%d%s", tab[i], "; ");
    printf("\n\n");
}

//------------------------------------------------------------------------time---------------------------------------------------------------------------

void time_Check(float Start, float Stop) {
    float Time;
    Time = (Stop - Start) / CLOCKS_PER_SEC;
    printf("Sorting time:\n %f  s ", Time);
    printf("\n\n");
}
//----------------------------------------------------------------------generate numbers------------------------------------------------------------------

void numbers_generate(int tab[], int n) {
    int i;
    srand(time(NULL)); //randomize speed
    for (i = 0; i < n; i++) {
        tab[i] = rand() % n;
    }
}

//---------------------------------------------------------------------main function---------------------------------------------------------------------------

int main() {
    int numbers[1000];
    float start;
    float stop;
    int n;
    n = (sizeof(numbers)) / (sizeof(int)); //find the size of array

    cout << "MERGE SORT" << endl << endl;
    numbers_generate(numbers, n);
    print_tab(numbers, n);
    start = clock();
    merge_sort(numbers, 0, n - 1);
    stop = clock();
    print_tab(numbers, n);
    time_Check(start, stop);


    cout << "TILED BOTTOM UP MARGE SORT" << endl << endl;
    numbers_generate(numbers, n);
    print_tab(numbers, n);
    start = clock();
    tiled_bottom_up_merge_sort(numbers, 0, n - 1, n / 10);
    stop = clock();
    print_tab(numbers, n);
    time_Check(start, stop);


    cout << "QUICK SORT" << endl << endl;
    numbers_generate(numbers, n);
    print_tab(numbers, n);
    start = clock();
    qsort(numbers, n, sizeof(int), compare);
    stop = clock();
    print_tab(numbers, n);
    time_Check(start, stop);
//----------------------------------------------------n=20^22 for tiled bottom-up merge sort-------------------------------------------------------------------
    int numbers1[16384];
    cout << "TILED BOTTOM UP MARGE SORT for n = 20^22 " << endl << endl;
    numbers_generate(numbers1, n);
    print_tab(numbers1, n);
    start = clock();
    tiled_bottom_up_merge_sort(numbers1, 0, n - 1, (20^22) / 10);
    stop = clock();
    print_tab(numbers1, n);
    time_Check(start, stop);
      return 0;
}