quick sort P3

 #include <stdio.h>

#include <stdlib.h>

#include <time.h>

// Function to partition the array and return the pivot index

int partition(int arr[], int low, int high) {

    int pivot = arr[high]; // Pivot element

    int i = (low - 1); // Index of smaller element

    for (int j = low; j <= high - 1; j++) {

        // If current element is smaller than or equal to pivot

        if (arr[j] <= pivot) {

            i++; // Increment index of smaller element

            // Swap arr[i] and arr[j]

            int temp = arr[i];

            arr[i] = arr[j];

            arr[j] = temp;

        }

    }

    // Swap arr[i + 1] and arr[high] (or pivot)

    int temp = arr[i + 1];

    arr[i + 1] = arr[high];

    arr[high] = temp;

    return (i + 1);

}

// Function to implement Quick Sort

void quickSort(int arr[], int low, int high) {

    if (low < high) {

        // pi is partitioning index, arr[pi] is now at the right place

        int pi = partition(arr, low, high);

        // Separately sort elements before partition and after partition

        quickSort(arr, low, pi - 1);

        quickSort(arr, pi + 1, high);

    }

}

int main() {

    int n, i;

    clock_t start, end;

    double cpu_time_used;

    printf("Enter the number of elements (n): ");

    scanf("%d", &n);

    if (n < 5000) {

        printf("Please enter a value of n greater than 5000.\n");

        return 1;

    }

    int *arr = (int *)malloc(n * sizeof(int));

    if (arr == NULL) {

        printf("Memory allocation failed.\n");

        return 1;

    }

    // Generate n random numbers

    srand(time(NULL));

    for (i = 0; i < n; i++) {

        arr[i] = rand() % 10000; // Generating random numbers between 0 to 9999

    }

    // Record the starting time

    start = clock();

    // Perform Quick Sort

    quickSort(arr, 0, n - 1);

    // Record the ending time

    end = clock();

    // Calculate the time taken

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

    printf("Time taken for sorting: %lf seconds\n", cpu_time_used);

    free(arr); // Free dynamically allocated memory

    return 0;

}