#include<iostream>
#include<fstream>
using namespace std;

ifstream f("UnOrderedArray.txt");
ofstream g("OrderedArray.txt");

//

struct LIST{
    int value;
    LIST *next;
};

void SWAP(int &a,int &b)
{
    int aux;
    aux=a;
    a=b;
    b=aux;
}
//LIST DECLARATION
LIST *listArray = new LIST();

void add(int x)
{
    LIST *p = new LIST();
    p->value=x;
    p->next=NULL;

    //check if is the first elem
    if(listArray==NULL)
    {
        //cout<<"1\n";
        listArray=p;
        listArray->next=NULL;
    }else{
        //cout<<"2\n";
        LIST *q = new LIST();
        q=listArray;
        while(q->next!=NULL)
        {
            q=q->next;
        }
        q->next=p;

    }

}
int* convertListToArray(LIST *a,int SIZE)
{
   int *matrix = new int[SIZE];
   for(int i=0;i<SIZE;i++)
   {
       matrix[i]=a->value;
       a=a->next;
   }
   return matrix;
}
void print_array(int *matrix,int n)
{
    for(int i=0;i<n;i++)
        g<<i<<" "<<matrix[i]<<endl;
}
//
void merge(int arr[], 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];

    /* Copy data to temp arrays L[] and R[] */
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1+ j];

    /* Merge the temp arrays back into arr[l..r]*/
    i = 0;
    j = 0;
    k = l; // Initial index of merged subarray
    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            arr[k] = L[i];
            i++;
        }
        else
        {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    /* Copy the remaining elements of L[], if there
       are any */
    while (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    }

    /* Copy the remaining elements of R[], if there
       are any */
    while (j < n2)
    {
        arr[k] = R[j];
        j++;
        k++;
    }
}

/* l is for left index and r is right index of the
   sub-array of arr to be sorted */
void mergeSort(int arr[], int l, int r)
{
    if (l < r)
    {
        // Same as (l+r)/2, but avoids overflow for
        // large l and h
        int m = l+(r-l)/2;

        // Sort first and second halves
        mergeSort(arr, l, m);
        mergeSort(arr, m+1, r);

        merge(arr, l, m, r);
    }
}

void quickSort(int vec[],int left,int right)
{
    int i,j,x;
    x=vec[(left+right)/2];

    i=left;
    j=right;
    do{
    while((i<right) && (vec[i]<x))
        i++;
    while((j>left) && (vec[j]>x))
        j--;
        if(i<=j)
        {
            SWAP(vec[i],vec[j]);
            i++;
            j--;
        }

    }while(i<=j);

    if(left<j)
        quickSort(vec,left,j);
    if(i<right)
        quickSort(vec,i,right);

}
void insertionSort(int vec[],int arraySize)
{
    int i=1,j;
    while(i<arraySize)
    {
        j=i;
        while(j>0 && vec[j-1]>vec[j])
        {
            SWAP(vec[j-1],vec[j]);
            j--;
        }
        i++;
    }
}

void selectionSort(int vec[],int arraySize)
{
    int i,j,iMin;
    for(i=0;i<arraySize;i++)
    {

       iMin=i;
       for(j=i+1;j<arraySize;j++)
       {
           if(vec[iMin]>vec[j])
            iMin=j;
       }
        SWAP(vec[i],vec[iMin]);
    }

}
int * countingSort(int vec[],int arraySize)
{
    int *count,*output;
    int i;
    int MIN=vec[0],MAX=vec[0];

    int oldval,total;

    //Establish the min and max values for K
    for(i=0;i<arraySize;i++)
            if(MIN>vec[i])
                MIN=vec[i];
            else if(MAX<vec[i])
                MAX=vec[i];

    total=0;
    output = new int[arraySize];//output array


    //allocate the memory for the counting array
    if(MIN<0)
    {
        count = new int[-MIN+MAX];

        for(i=0;i<=MAX-MIN+1;i++)
            count[i]=0;
        for(i=0;i<arraySize;i++)
            if(vec[i]<0)
            count[vec[i]-MIN]++;
            else
                count[vec[i]-MIN]++;

        for(i=0;i<=-MIN+MAX+1;i++)
        {
            oldval=count[i];
            count[i]=total;
            total+=oldval;
        }


        for(i=0;i<arraySize;i++)
        {
            if(vec[i]<0)
            {
                output[count[vec[i]-MIN]]=vec[i];
                count[vec[i]-MIN]+=1;
            }else{
                output[count[vec[i]-MIN]]=vec[i];
                count[vec[i]-MIN]+=1;
            }

        }

    }

    else{
        count = new int[MAX];
        for(i=0;i<MAX;i++)
            count[i]=0;
        for(i=0;i<arraySize;i++)
            count[vec[i]]++;

        for(i=0;i<MAX+1;i++)
        {
            oldval=count[i];
            count[i]=total;
            total+=oldval;
        }

        for(i=0;i<arraySize;i++)
        {
            output[count[vec[i]]]=vec[i];
            count[vec[i]]+=1;
        }
    }

    return output;

}
void radixSort(int vec[],int arraySize)
{
    int i,j;

    //for(i=0;i<arraySize;i++)


}
int main()
{
    int *ARRAY;
    int input;
    int count=0;

    listArray=NULL;

    while(!f.eof())
    {
        f>>input;
        add(input);
        count++;
    }

    ARRAY=convertListToArray(listArray,count);

    //delete listArray;

    /*MERGE SORT*/
    //mergeSort(ARRAY,0,count-1);
    //print_array(ARRAY,count);

    /*QUICK SORT*/
    //quickSort(ARRAY,0,count-1);
    //print_array(ARRAY,count);

    /*INSERTION SORT*/
   // insertionSort(ARRAY,count);
    //print_array(ARRAY,count);

    /*SELECTION SORT*/
    //selectionSort(ARRAY,count);
    //print_array(ARRAY,count);

    /*COUNTING SORT*/
    //ARRAY=countingSort(ARRAY,count);
    //print_array(ARRAY,count);



    return 0;
}