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

clock_t start, end;
double cpu_time_used;
int i, j;
FILE *fp;
void swap(int *xp, int *yp)
{
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}

// A function to implement bubble sort
void bubbleSort(int arr[], int n)
{

    for (i = 0; i < n - 1; i++)

        // Last i elements are already in place
        for (j = 0; j < n - i - 1; j++)
            if (arr[j] > arr[j + 1])
                swap(&arr[j], &arr[j + 1]);
}

// A function to implement swap sort
void swapSort(int arr[], int n)
{
    for (i = 0; i < n - 1; i++)
    {
        for (j = i + 1; j < n; j++)
        {
            if (arr[i] > arr[j])
            {
                swap(&arr[i], &arr[j]);
            }
        }
    }
}

int partition(int arr[], int l, int h)
{
    int x = arr[h];
    int i = (l - 1);

    for (int j = l; j <= h - 1; j++)
    {
        if (arr[j] <= x)
        {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[h]);
    return (i + 1);
}

/* A[] --> Array to be sorted,
   l  --> Starting index,
   h  --> Ending index */

void quickSortIterative(int arr[], int l, int h)
{
    // Create an auxiliary stack
    int stack[h - l + 1];

    // initialize top of stack
    int top = -1;

    // push initial values of l and h to stack
    stack[++top] = l;
    stack[++top] = h;

    // Keep popping from stack while is not empty
    while (top >= 0)
    {
        // Pop h and l
        h = stack[top--];
        l = stack[top--];

        // Set pivot element at its correct position
        // in sorted array
        int p = partition(arr, l, h);

        // If there are elements on left side of pivot,
        // then push left side to stack
        if (p - 1 > l)
        {
            stack[++top] = l;
            stack[++top] = p - 1;
        }

        // If there are elements on right side of pivot,
        // then push right side to stack
        if (p + 1 < h)
        {
            stack[++top] = p + 1;
            stack[++top] = h;
        }
    }
}

/* Function to print an array */
void printArray(int arr[], int size)
{
    int i;

    for (i = 0; i < size; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
}
void sort_algorithm(int n, int arr[])
{

    int lower = 1, upper = n, count = n;
    // Use current time as
    // seed for random generator
    srand(time(0));
    for (i = 0; i < count; i++)
    {
        int num = (rand() %
                   (upper - lower + 1)) +
                  lower;
        arr[i] = num;
    }

    printf("Unsorted array: \n");
    printArray(arr, n);


    start = clock();
    bubbleSort(arr, n);
    end = clock();
    cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
    fprintf(fp, "Time for bubbleSort: %f \n", cpu_time_used);
    printf("Sorted array by bubbleSort: \n");
    printArray(arr, n);
    printf("Time for bubbleSort: \n");
    printf("%f \n", cpu_time_used);

    start = clock();
    swapSort(arr, n);
    end = clock();
    cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
    fprintf(fp, "Time for swapSort: %f \n", cpu_time_used);
    printf("Sorted array by swapSort: \n");
    printArray(arr, n);
    printf("Time for swapSort: \n");
    printf("%f \n", cpu_time_used);

    start = clock();
    quickSortIterative(arr, 0, n - 1);
    end = clock();
    cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
    fprintf(fp, "Time for quickSort: %f \n", cpu_time_used);
    printf("Sorted array by quickSort: \n");
    printArray(arr, n);
    printf("Time for quickSort: \n");
    printf("%f \n", cpu_time_used);
}

int main()
{
    fp = fopen("Output.txt", "w");
    int *arr;
    int lenght_of_array;
    for (lenght_of_array = 10; lenght_of_array <= 1000; lenght_of_array*=10)
    {
        fprintf(fp, "Size of array is: %d\n", lenght_of_array);
        arr=calloc(lenght_of_array, sizeof(int));
        sort_algorithm(lenght_of_array, arr);

    }

    fclose(fp);
    free(arr);
    return 0;
}