lab10

 #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 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; 

33 

Department of CSE (CY), RNSIT         

IV Semester          BCSL404 – ADA LABORATORY 

 

Department of CSE (CY), RNSIT         34 

 

 

 

    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)); 

    // printf("Randomly generated array: "); 

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

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

9999 

        // printf("%d ", arr[i]); 

    } 

    // printf("\n"); 

 

    // 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("Sorted array: "); 

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

    //     printf("%d ", arr[i]); 

    // } 

    // printf("\n"); 

 

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

 

    free(arr); // Free dynamically allocated memory 

    return 0; 

}