#include <iostream>
using namespace std;
#include <Windows.h>
#include <ctime>

void insertionsort(int arr[],int size){

    int n=size,temp,d;

    for (int c = 1 ; c <= n - 1; c++)
    {
        d = c;

        while ( d > 0 && arr[d] < arr[d-1]) {
            temp     = arr[d];
            arr[d]   = arr[d-1];
            arr[d-1] = temp;

            d--;
        }
    }


}

void bubblesort(int arr[],int size){

    int swap;


    for(int k=0;k<size;k++){
        for(int l=0;l<size;l++){


            if(arr[l+1]!=arr[size]&&arr[l]>arr[l+1]){

                swap=arr[l];
                arr[l]=arr[l+1];
                arr[l+1]=swap;

            }

        }

    }
}

void mergeSort(int arr[],int low,int mid,int high,int msize){

    int temp[100000];
    int i,m,k,l;

    l=low;
    i=low;
    m=mid+1;

    while((l<=mid)&&(m<=high)){

        if(arr[l]<=arr[m]){
            temp[i]=arr[l];
            l++;
        }
        else{
            temp[i]=arr[m];
            m++;
        }
        i++;
    }

    if(l>mid){
        for(k=m;k<=high;k++){
            temp[i]=arr[k];
            i++;
        }
    }
    else{
        for(k=l;k<=mid;k++){
            temp[i]=arr[k];
            i++;
        }
    }

    for(k=low;k<=high;k++){
        arr[k]=temp[k];
    }

}

void partitionmerge(int arr[],int low,int high,int mersize){

    int mid;

    if(low<high){
        mid=(low+high)/2;

        partitionmerge(arr,low,mid,mersize);
        partitionmerge(arr,mid+1,high,mersize);
        mergeSort(arr,low,mid,high,mersize);
    }
}

void quickSort(int arr[], int left, int right) {
    int i = left, j = right;
    int tmp;
    int pivot = arr[(left + right) / 2];

    /* partition */
    while (i <= j) {
        while (arr[i] < pivot)
            i++;
        while (arr[j] > pivot)
            j--;
        if (i <= j) {
            tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
            i++;
            j--;
        }
    };

    /* recursion */
    if (left < j)
        quickSort(arr, left, j);
    if (i < right)
        quickSort(arr, i, right);
}

void printfun(int *a,int max){
    cout<<"Sorted elements are : ";

    for(int k=0;k<max;k++){

        cout<<a[k]<<",";

    }
    cout<<endl;

}

void createarr(int a[],int size){


    for(int k=0;k<size;k++){

        a[k]=0+rand()%size;

    }



}


int main(){

    //insertionsort(arr,size);
    //bubblesort(arr,size);
    //partitionmerge(arr,0,max,arrsize)
    //quickSort(arr,0,arrsize-1)


#pragma region implementarray
    srand(time(NULL));
    int *arr1=new int[20];
    int *arr2=new int[50];
    int *arr3=new int[100];
    int *arr4=new int[300];
    int *arr5=new int[500];
    int *arr6=new int[1000];
    int *arr7=new int[5000];
    int *arr8=new int[10000];
    int *arr9=new int[50000];
    int *arr10=new int[100000];


    createarr(arr1,20);
    createarr(arr2,50);
    createarr(arr3,100);
    createarr(arr4,300);
    createarr(arr5,500);
    createarr(arr6,1000);
    createarr(arr7,5000);
    createarr(arr8,10000);
    createarr(arr9,50000);
    createarr(arr10,100000);





#pragma endregion implementarray

#pragma region testingtime

    LARGE_INTEGER frequency;        // ticks per second
    LARGE_INTEGER t1, t2;           // ticks
    double elapsedTime;


    QueryPerformanceFrequency(&frequency);
    QueryPerformanceCounter(&t1);



    //bubblesort(arr1,20);
    //bubblesort(arr2,50);
    //bubblesort(arr3,100);
    //bubblesort(arr4,300);
    //bubblesort(arr5,500);
    //bubblesort(arr6,1000);
    //bubblesort(arr7,5000);
    //bubblesort(arr8,10000);
    //bubblesort(arr9,50000);
    //bubblesort(arr10,100000);


    //insertionsort(arr1,20);
    //insertionsort(arr2,50);
    //insertionsort(arr3,100);
    //insertionsort(arr4,300);
    //insertionsort(arr5,500);
    //insertionsort(arr6,1000);
    //insertionsort(arr7,5000);
    //insertionsort(arr8,10000);
    //insertionsort(arr9,50000);
    //insertionsort(arr10,100000);


    //quickSort(arr1,0,19);
    //quickSort(arr2,0,49);
    //quickSort(arr3,0,99);
    //quickSort(arr4,0,299);
    //quickSort(arr5,0,499);
    //quickSort(arr6,0,999);
    //quickSort(arr7,0,4999);
    //quickSort(arr8,0,9999);
    //quickSort(arr9,0,49999);
    //quickSort(arr10,0,99999);

    //partitionmerge(arr1,0,19,20);
    //partitionmerge(arr2,0,49,50);
    //partitionmerge(arr3,0,99,100);
    //partitionmerge(arr4,0,299,300);
    //partitionmerge(arr5,0,499,500);
    //partitionmerge(arr6,0,999,1000);
    //partitionmerge(arr7,0,4999,5000);
    //partitionmerge(arr8,0,9999,10000);
    //partitionmerge(arr9,0,49999,50000);
    //partitionmerge(arr10,0,99999,100000);

    QueryPerformanceCounter(&t2);

    elapsedTime = (t2.QuadPart - t1.QuadPart) * 1000.0 / frequency.QuadPart;
    cout << elapsedTime << " ms.\n";



#pragma endregion testingtime

    delete []arr1;
    delete []arr2;
    delete []arr3;
    delete []arr4;
    delete []arr5;
    delete []arr6;
    delete []arr7;
    delete []arr8;
    delete []arr9;
    delete []arr10;


    system("Pause");
    return 0;

}