#include <iostream>
#include <time.h>
#include <cstdlib>
#include <string>
#include <sstream>


using namespace std;

time_t showTime(time_t start,time_t endTime)
{
    cout << endl << "Processing time: " << difftime(endTime,start) << endl;
    return difftime(endTime,start);
}

void showArr(int array[], int size){//tablica poprawnie przekazana do funkcji
    for(int i = 0;i < size;i++)
    {
        cout << array[i] << ',';//tu wyskakuje blad (segmentation fault)
    }
    cout << endl;
}


void insertSort(int arr[],int n,time_t *tt)
{
     int i,j,k,elem;
     time_t start,endTime;
     time(&start);
     for(i = (n-2);i >= 0;i--)
     {
         j = n - 1;
         elem=arr[i];
         while(j > i && arr[j]>=elem)
            j--;
         for(k = i;k < j;k++)
            arr[k]=arr[k+1];
         arr[j]=elem;
         showArr(arr,n);
     }
     time(&endTime);
     *tt = showTime(start,endTime);
}

void bubbleSort(int arr[],int n,time_t *tt)
{
    int i,j,tmp;
    time_t start,endTime;
    time(&start);
    for(i = 0;i < n - 1;i++)
    {
        for(j = (n-1);j > i;j--)
            if(arr[j] < arr[j-1])
            {
                tmp=arr[j];
                arr[j]=arr[j-1];
                arr[j-1]=tmp;
            }
     showArr(arr,n);
     }
     time(&endTime);
     *tt = showTime(start,endTime);
}

void mergeArr(int arr[],int arrAux[], int nFrom, int nCenter, int nTo)
{
    int j = nFrom,k = nCenter;
    for(int i = nFrom;j < nCenter || k < nTo;i++)
    {
        if(j == nCenter)
        {
            arrAux[i] = arr[k];
            k++;
        }
        else if(k == nTo)
        {
            arrAux[i] = arr[j];
            j++;
        }
        else
        {
            arrAux[i] = arr[j] <= arr[k] ? arr[j] : arr[k];
            if(arr[j] <= arr[k])j++;
            else k++;
        }
    }
    for(int i = nFrom;i < nTo;i++)
        arr[i] = arrAux[i];
}

void auxMergeSort(int arr[],int arrAux[], int nFrom, int nTo)
{
    if(nFrom<nTo-1)
    {
        int nCenter=(nFrom+nTo)/2;
        auxMergeSort(arr,arrAux,nFrom,nCenter);
        auxMergeSort(arr,arrAux,nCenter,nTo);
        mergeArr(arr,arrAux,nFrom,nCenter,nTo);
    }
}
void mergeSort(int arr[],int len,time_t *tt)
{
    time_t start,endTime;
    time(&start);
    int *arr2=new int[len];
    auxMergeSort(arr,arr2,0,len);
    delete []arr2;
    time(&endTime);
    *tt = showTime(start,endTime);
}
int * loadArray(int size){
    int *arr = new int(size);
    int *p = arr;
    if(arr == NULL)
        return NULL;
    else
    {
        for(int i = 0;i < size;i++)
        {
            *p = rand()%100;
            p++;
        }
        return arr;//tablica poprawnie zaalokowana
    }
}

int main()
{
    srand(1);
    time_t one,two,three;
    int *ar = loadArray(1000);
    insertSort(ar,1000,&one);
    delete ar;
    ar = loadArray(1000);
    insertSort(ar,1000,&two);
    delete ar;
    ar = loadArray(10000);
    insertSort(ar,100,&three);
    delete ar;
    cout << "\nOne: " << one << "\nTwo: " << two << "\nThree: " << three;
    return 0;
}