#include "sortAlgos.h"
#include <stdio.h>
#include <sys/timeb.h>

int msDiff();
void arrCP(long int *a1, long int *a2, long int laenge);
void arrUmordnen(long int *a1, long int *a2, long int laenge);

struct timeb t1, t2, tdiff;
int z1, z2;

int main(int argc, char** argv) {
    long int anzSch1 = 0; //Anzahl der Schluessel fuer Gruppe 1
    long int anzSch2 = 0; //Anzahl der Schluessel fuer Gruppe 2

    srand(time(0));

    printf("Gruppe 1:\n"
            "  Einfuegen (Insertion-Sort)\n"
            "  Auswaehlen (Selection-Sort)\n"
            "  Austauschen (Bubble-Sort, Exchange-Sort) ohne Merker\n"
            "  Austauschen (Bubble-Sort, Exchange-Sort) mit Merkern\n\n"
            "Gruppe 2:\n"
            "  Abnehmende Schrittweite (Shellsort)\n"
            "  Baeumen (Heapsort)\n"
            "  Zerlegung (Quicksort)\n"
            "  Mischen (Mergesort)\n\n"
            "Anzahl der Schluessel fuer Gruppe 1 eingeben: ");

    scanf("%d", &anzSch1);

    long int toSortASC[anzSch1];
    long int toSortRND[anzSch1];
    long int toSortDSC[anzSch1];

    long int toSortASC2[anzSch1];
    long int toSortRND2[anzSch1];
    long int toSortDSC2[anzSch1];

    //Array fuer Gruppe 1 fuellen
    for (long int i = 0; i < anzSch1; i++) {
        toSortRND[i] = RandomNumber(65535, 1);
        //printf("G1 %d\n", toSort1[i]);    //debug
    }

    //Unsortiertes "Quellarray" toSortRND kopieren
    arrCP(toSortRND, toSortASC, anzSch1);

    //Kopiertes Array (aufsteigend) sortieren
    quickSort(toSortASC, 0, anzSch1);

    //Aufsteigend sortiertes Array kopieren und auf absteigend "umordnen"
    arrUmordnen(toSortASC, toSortDSC, anzSch1);



    printf("Anzahl der Schluessel fuer Gruppe 2 eingeben: ");

    scanf("%d", &anzSch2);


    long int toSortASCz[anzSch2];
    long int toSortRNDz[anzSch2];
    long int toSortDSCz[anzSch2];

    long int toSortASCz2[anzSch2];
    long int toSortRNDz2[anzSch2];
    long int toSortDSCz2[anzSch2];
    //Array fuer Gruppe 2 fuellen
    for (long int i = 0; i < anzSch2; i++) {
        toSortRNDz[i] = RandomNumber(65535, 1);
    }

    //Unsortiertes "Quellarray" toSortRND kopieren
    arrCP(toSortRNDz, toSortASCz, anzSch2);

    //Kopiertes Array (aufsteigend) sortieren
    quickSort(toSortASCz, 0, anzSch2);

    //Aufsteigend sortiertes Array kopieren und auf absteigend "umordnen"
    arrUmordnen(toSortASCz, toSortDSCz, anzSch2);


    printf("\nNo. of keys\tascending \trandom \t\tdescending\n"
            "%d\t\t[ms] \t\t[ms] \t\t[ms]\n"
            "-----------------------------------------------------------\n",
            anzSch1);

    // I N S E R T I O N  -  S O R T
    arrCP(toSortASC, toSortASC2, anzSch1);
    arrCP(toSortRND, toSortRND2, anzSch1);
    arrCP(toSortDSC, toSortDSC2, anzSch1);


    ftime(&t1);
    insertionSort(toSortASC2, anzSch1);
    ftime(&t2);

    printf("Insertion-Sort\t%d", msDiff());

    ftime(&t1);
    insertionSort(toSortRND2, anzSch1);
    ftime(&t2);

    printf("\t\t%d", msDiff());

    ftime(&t1);
    insertionSort(toSortDSC2, anzSch1);
    ftime(&t2);

    printf("\t\t%d\n", msDiff());


    // S E L E C T I O N  -  S O R T

    //Neue Testarrays fuer Selection-Sort bereitstellen
    arrCP(toSortASC, toSortASC2, anzSch1);
    arrCP(toSortRND, toSortRND2, anzSch1);
    arrCP(toSortDSC, toSortDSC2, anzSch1);


    ftime(&t1);
    selectionSort(toSortASC2, anzSch1);
    ftime(&t2);

    printf("Selection-Sort\t%d", msDiff());

    ftime(&t1);
    selectionSort(toSortRND2, anzSch1);
    ftime(&t2);

    printf("\t\t%d", msDiff());

    ftime(&t1);
    selectionSort(toSortDSC2, anzSch1);
    ftime(&t2);

    printf("\t\t%d\n", msDiff());


    // B U B B L E  -  S O R T

    //Neue Testarrays fuer Bubble-Sort bereitstellen
    arrCP(toSortASC, toSortASC2, anzSch1);
    arrCP(toSortRND, toSortRND2, anzSch1);
    arrCP(toSortDSC, toSortDSC2, anzSch1);


    ftime(&t1);
    bubbleSort(toSortASC2, anzSch1);
    ftime(&t2);

    printf("Bubble-Sort\t%d", msDiff());

    ftime(&t1);
    bubbleSort(toSortRND2, anzSch1);
    ftime(&t2);

    printf("\t\t%d", msDiff());

    ftime(&t1);
    bubbleSort(toSortDSC2, anzSch1);
    ftime(&t2);

    printf("\t\t%d\n", msDiff());




    // B U B B L E  -  S O R T  M I T  M E R K E R

    //Neue Testarrays fuer Bubble-Sort mit Merker bereitstellen
    arrCP(toSortASC, toSortASC2, anzSch1);
    arrCP(toSortRND, toSortRND2, anzSch1);
    arrCP(toSortDSC, toSortDSC2, anzSch1);


    ftime(&t1);
    bubbleSortM(toSortASC2, anzSch1);
    ftime(&t2);

    printf("Bubble-Sort (M)\t%d", msDiff());

    ftime(&t1);
    bubbleSortM(toSortRND2, anzSch1);
    ftime(&t2);

    printf("\t\t%d", msDiff());

    ftime(&t1);
    bubbleSortM(toSortDSC2, anzSch1);
    ftime(&t2);

    printf("\t\t%d\n", msDiff());




    printf("\nNo. of keys\tascending \trandom \t\tdescending\n"
            "%d\t\t[ms] \t\t[ms] \t\t[ms]\n"
            "-----------------------------------------------------------\n",
            anzSch2);



    // S H E L L  -  S O R T

    //Neue Testarrays fuer Shell-Sort bereitstellen
    arrCP(toSortASCz, toSortASCz2, anzSch2);
    arrCP(toSortRNDz, toSortRNDz2, anzSch2);
    arrCP(toSortDSCz, toSortDSCz2, anzSch2);


    ftime(&t1);
    shellSort(toSortASCz2, anzSch2);
    ftime(&t2);

    printf("Shell-Sort\t%d", msDiff());

    ftime(&t1);
    shellSort(toSortRNDz2, anzSch2);
    ftime(&t2);

    printf("\t\t%d", msDiff());

    ftime(&t1);
    shellSort(toSortDSCz2, anzSch2);
    ftime(&t2);

    printf("\t\t%d\n", msDiff());




    // H E A P  -  S O R T

    //Neue Testarrays fuer Heap-Sort bereitstellen
    arrCP(toSortASCz, toSortASCz2, anzSch2);
    arrCP(toSortRNDz, toSortRNDz2, anzSch2);
    arrCP(toSortDSCz, toSortDSCz2, anzSch2);


    ftime(&t1);
    heapSort(toSortASCz2, anzSch2);
    ftime(&t2);

    printf("Heap-Sort\t%d", msDiff());

    ftime(&t1);
    heapSort(toSortRNDz2, anzSch2);
    ftime(&t2);

    printf("\t\t%d", msDiff());

    ftime(&t1);
    heapSort(toSortDSCz2, anzSch2);
    ftime(&t2);

    printf("\t\t%d\n", msDiff());



    // Q U I C K  -  S O R T

    //Neue Testarrays fuer Quick-Sort bereitstellen
    arrCP(toSortASCz, toSortASCz2, anzSch2);
    arrCP(toSortRNDz, toSortRNDz2, anzSch2);
    arrCP(toSortDSCz, toSortDSCz2, anzSch2);


    ftime(&t1);
    quickSort(toSortASCz2, 0, anzSch2);
    ftime(&t2);

    printf("Quick-Sort\t%d", msDiff());

    ftime(&t1);
    quickSort(toSortRNDz2, 0, anzSch2);
    ftime(&t2);

    printf("\t\t%d", msDiff());

    ftime(&t1);
    quickSort(toSortDSCz2, 0, anzSch2);
    ftime(&t2);

    printf("\t\t%d\n", msDiff());



    // M E R G E  -  S O R T

    //Neue Testarrays fuer Merge-Sort bereitstellen
    arrCP(toSortASCz, toSortASCz2, anzSch2);
    arrCP(toSortRNDz, toSortRNDz2, anzSch2);
    arrCP(toSortDSCz, toSortDSCz2, anzSch2);


    ftime(&t1);
    mergeSort(toSortASCz2, anzSch2);
    ftime(&t2);

    printf("Merge-Sort\t%d", msDiff());

    ftime(&t1);
    mergeSort(toSortRNDz2, anzSch2);
    ftime(&t2);

    printf("\t\t%d", msDiff());

    ftime(&t1);
    mergeSort(toSortDSCz2, anzSch2);
    ftime(&t2);

    printf("\t\t%d\n", msDiff());


    //arrayAusgeb(toSort1);
    return (0);
}

int msDiff() { //Nimmt halt immer &t1 und &t2
    //Zeit umrechnen in milisekunden seit Unixzeitbeginn
    z1 = t1.time * 1000 + t1.millitm;
    z2 = t2.time * 1000 + t2.millitm;
    return (z2 - z1);
}

void arrCP(long int *a1, long int *a2, long int laenge) { //Kopiert Inhalte von a1 in a2
    for (long int i = 0; i < laenge; i++) {
        a2[i] = a1[i];
    }
}

//Schreibe a1 in umgekehrter Reihenfolge in a2
void arrUmordnen(long int *a1, long int *a2, long int laenge) {
    for (long int i = 0; i < laenge; i++) {
        a2[i] = a1[laenge - 1 - i];
    }
}