Question

c++

please read all question edit the program to test different random sizes of the array and give me the time in a file will be like random size of the array and next to it the time it took for each size

Im trying to do time analysis for Quick sort but i keep getting time = 0 also i want edit the program to test different random sizes of the array and give me the time in a file will be like random size of the array and next to it the time it took for each size of the random array for it so i can make a graph with time and size for quick sort

code c++

//System Libraries
#include<stdio.h>
#include <ctime>
#include <cmath>
#include <bits/stdc++.h>
#include<iostream>
#include <cstdlib>
using namespace std;

// A utility function to swap two elements
void swap(int* a, int* b)
{
    int t = *a;
    *a = *b;
    *b = t;
}

/* This function takes last element as pivot, places
   the pivot element at its correct position in sorted
    array, and places all smaller (smaller than pivot)
   to left of pivot and all greater elements to right
   of pivot */
int partition (int arr[], int low, int high)
{
    int pivot = arr[high];    // pivot
    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], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

/* The main function that implements QuickSort
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
void quickSort(int arr[], int low, int high)
{
    time_t start,end;
    float timeSp;
    start=clock();
    if (low < high)
    {
        /* pi is partitioning index, arr[p] 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);
    }

    end=clock();
    timeSp=float(start-end)/CLOCKS_PER_SEC;
    cout<<"Time spent= "<< timeSp <<endl;
}

/* 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");
}

// Driver program to test above functions
int main()
{
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    quickSort(arr, 0, n-1);
    printf("Sorted array: n");
    printArray(arr, n);
    return 0;
}

Answer 1

Give the size in large so you can get time.......

/**********************sort.cpp**********************/

#include<stdio.h>
#include <ctime>
#include <cmath>
#include <bits/stdc++.h>
#include<iostream>
#include <cstdlib>
using namespace std;

// A utility function to swap two elements
void swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}

/* This function takes last element as pivot, places
the pivot element at its correct position in sorted
array, and places all smaller (smaller than pivot)
to left of pivot and all greater elements to right
of pivot */
int partition (int arr[], int low, int high)
{
int pivot = arr[high]; // pivot
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], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}

/* The main function that implements QuickSort
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
void quickSort(int arr[], int low, int high)
{

if (low < high)
{
/* pi is partitioning index, arr[p] 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);
}
}

/* 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");
}

// Driver program to test above functions
int main()
{
int arr[100000];
int n = sizeof(arr)/sizeof(arr[0]);
for(int i=0;i<n;i++){
  
   arr[i] = rand() % 10000 + 1;
   }
   time_t start,end;
float timeSp;
start=clock();
quickSort(arr, 0, n-1);
end=clock();
timeSp=float(end-start)/CLOCKS_PER_SEC;
cout<<"Time spent= "<< timeSp <<endl;
// printf("Sorted array: \n");
//printArray(arr, n);
return 0;
}

/**************output***********************/

D:AFilelsort.exe 68 L 69 70 / Driver program to test above functions 71int main() Time spent= 0.005 Process exited after 0.1706 seconds with return value e Press any key to continue . . . 73 74 75 int n sizeof (arr)/sizeof (arr[]); for (int i-0jiknji+) arr[1] rand() % 10000 + 1; 78 79 80 81 82 83 84 85 86 87 time_t start,end; float timeSp; start-clock(); quickSort (arr, 0, n-1); end-clock); timeSp float (end-start)/CLOCKS_PER_SEC; coutくく"Time spent= "くく timeSp くくendl; // printf("Sorted array: n"); //printArray(arr, n); return 0; 89

// Driver program to test above functions | D:File'sort.exe 1 int main() 2 Time spent- 0.025 int arrhe000e int n sizeof (arr)/sizeof (arr[e]); for(int i-0ji<nji++)I Process exited after 0.1586 seconds with return value 0 Press any key to continue .. . arr[1] rand() % 10000 + 1; 7 time t start,end float tmeSp; start-clock (); quickSort(arr, 8, n-1)5 end-clock); timeSp-float(end-start)/CLOCKS_PER SEC coutくく"Time spent= "くく timeSp くくendl; 2 34 5 6 // printf("Sorted array: In") //printArray (arr, n); return 0; 8 39

Please let me know if you have any problem or you want to modify the answer, thanks :)