DS_Assignment1

/*
 * main.c
 *
 *  Created on: Dec 15, 2014
 *      Author: hershco
 */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 10

void Merge(int* a ,int data[], int p ,int q , int r);
void MergeSort(int* a ,int data[], int p , int r);
int Partition(int* a,int data[], int p, int r);
void quickSort( int a[], int data[], int p, int r);
void insertionSort (int a [],int data[], int size);
void quicksort_analysis(int a[], int data[], int length, int amount,FILE * database);
void insertsort_analysis(int a[], int data[], int length, int amount,FILE * database);
void mergesort_analysis(int a[], int data[], int length, int amount,FILE * database);
void printdata(int a[], int data[], int n);
void fillarray(int a[], int n);



int main()
{
    FILE * database;
    int a[100000], i, n, size,data[5];
    time_t t;
    srand((unsigned) time(&t));

    database=fopen("data.csv","w");
    n = 50; //Number of Array to build & Sort
    size = 100; //size of each array

    for (i=1; i<31; i++)
    {
    printf("Running on size : %d \n",size*i);
    fprintf(database,"\n%d",size*i);
    quicksort_analysis(a,data, size*i, n,database);
    mergesort_analysis(a,data, size*i, n,database);
    insertsort_analysis(a,data, size*i, n,database);
    }
    fclose(database);

}//end main


void Merge(int a[] ,int data[], int p ,int q , int r){
    int i,j = 0,k = 0;
    int n1 = q-p+1;
    int n2 = r-q;
    int *left = NULL,*right= NULL;
    if (!(left = (int*)malloc(sizeof(int)* (n1 + 1))))
            exit(1);
    if(!(right = (int*)malloc(sizeof(int)* (n2 +1)))){
        free(left);
        exit(1);
    }
    for (i =0 ; i < n1 ; i ++){
        left[i] = a[p + i];
        data[1] ++;
    }
    for (i = 0; i < n2 ;  i++ ){
        right[i] = a[q  + i + 1];
        data[1] ++;
    }
    left[n1] =  2147483647;
    right[n2] =  2147483647;
    for (i = p ;i <= r; i++){
        if (left[j] <= right[k]){
            a[i] = left[j];
            data[1]++;
            j++;
        }
        else{
            a[i] =right[k];
            data[1]++;
            k++;
        }
        data[2] ++;
    }
    free(left);
    free(right);
}

void MergeSort(int a[] ,int data[], int p , int r){
    int q;
    if(p<r){
        q = (p+r)/2;
        MergeSort(a,data,p,q);
        MergeSort(a,data,q+1,r);
        Merge(a,data,p,q,r);
    }
}

int Partition(int a[],int data[],int p,int r){
    int x,i,j,temp;
    x = a[r];
    data[1] ++;
    i = p-1;
    for ( j= p ; j <r ; j++){
        if (a[j] <= x){
            i++;
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
            data[1] = data[1] + 3;
        }
        data[2]++;
    }
    temp = a[i+1];
    a[i+1] =a[r];
    a[r] = temp;
    data[1] = data[1] + 3;
    return i+1;
}


void quickSort( int a[], int data[], int p, int r){
 int q;
 int temp;
 if (p <  r){
     q = rand() % (r - p);
     q= q + p;
     temp =  a[q];
     a[q] = a[r];
     a[r] = temp;
     data[1]  = data[1] +3;
     q = Partition(a, data, p ,r);
     quickSort(a,data,p,q-1);
     quickSort(a,data,q+1,r);
 }
}

void insertionSort (int* a,int data[] , int size){
    int j ,i, key;
    for ( j =1;  j < size ; j++){
        key =  a[j];
        data[1]++;
        i = j -1;
        while (i >= 0){
            data[2] ++;
            if (a[i ]< key) {data[2]++;break;}
            data[2]++;
            a[i+1] = a[i];
            data[1]++;
            i = i -1;
        }
    a[i+1] = key ;
    data[1] ++;
    }

}

void fillarray(int a[], int n)
{
 int i;
 for (i=0; i<n; i++)
  a[i]=rand() % 100 + 1;
}//end fillarray

void printdata(int a[], int data[], int n)
{
 int i;
 for (i=0; i<4; i++)
  printf("\n %d ", data[i]);
 printf("\n");
 for (i=0; i<n; i++)
  printf(" %d ", a[i]);
 printf("\n");
}//end printarray


void mergesort_analysis(int a[], int data[], int length, int amount,FILE * database)
{
    int i;
    data[4] = 0;
    data[3] = 0;

    for (i=0; i<amount; i++)
    {
    fillarray(a,length);
    data[1] = 0;
    data[2] = 0;
    MergeSort(a,data,0,length-1);
    data[4] = data[4]+(data[2]/amount);
    data[3] = data[3]+(data[1]/amount);
    }
    //printf("\nMS Average Comparisons for %d arrays of %d items: %d\n",amount,length,data[4]);
    //printf("MS Average Swaps for %d arrays of %d items: %d\n",amount,length,data[3]);
    fprintf(database,",%d,%d", data[4],data[3]);
}

void insertsort_analysis(int a[], int data[], int length, int amount,FILE * database)
{
    int i;
    data[4] = 0;
    data[3] = 0;

    for (i=0; i<amount; i++)
    {
    fillarray(a,length);
    data[1] = 0;
    data[2] = 0;
    insertionSort(a,data,length-1);
    data[4] = data[4]+(data[2]/amount);
    data[3] = data[3]+(data[1]/amount);
    }
    //printf("\nMS Average Comparisons for %d arrays of %d items: %d\n",amount,length,data[4]);
    //printf("MS Average Swaps for %d arrays of %d items: %d\n",amount,length,data[3]);
    fprintf(database,",%d,%d", data[4],data[3]);
}

void quicksort_analysis(int a[], int data[], int length, int amount,FILE * database)
{
    int i;
    data[4] = 0;
    data[3] = 0;

    for (i=0; i<amount; i++)
    {
    fillarray(a,length);
    data[1] = 0;
    data[2] = 0;
    quickSort(a,data,0,length-1);
    data[4] = data[4]+(data[2]/amount);
    data[3] = data[3]+(data[1]/amount);
    }
    //printf("QS Average Comparisons for %d arrays of %d items: %d\n",amount,length,data[4]);
    //printf("QS Average Swaps for %d arrays of %d items: %d\n",amount,length,data[3]);
    fprintf(database,",%d,%d", data[4],data[3]);
}