lab 2 08.04

#include <stdio.h>
#include <time.h>
#include <cstdlib>

using namespace std;

/*void mergeOutOfPlace(int *arr, int first, int mid, int last) {
    // Merges two contigous sub-arrays and sorts them out-of-place
    // Condition Required: Sub-arrays must be sorted individually
    int *l = new int [mid-first];
    int *r = new int [last-mid];
    int *tempArr = new int [last-first];

    // copying into new arrays
    for (int i=0, j=first; i<mid-first; ++i, ++j) {
        l[i] = arr[j];
    }
    for (int i=0, j=mid; i<last-mid; ++i, ++j) {
        r[i] = arr[j];
    }

    // merge
    for(int i=0, j=0, k=0; k<last-first; ++k) {
        if (i == mid-first) {
            tempArr[k] = r[j++];
        }
        else if (j == last-mid) {
            tempArr[k] = l[i++];
        }
        else {
            //(l[i] < r[j]) ? (tempArr[k] = l[i++]) : (temp[k] = r[j++]);
        }
    }

    // copy into original array
    for(int i=first, j=0; j<last-first; ++i, ++j) {
        arr[i] = tempArr[j];
    }

    delete[] l;
    delete[] r;
    delete[] tempArr;
}

void mergeSortBottomUp(int *arr, int first, int last, int size) {
    if (size == 0) return;
    // width determines the length of the 2 arrays, the contiguous
    // arrays which are sent to the mergeOutOfPlace function.
    int width=2;
    // we select arrays with length = power of 2.
    for ( ; width<size ; width*=2) {
        // iterating backwards as iterating forward
        // does not work. mergeOutOfPlace is common
        // for different merge algorithms. When iterating
        // forward the left array has a bug
        int next=size-width, curr=size;
        for ( ; next>=0; curr=next, next-=width) {
            int mid = (curr+next)/2;
            mergeOutOfPlace(arr, next, mid, curr);
        }
        // whenever array of length = pow2 is not selectable
        // we select varied length array, which is always near
        // the end of iteration
        if (curr>=2) {
            mergeOutOfPlace(arr, 0, (size%(width>>1)), curr);
        }
    }
    // if array not power of 2
    if ( (size%(width>>1)) != 0 )
        mergeOutOfPlace(arr, 0, size%(width>>1), size);
        // if array power of 2
    else mergeOutOfPlace(arr, 0, size/2, size);
}
*/
void selectionSort(int arr[], int n) {
    int i, j, minIndex, tmp;
    for (i = 0; i < n - 1; i++) {
        minIndex = i;
        for (j = i + 1; j < n; j++)
            if (arr[j] < arr[minIndex])
                minIndex = j;
        if (minIndex != i) {
            tmp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = tmp;
        }
    }
}

void fillArray(int array[], int table_size){
    for (int i = 0; i < table_size; i++) {
        array[i] = (rand() % 1000000) + 0;
    }
}

int main() {
    srand(time(NULL));
    int size_powers[3] = { 14, 18, 22 };
    int sorting_type;

    FILE * fp;
    fp = fopen ("times.csv", "w+");
    fprintf(fp, "table size,sorting type,sorting time\n");

    for(int n = 0; n < 3; n++) {

        float t = 0;
        clock_t start;
        int table_size = 2 << size_powers[n];
        int tab[table_size];

        switch(n){
            case 0:

                for(int i=0; i<3; i++){
                    switch(i){
                        case 0:
                            sorting_type = i + 1;
                            fillArray(tab, table_size);
                            start=clock();

                            t=(clock()-start)/ CLOCKS_PER_SEC;
                            printf ("%d -%d (%f seconds)\n",n,i, t);
                            fprintf(fp, "%d,%d,%f\n", table_size, sorting_type, t);
                            break;

                        case 1:

                            break;

                        case 2:

                            break;
                    }
                }
                break;

            case 1:

                for(int i=0; i<3; i++){
                    switch(i){
                        case 0:

                            break;

                        case 1:

                            break;

                        case 2:

                            break;
                    }
                }
                break;

            case 2:

                for(int i=0; i<3; i++){
                    switch(i){
                        case 0:

                            break;

                        case 1:

                            break;

                        case 2:

                            break;
                    }
                }
                break;
        }

    }
    fclose(fp);

    return 0;
}