LAB 2&1

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

using namespace std;
//----------------------------------------------------sorts from lab 1------------------------------------------------
void bubble_sort( int tab[], int n)
{
    int step;
    int temp;
    int i;
    for( step = 0; step < n - 1; ++ step)
    for(i = 0; i < n - step - 1;++i)
    {
        if(tab[i] > tab[i+1])
        {
            temp = tab[i];
            tab[i] = tab[i+1];
            tab[i+1] =  temp;

        }
    }
}

void insertion1_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 selection_sort (int tab[], int n)
{
    int k ,j , minimum_position, swap;
    for (k = 0; k < (n - 1); k++)
    {
        minimum_position = k;
        for(j = k + 1; j < n; j++)
        {
            if(tab[j]< tab[minimum_position])
            minimum_position = j;
        }
        //swap(tab[k], tab[minimum_position]);
        swap = tab[k];
        tab[k]= tab[minimum_position];
        tab[minimum_position]= swap;
    }
}



//-----------------------------------------------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);

    //--------------------------------------------------from lab 1------------------------------------------------------------------------
    cout <<"--------------BUBBLE SORT------------"<< endl << endl;
    numbers_generate(numbers, n);
    start = clock(); //start measuring time
    bubble_sort(numbers, n); //apply bubble sort
    stop = clock();// stop measuring time
   time_Check(start, stop); //display measured time

cout << endl <<"--------------INSERTION SORT------------"<< endl << endl;
    numbers_generate(numbers, n);
    start = clock();
    insertion1_sort(numbers, n);
    stop = clock();
    time_Check(start, stop);

cout << endl<<"--------------SELECTION SORT------------"<< endl << endl;
    numbers_generate(numbers, n);
    start = clock();
    selection_sort(numbers, n); //apply selection sort
    stop = clock();
    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;
}