Need help C++ Functions or classes are ok. Initialize the an array from the Valu
ID: 3729924 • Letter: N
Question
Need help C++
Functions or classes are ok.
Initialize the an array from the Values Mostly Sorted Descending.
Implement Selection 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.
update code from implementation quick sort to
implementation selection sort
#include <iostream>
#include <stdlib.h> /* srand, rand */
#include <time.h>
#include <chrono>
using namespace std;
void quick_sort (float arr[], int low, int high); //declare quick_sort() function
int
main ()
{
float arr[1000];
for (int i = 0; i < 1000; i++)
arr[i] =
1 + static_cast < float >(rand ()) / (static_cast <
float >(RAND_MAX / (1000)));
int i, j, n = 1000;
float key;
for (int k = 0; k < 3; k++)
{
auto begin = chrono::steady_clock::now ();
clock_t t;
t = clock ();
#if 0
/* Commented your sorting algorithm */
for (i = 1; i < n; i++)
{
key = arr[i];
j = i - 1;
/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j >= 0 && arr[j] > key)
{
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
#endif /*
*/
quick_sort (arr, 0, n - 1);
auto end = chrono::steady_clock::now ();
cout << "Elapsed time in milliseconds : " << chrono::duration_cast <
chrono::milliseconds > (end - begin).count () << " ms" << endl;
}
// getchar(); //Added getchar() to stop executing and take the output.. Remove this line
for (i = 0; i < 1000; i++)
cout << arr[i] << endl;
}
void
swap_entries (float *a, float *b)
{
float temp = *a; //Read a in temp
*a = *b; //Make a = b
*b = temp; // Make b = temp
}
/* The partition function takes a pivot element and finds its correct position. After that it puts the elements less than it to the left of it and elements greater than it are placed to the right of it. */
int
partition (float arr[], int low, int high)
{
float pivot = arr[high]; // here we are assuming the last element as 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, then replace the element with pivot */
if (arr[j] <= pivot)
{
++i; // increment index of smaller element
swap_entries (&arr[i], &arr[j]); //swap lowest element with j
}
}
swap_entries (&arr[i + 1], &arr[high]); // swap the lowest element with the pivot element
return (i + 1); //Return position of lowest element
}
/* The quick_sort function takes three arguments.
arr[] --> Array to be sorted, low --> Starting index of array, high --> Ending index of array*/
void
quick_sort (float arr[], int low, int high)
{
if (low < high) // If low is less than high, then partition the array and do sort on it
{
/* index is partitioning index, arr[p] is now at right place */
int index = partition (arr, low, high);
// Separately sort elements before partition and after partition
quick_sort (arr, low, index - 1);
quick_sort (arr, index + 1, high);
}
}
Explanation / Answer
Please find the code in the following link:
https://paste.ubuntu.com/p/8YSdPp4xNX/
The array has been initialized with random values as in above code. Then, it is reverse sorted and then selection sort algorithm is applied 3 times on it. The main function is almost the same as above.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.