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
Match the military operation to the category of satellite that would perform it.
SOVA2 [1]

Answer:

1. Location of enemy ground troops  - EARTH OBSERVING.

Using earth observing satellite imagery, the military can observe vast expanses of land and in so doing, find the location of enemy ground troops.

2. Routine reconnaissance of an unfamiliar climate  - WEATHER

In other to find out more about the climate of an area, a weather satellite can be used to observe the areas and its changing weather patterns.

3. Analyze waterways in an unfamiliar location  - NAVIGATION

Using navigation satellites, navigation conduits such as roads and waterways can be observed.

4. Provide warning of an attack - COMMUNICATION.

Communications satellites enable people to communicate over great distances and so can be used by the military to warn of an impending attack.

5 0
3 years ago
A 800-MW steam power plant, which is cooled by a nearby river, has a thermal efficiency of 40 percent. Determine the rate of hea
Arturiano [62]

Answer:

Rate of heat transfer to river=1200MW

So the actual amount of heat rejected ti the river will be less as there will some heat loss to surrounding and in pipes

Explanation:

In order to find the actual heat transfer rate is lower or higher than its value we will first find the rate of heat transfer to power plant:

Efficiency=\frac{work}{heat transfer to power plant}

Heat transfer=\frac{work}{Efficiency\\} \\\\Heat transfer=\frac{800}{0.40}\\\\Heat transfer=2000MW

From First law of thermodynamics:

Rate of heat transfer to river=heat transfer to power plant-work done

Rate of heat transfer to river=2000-800

Rate of heat transfer to river=1200MW

So the actual amount of heat rejected ti the river will be less as there will some heat loss to surrounding and in pipes.

4 0
3 years ago
John wants to construct a device using quartz crystal, Which device can he construct?
tatiyna

Answer: Option D, piezoelectric pressure guage

Explanation: Quartz crystal possess a very useful quality in science as they can generate small charges when pressure is applied to them or when they are hit. This property can be harnessed to construct a piezoelectric pressure gauge which would be used to measure and indicate changes in pressure, the quartz crystal releases little voltage each time there is an applied pressure . This device would be able to sense changes in pressure as there would voltage proportional to the applied pressure.

4 0
3 years ago
Read 2 more answers
A 20-mm-diameter steel bar is to be used as a torsion spring. If the torsional stress in the bar is not to exceed 110 MPa when o
ch4aika [34]

Answer:

1.887 m

Explanation:

(15 *pi)/180

= 0.2618 rad

Polar moment

= Pi*d⁴/32

= (22/7*20⁴)/32

= 15707.96

Torque on shaft

= ((22/7)*20³*110)/16

= 172857.14

= 172.8nm

Shear modulus

G = 79.3

L = Gjθ/T

= 79.3x10⁹x(1.571*10^-8)x0.2618/172.8

= 1.887 m

The length of the bar is therefore 1.887 meters

5 0
3 years ago
You will create an array manipulation program that allows the user to do pretty much whatever they want to an array. When launch
enyata [817]

Answer:

Check the explanation

Explanation:

#include <iostream>

using namespace std;

void insert(int* arr, int* size, int value, int position){

if(position<0 || position>=*size){

cout<<"position is greater than size of the array"<<endl;

return ;

}

*size = *size + 1 ;

for(int i=*size;i>position;i--){

arr[i] = arr[i-1];

}

arr[position] = value ;

}

void print(int arr[], int size){

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

cout<< arr[i] <<" ";

}

cout<<" "<<endl;

}

void remove(int* arr, int* size, int position){

* size = * size - 1 ;

for(int i=position;i<*size;i++){

arr[i] = arr[i+1];

}

}

int count(int arr[], int size, int target){

int total = 0 ;

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

if(arr[i] == target)

total += 1 ;

}

return total ;

}

int main()

{

int size;

cout<<"Enter the initial size of the array:";

cin>>size;

int arr[size],val;

cout<<"Enter the values to fill the array:"<<endl;

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

cin>>val;

arr[i] = val ;

}

int choice = 5,value,position,target ;

do{

cout<<"Make a selection:"<<endl;

cout<<"1) Insert"<<endl;

cout<<"2) Remove"<<endl;

cout<<"3) Count"<<endl;

cout<<"4) Print"<<endl;

cout<<"5) Exit"<<endl;

cout<<"Choice:";

cin>>choice;

switch(choice){

case 1:

cout << "Enter the value:";

cin>>value;

cout << "Enter the position:";

cin>>position;

insert(arr,&size,value,position);

break;

case 2:

cout << "Enter the position:";

cin>>position;

remove(arr,&size,position);

break;

case 3:

cout<<"Enter the target value:";

cin>>target;

cout <<"The number of times "<<target<<" occured in your array is:" <<count(arr,size,target)<<endl;

break;

case 4:

print(arr,size);

break;

case 5:

cout <<"Thank you..."<<endl;

break;

default:

cout << "Invalid choice..."<<endl;

}

}while(choice!=5);

return 0;

}

Kindly check the attached images below for the code output.

3 0
3 years ago
Other questions:
  • 11.A heat engine operates between two reservoirs at 800 and 20°C. One-half of the work output of the heat engine is used to driv
    6·1 answer
  • Do all websites use the same coding to create?
    8·1 answer
  • all of the following are steps in the problem solving process except a. try, b. reflect, c. debug, d. define
    11·1 answer
  • A piston–cylinder device containing carbon dioxide gas undergoes an isobaric process from 15 psia and 80°F to 170°F. Determine t
    15·1 answer
  • PLS HELP ME
    14·1 answer
  • Omplete the following program: [0.5 X 4 = 2]
    11·1 answer
  • A school is playing $0.XY per kWh for electric power. To reduce its power bill, the school installs a wind turbine with a rated
    6·1 answer
  • Which of the following sensors is used to provide suspension control module with feedback regarding vehicle cornering​ forces?
    8·1 answer
  • At time t the resultant force on a particle, of mass 250kg is (300ti-400tj)N. Initially, the particle is at the origin and is mo
    6·1 answer
  • How frequently should vehicle registration be renewed?
    6·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!