Update/change the source code provided with the new task listed below. Change th
ID: 3729837 • Letter: U
Question
Update/change the source code provided with the new task listed below. Change the insertion sort to quick sort. Pls add conventional comments to explain code!
/*
To calculate time you need to put function call between start and end time of system.
So Took the current system time in a begin variable and called function and took the end time
in end_time variable after that I calculated time and printed.
I implemented insertion sort function.
Sample Output:
Time: 1.00 milliseconds*/
#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include <ctime>
using namespace std;
/* Function to sort an array using insertion sort*/
void insertionSort(float arr[], int size) {
int i,j;
float temp;
//Loop on unsorted array
for(i=1; i<size; i++) { //Loop on sorted array and finding position to place number
temp=arr[i];
j=i-1;
while((temp<arr[j]) && (j>=0)) { //Adjusting all greater elements then temp to the right
arr[j+1]=arr[j];
j=j-1;
}
arr[j+1]=temp; //Placing new element at right palace
}
}
int main() {
float arr[1000]; //Declaring array of float type
//Generating array of 1000 float value
for(int i=0;i<1000;i++) {
arr[i]=((1000-1) * ((float)rand() / 1000)) + 1;
}
const clock_t begin_time = clock(); //Starting time
insertionSort(arr,1000); //Calling function
const clock_t end_time = clock(); //Ending times
//Calculating time
//1000 is multiplied to convert seconds to milliseconds
float time=1000*float(end_time-begin_time)/CLOCKS_PER_SEC;
//Displaying time
printf("Time: %.2f milliseconds",time);
return 0;
}
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 OutputExplanation / Answer
// An iterative implementation of quick sort
#include <stdio.h>
#include<iostream>
#include<stdlib.h>
#include <ctime>
// A utility function to swap two elements
void swap (float *a, float *b)
{
float t = *a;
*a = *b;
*b = t;
}
/* This function is same in both iterative and recursive*/
int partition (float arr[], int l, int h)
{
int x = arr[h];
int i = (l - 1);
for (int j = l; j <= h - 1; j++)
{
if (arr[j] <= x)
{
i++;
swap (&arr[i], &arr[j]);
}
}
swap (&arr[i + 1], &arr[h]);
return (i + 1);
}
/* A[] --> Array to be sorted,
l --> Starting index,
h --> Ending index */
void quickSortIterative (float arr[], int l, int h)
{
// Create an auxiliary stack
int stack[h - l + 1];
// initialize top of stack
int top = -1;
// push initial values of l and h to stack
stack[++top] = l;
stack[++top] = h;
// Keep popping from stack while is not empty
while (top >= 0)
{
// Pop h and l
h = stack[top--];
l = stack[top--];
// Set pivot element at its correct position
// in sorted array
int p = partition (arr, l, h);
// If there are elements on left side of pivot,
// then push left side to stack
if (p - 1 > l)
{
stack[++top] = l;
stack[++top] = p - 1;
}
// If there are elements on right side of pivot,
// then push right side to stack
if (p + 1 < h)
{
stack[++top] = p + 1;
stack[++top] = h;
}
}
}
// A utility function to print contents of arr
void printArr (float arr[], int n)
{
int i;
for (i = 0; i < n; ++i)
printf ("%f ", arr[i]);
}
// Driver program to test above functions
int main ()
{
float arr[1000]; //Declaring array of float type
//Generating array of 1000 float value
for (int i = 0; i < 1000; i++)
{
// arr[i] = ((10 - 1) * ((float) rand () / 10)) + 1;
arr[i]=rand() % 1000 + 1;
//printf ("%f ", arr[i]);
}
const clock_t begin_time = clock (); //Starting time
int n = sizeof( arr ) / sizeof( *arr );
quickSortIterative( arr, 0, n - 1 );
printArr( arr, n );
//insertionSort (arr, 1000); //Calling function
const clock_t end_time = clock (); //Ending times
//Calculating time
//1000 is multiplied to convert seconds to milliseconds
float time = 1000 * float (end_time - begin_time) / CLOCKS_PER_SEC;
//Displaying time
printf ("Time: %.2f milliseconds", time);
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.