1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
iren2701 [21]
3 years ago
13

Implement a quick sort algorithm that will accept an integer array of size n and in random order. Develop or research three diff

erent approaches as how you can pick the pivot. Write the code so the quick sort can choose among the above three different ways of picking the pivot. Run the algorithm for different sets of random data and make sure that for each set of data, you run the algorithm with all three options for the pivot selection. Record the number of key operations for each case. Report the numbers in a way that will allow you to draw a conclusion about which pivot selection approach was more efficient and how much variations you see between the different runs.
Engineering
1 answer:
Nostrana [21]3 years ago
8 0

Answer:

#include <cstdlib>  

#include <iostream>  

#include <array>  

using namespace std;  

const string APP_NAME = "Quick Sort Algorithm";  

const array<string, 3> MENU_OPTIONS = {  

"Simulate with Random data",  

"Enter data",  

"Exit program"  

};  

void printMenuOptions() {  

cout << endl << "---------------------------" << endl;  

cout << APP_NAME << endl;  

cout << "---------------------------" << endl;  

for (int i=0; i<MENU_OPTIONS.size(); i++) {  

cout << i+1 << ". " << MENU_OPTIONS[i] << endl;  

}  

cout << endl << "Select an option: ";  

}  

int getRandomInt(int min, int max) {  

return min + (static_cast<int>(rand() % (max - min + 1)));  

}  

bool inArray(int value, int* arr, int size) {  

bool found = false;  

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

if (arr[i] == value) {  

found = true;  

}  

}  

return found;  

}  

void generateRandomArrays(int size, int* arr0, int* arr1, int* arr2, int* arr3) {  

int value;  

bool ok = false;  

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

while (!ok) {  

value = getRandomInt(1, size*10);  

if (!inArray(value, arr0, size)) {  

arr0[i] = value;  

arr1[i] = value;  

arr2[i] = value;  

arr3[i] = value;  

ok = true;  

}  

}  

ok = false;  

}  

}  

void print(int* data, int size) {  

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

cout << data[i] << " ";  

}  

}  

int getPivot(int first, int last, int approach) {  

int pivot;  

switch (approach) {  

case 2:  

pivot = first;  

break;  

case 3:  

pivot = last;  

break;  

case 1:  

default:  

pivot = (first + last) / 2;  

}  

return pivot;  

}  

void swap(int* data, int i, int j) {  

int temp = data[i];  

data[i] = data[j];  

data[j] = temp;  

}  

int quickSort(int* data, int first, int last, int approach) {  

int ops = 0;  

int i = first;  

int j = last;  

int pivot = getPivot(i, j, approach);  

while (i <= j) {  

while (data[i] < data[pivot]) {  

i++;  

}  

while (data[j] > data[pivot]) {  

j--;  

}  

if (i <= j) {  

ops++;  

swap(data, i, j);  

i++;  

j--;  

}  

}  

if (j > first) {  

ops += quickSort(data, first, j, approach);  

}  

if (i < last) {  

ops += quickSort(data, i, last, approach);  

}  

return ops;  

}  

void simulate(int size, bool display) {  

int* data0 = new int[size];  

int* data1 = new int[size];  

int* data2 = new int[size];  

int* data3 = new int[size];  

int ops1, ops2, ops3;  

generateRandomArrays(size, data0, data1, data2, data3);  

ops1 = quickSort(data1, 0, size-1, 1);  

ops2 = quickSort(data2, 0, size-1, 2);  

ops3 = quickSort(data3, 0, size-1, 3);  

if (display) {  

cout << "Unsorted Array: ";  

print(data0, size);  

}  

cout << endl << endl << "> QuickSort #1: pivot is at the median" << endl;  

cout << "Swaps done: " << ops1 << endl;  

if (display) {  

cout << "Sorted Array: ";  

print(data1, size);  

}  

cout << endl << endl << "> QuickSort #2: pivot is at the start" << endl;  

cout << "Swaps done: " << ops2 << endl;  

if (display) {  

cout << "Sorted Array: ";  

print(data2, size);  

}  

cout << endl << endl << "> QuickSort #3: pivot is at the end" << endl;  

cout << "Swaps done: " << ops3 << endl;  

if (display) {  

cout << "Sorted Array: ";  

print(data3, size);  

}  

}  

void enterArray(int size, bool display) {  

// declare some variables  

int* data0 = new int[size];  

int* data1 = new int[size];  

int* data2 = new int[size];  

int* data3 = new int[size];  

int ops1, ops2, ops3;  

int value;  

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

cout << "Enter value " << i+1 << " of " << size << ": ";  

cin >> value;  

data0[i] = value;  

data1[i] = value;  

data2[i] = value;  

data3[i] = value;  

}  

ops1 = quickSort(data1, 0, size-1, 1);  

ops2 = quickSort(data2, 0, size-1, 2);  

ops3 = quickSort(data3, 0, size-1, 3);  

if (display) {  

cout << "Unsorted Array: ";  

print(data0, size);  

}  

cout << endl << endl << "> QuickSort #1: pivot is at the median" << endl;  

cout << "Swaps done: " << ops1 << endl;  

if (display) {  

cout << "Sorted Array: ";  

print(data1, size);  

}  

cout << endl << endl << "> QuickSort #2: pivot is at the start" << endl;  

cout << "Swaps done: " << ops2 << endl;  

if (display) {  

cout << "Sorted Array: ";  

print(data2, size);  

}  

cout << endl << endl << "> QuickSort #3: pivot is at the end" << endl;  

cout << "Swaps done: " << ops3 << endl;  

if (display) {  

cout << "Sorted Array: ";  

print(data3, size);  

}  

}  

int main(int argc, char** argv) {  

int choice;  

char option;  

int num;  

bool end = false;  

bool display = false;  

while (!end) {  

printMenuOptions();  

cin >> choice;  

switch (choice) {  

case 1:  

cout << endl << "Enter size of array (elements will be integers randomly generated): ";  

cin >> num;  

if (num > 0) {  

cout << "Values will be randomly generated from 1 to " << num*10 << endl;  

cout << "Do you want to display the sorted arrays? <y/N>: ";  

cin >> option;  

display = (option == 'y') ? true : false;  

simulate(num, display);  

} else {  

cout << endl << "Incorrect size." << endl;  

}  

break;  

case 2:  

cout << endl << "Enter size of array (you will enter the numbers): ";  

cin >> num;  

if (num > 0) {  

cout << "Do you want to display the sorted arrays? <y/N>: ";  

cin >> option;  

display = (option == 'y') ? true : false;  

enterArray(num, display);  

} else {  

cout << endl << "Incorrect size." << endl;  

}  

break;  

case 3:  

end = true;  

break;  

default:  

cout << endl << "Incorrect option. Try again." << endl;  

}  

}  

return 0;  

}

You might be interested in
For surface-mounted and pendant-hung luminaires, support rods should be placed so that they extend about ____
7nadin3 [17]

Answer:

One

For surface-mounted and pendant-hung luminaires, support rods should be placed so that they extend about _one___

<h3>what is supported mounted?</h3>
  • A structure that holds up or serves as a foundation for something else. Support is a synonym for mounting.

To learn more about it, refer

to brainly.com/question/25689052

#SPJ4

4 0
2 years ago
PLS HELP!!!
Advocard [28]

Answer:

I would say C

Explanation:

let me know if im right

3 0
2 years ago
Read 2 more answers
The specific volume of a system consisting of refrigerant-134a at 1.0 Mpa is 0.01 m /kg. The quality of the R-134a is: (a) 12.6%
Flura [38]

Answer:

option c is correct

47.2%

Explanation:

given data

consisting of refrigerant = 134 a

volume V = 0.01 m³/kg

pressure P = 1MPa = 1000 kPa

to find out

quality of the R 134a

solution

we will get here value of volume Vf and Vv from pressure table 60 kpa to 3 Mpa for 1 Mpa of R134 a

that is

Vf = 0.0008701 m³/kg

Vv = 0.0203 m³/kg

so we will apply here formula that is

quality = (V - Vf) / (Vv - Vf)    ............1

put here value

quality = (0.01 - 0.0008701 ) / ( 0.0203 - 0.0008701 )

quality = 0.4698

so quality is 47 %

SO OPTION C IS CORRECT

4 0
3 years ago
What does the line strung between the batter boards represent?
soldi70 [24.7K]

Batter boards (or battre boards, Sometimes mispronounced as "battle boads") are temporary frames, set beyond the corners of a planned foundation at precise elevations. These batter boards are then used to hold layout lines (construction twine) to indicate the limits (edges and corners) of the foundation.

7 0
2 years ago
Read 2 more answers
Lab scale tests performed on a cell broth with a viscosity of 5cP gave a specific cake resistance of 1 x1011 cm/g and a negligib
insens350 [35]

Answer:

5.118 m^3/hr

Explanation:

Given data:

viscosity of cell broth = 5cP

cake resistance = 1*1011 cm/g

dry basis per volume of filtrate = 20 g/liter

Diameter = 8m ,  Length = 12m

vacuum pressure = 80 kpa

cake formation time = 20 s

cycle time = 60 s

<u>Determine the filtration rate in volumes/hr  expected fir the rotary vacuum filter</u>

attached below is a detailed solution of the question

Hence The filtration rate in volumes/hr expected for the rotary vacuum filter

V' = ( \frac{60}{20} ) * 1706.0670

   = 5118.201 liters  ≈ 5.118 m^3/hr

4 0
2 years ago
Other questions:
  • A well-insulated tank in a vapor power plant operates at steady state. Saturated liquid water enters at inlet 1 at a rate of 125
    6·2 answers
  • A manufacturer makes two types of drinking straws: one with a square cross-sectional shape, and the other type the typical round
    9·1 answer
  • Plot the function for . Notice that the function has two vertical asymptotes. Plot the function by dividing the domain of x into
    5·1 answer
  • Assuming that the following three variables have already been declared, which variable will store a Boolean value after these st
    14·1 answer
  • On a hot summer day, a student turns his fan on when he leaves his room in the morning. When he returns in the evening, will the
    5·1 answer
  • B1) 20 pts. The thickness of each of the two sheets to be resistance spot welded is 3.5 mm. It is desired to form a weld nugget
    8·1 answer
  • Determine the combined moment about O due to the weight of the mailbox and the cross member AB. The mailbox weighs 3.2 lb and th
    14·1 answer
  • Gtjffs
    5·1 answer
  • . H<br> Kijwhayhwbbwyhwbwbwgwwgbwbwhwh
    6·2 answers
  • A step-up transformer has 20 primary turns and 400 secondary turns. If the primary current is 30 A, what is the secondary curren
    15·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!