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

// Quicksort implementation as per Session 3 logic [cite: 13, 77]
int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // Choosing the last element as pivot [cite: 77]
    int i = (low - 1);
    for (int j = low; j < high; j++) {
        // If current element is smaller than or equal to pivot [cite: 77]
        if (arr[j] <= pivot) {
            i++;
            // Swap arr[i] and arr[j] [cite: 77]
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    // Final pivot swap to place it in the sorted position [cite: 77]
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return (i + 1);
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // Find pivot index such that smaller elements are on left [cite: 77]
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}


int main() {
    int n = 5000; // You can change this to 5000 or 10000 for your report
    int arr[n];
    clock_t start, end;

    // Seed the random number generator
    srand(time(0)); 

    // Fill the array with random numbers as per lab manual guidelines
    for (int i = 0; i < n; i++) {
        arr[i] = rand() % 10000; 
    }

    printf("Sorting %d elements using Quicksort...\n", n);

    // Capture start time
    start = clock(); 
    
    // Call the function (ensure your parameters match your manual's quickSort)
    quickSort(arr, 0, n - 1); 
    
    // Capture end time
    end = clock(); 

    double time_taken = ((double)(end - start)) / CLOCKS_PER_SEC;

    printf("Execution Successful!\n");
    printf("Time Taken: %f seconds\n", time_taken);

    return 0;
}