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;
}
