Modify SortingAlgos.cpp in the Code Below.

1) Implement bubbleSortSmarter which is capable of O(n) best case performance by stopping when no additional swapping needed. Add a section to the main() that calls this function.

2) Complete insertionSort and verify that it works using the section in main().

3) Count the number of comparisons and swaps performed in each of these functions: bubbleSortSmarter, selectionSort, and insertionSort. Keep a running count and print the totals at the end of each function call.

4) Add a comment in your code with the totals from step 3 and include at least 2 sentences on your observations about which algo does more comparisons or more 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;

}