Modify SortingAlgos.cpp in the code below 1) Inclue the QuickSort header 2) Usin
ID: 3740160 • Letter: M
Question
Modify SortingAlgos.cpp in the code below
1) Inclue the QuickSort header
2) Using the MergeSort section as an example, fill in the QuickSort section
3) Add comparison and swap counting to MergeSort() and QuickSort() *NOTE: print out comparisons, swaps, and total length before function exits
4) Include screenshot with output showing benchmarks for all 5 algorithms
5) Include the two headers and the Sort.cpp file with your modifications (comment your changes)
6) Include at the top of Sort.cpp at least two brief observations about the relative performance include runtime, comparisons, and swaps.
_______________________________________________________
#include
using namespace std;
// Bubble Sort (stupid edition)
void bubbleSortStupid(int arr[], int length) {
// Make N passes through arr[].
for (int i=0; i < length; i++)
// Potentially swap any given element.
for (int j=1; j < length; j++)
// Check if pairs are out of order.
if (arr[j] < arr[j - 1]) {
// Swap.
int temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
}
}
void selectionSort(int arr[], int length) {
// Make N passes through the array.
for (int i = 0; i < length; i++) {
int min_index = i; // Item which might be swapped out.
// Find the smallest (index) between i and len-1.
for (int j = i; j < length; j++)
if (arr[j] < arr[min_index]) min_index = j;
// Swap smallest with arr[i] if needed.
if (i != min_index) {
int temp = arr[i];
arr[i] = arr[min_index];
arr[min_index] = temp;
}
}
}
void insertionSort(int arr[], int length) {
// Make N passes through the array.
for (int i = 1; i < length; i++)
// Starting at i, swap pairwise until
// can't swap (it's inserted).
for (int j = i; j > 0; j--) {
// Swap if right less than left.
}
}
void printArray(int arr[], int length) {
for (int i = 0; i < length; i++)
cout << arr[i] << " ";
cout << endl;
}
int main() {
//----------------- Bubble Sort ---------------------------//
int numbers[] = { 5, 1, 7, 6, 10, 3, 4, 9, 2, 8 };
int length = sizeof(numbers) / sizeof(numbers[0]);
cout << "Length: " << length << endl;
printArray(numbers, length);
bubbleSortStupid(numbers, length);
printArray(numbers, length);
//--------------------- Selection Sort ------------------//
int numbers_ss[] = { 5, 1, 7, 6, 10, 3, 4, 9, 2, 8 };
int length_ss = sizeof(numbers_ss) / sizeof(numbers_ss[0]);
cout << "Length: " << length_ss << endl;
printArray(numbers_ss, length);
selectionSort(numbers_ss, length);
printArray(numbers_ss, length);
//--------------------- Insertion Sort ------------------//
int numbers_is[] = { 5, 1, 7, 6, 10, 3, 4, 9, 2, 8 };
int length_is = sizeof(numbers_is) / sizeof(numbers_is[0]);
cout << "Length: " << length_is << endl;
printArray(numbers_is, length);
insertionSort(numbers_is, length);
printArray(numbers_is, length);
return 0;
}
Explanation / Answer
Hi friend, You have not posted Merger Sort (as it is mentioned and Sort.cpp).
I have implemented Quick Sort:
#include <iostream>
using namespace std;
// Bubble Sort (stupid edition)
void bubbleSortStupid(int arr[], int length) {
// Make N passes through arr[].
for (int i=0; i < length; i++)
// Potentially swap any given element.
for (int j=1; j < length; j++)
// Check if pairs are out of order.
if (arr[j] < arr[j - 1]) {
// Swap.
int temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
}
}
// An optimized version of Bubble Sort
void bubbleSortSmarter(int arr[], int n)
{
int i, j;
bool swapped;
for (i = 0; i < n-1; i++)
{
swapped = false;
for (j = 0; j < n-i-1; j++)
{
if (arr[j] > arr[j+1])
{
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
// IF no two elements were swapped by inner loop, then break
if (swapped == false)
break;
}
}
void selectionSort(int arr[], int length) {
// Make N passes through the array.
for (int i = 0; i < length; i++) {
int min_index = i; // Item which might be swapped out.
// Find the smallest (index) between i and len-1.
for (int j = i; j < length; j++)
if (arr[j] < arr[min_index]) min_index = j;
// Swap smallest with arr[i] if needed.
if (i != min_index) {
int temp = arr[i];
arr[i] = arr[min_index];
arr[min_index] = temp;
}
}
}
void insertionSort(int arr[], int length) {
int key, j;
// Make N passes through the array.
for (int i = 1; i < length; 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;
}
}
// A utility function to swap two elements
void swap(int &a, int &b)
{
int t = a;
a = b;
b = t;
}
/* This function takes last element as pivot, places
the pivot element at its correct position in sorted
array, and places all smaller (smaller than pivot)
to left of pivot and all greater elements to right
of pivot */
int partition (int arr[], int low, int high)
{
int pivot = arr[high]; // 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
if (arr[j] <= pivot)
{
i++; // increment index of smaller element
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return (i + 1);
}
/* The main function that implements QuickSort
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
void quickSort(int arr[], int low, int high)
{
if (low < high)
{
/* pi is partitioning index, arr[p] is now
at right place */
int pi = partition(arr, low, high);
// Separately sort elements before
// partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
void printArray(int arr[], int length) {
for (int i = 0; i < length; i++)
cout << arr[i] << " ";
cout << endl;
}
int main() {
//----------------- Bubble Sort ---------------------------//
int numbers[] = { 5, 1, 7, 6, 10, 3, 4, 9, 2, 8 };
int length = sizeof(numbers) / sizeof(numbers[0]);
cout << "Length: " << length << endl;
printArray(numbers, length);
bubbleSortStupid(numbers, length);
printArray(numbers, length);
//--------------------- Selection Sort ------------------//
int numbers_ss[] = { 5, 1, 7, 6, 10, 3, 4, 9, 2, 8 };
int length_ss = sizeof(numbers_ss) / sizeof(numbers_ss[0]);
cout << "Length: " << length_ss << endl;
printArray(numbers_ss, length);
selectionSort(numbers_ss, length);
printArray(numbers_ss, length);
//--------------------- Insertion Sort ------------------//
int numbers_is[] = { 5, 1, 7, 6, 10, 3, 4, 9, 2, 8 };
int length_is = sizeof(numbers_is) / sizeof(numbers_is[0]);
cout << "Length: " << length_is << endl;
printArray(numbers_is, length);
insertionSort(numbers_is, length);
printArray(numbers_is, length);
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.