Question

Task 3:

Functions or classes are ok.

Create an array that holds 1000 random floats between 1-1000.

Implement Quick Sort to sort the values in ascending order. Least → Greatest

Measure the time it takes to execute the sort in milliseconds.

Please run the sort 3 times.

Attach Photos of Source Code and Output

Answer 1

#include <iostream>

#include <cstdlib>

#include <ctime>

#include <iomanip>

#include <stdio.h>

using namespace std;

void swap(float* a, float* b)

{

float t = *a;

*a = *b;

*b = t;

}

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

{

float pivot = arr[high]; // pivot

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

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

{

if (arr[j] <= pivot)

{

i++; // increment index of smaller element

swap(&arr[i], &arr[j]);

}

}

swap(&arr[i + 1], &arr[high]);

return (i + 1);

}

void quickSort(float 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(float arr[], int size)

{

int i;

for (i=0; i < size; i++)

printf("%.2f\n", arr[i]);

printf("\n");

}

int main() {

int size = 1000;

float arr[size];

int i=0;

int low = 1, high = 1000;

srand(time(0));

while (i < size)

{

arr[i] = (float)rand()/(float)(RAND_MAX/1000.0);

i++;

}

cout<<"\n\nArray Content before sorting: \n";

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

// cout<<std::fixed<<setprecision(2)<<arr[i]<<" ";

// }

int start_s=clock();

quickSort(arr, 0,size);

int stop_s=clock();

cout << "\nTime taken: " << (stop_s-start_s)/double(CLOCKS_PER_SEC)*1000 << endl;

cout<<"\n\nArray Content after sorting: \n";

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

// cout<<std::fixed<<setprecision(2)<<arr[i]<<" ";

// }

return 0;

}