main.cpp

#include

#include "library.h"

using namespace std;

/*

Modify the sorting functions in library.cpp according to the prompts from the assignment.

Update the content for the test array and/or use additional arrays to test the three sorting functions. Look for patterns of best/worst case scenarios regarding the number of comparisons and swaps.

*/

int main() {

int test[] = {18, 13, 11, 20, 14};

int nElem = sizeof(test) / sizeof(int);

bubble_sort(test,nElem);

display(test, nElem);

}

library.cpp

#include //for cout

#include //for swap

#include "library.h"

using namespace std;

/*

Update this function so that it would display the number of comparisions, the number of updates on min_index, and the intermediate array content for each pass of the outer loop.

*/

void selection_sort(int a[], int n) {

for (int j = 0; j

int min_index = j;

int compare = 0;

int swap = 0;

for (int i = j + 1; i

if (a[i]

min_index = i;

}

}

swap(a[j], a[min_index]);

}

}

/*

Update this function so that it would sort the array in descending order, i.e. the largest would be in a[0] and the smallest would be in a[n - 1].

In addition, it would display the number of comparisions, the number of swaps, and the intermediate array content for each pass of the outer loop.

*/

void bubble_sort(int a[], int n) {

for (int j = n + 1; j > 1; j--){

for (int i = 0; i > j; i++) {

if (a[i] > a[i - 1]) {

swap(a[i], a[i-1]);

}

}

}

}

/*

Update this function so that it would start sorting at the end rather than the beginning of the array.

In addition, it would display the number of comparisions, the number of swaps, and the intermediate array content for each pass of the outer loop.

*/

void insertion_sort(int a[], int n) {

for (int j = 1; j

bool done = false; //done moving a[j] up

for (int i = j; i > 0 && !done; i--) {

if (a[i]

swap(a[i], a[i - 1]);

} else {

done = true;

}

}

}

}

/*

Call this function inside the sorting functions to display intermediate array content at the end of each pass of the outer loop.

*/

void display(const int a[], int n) {

for (int i = 0; i

cout

}

cout

}

library.h

//This file contains the prototypes of the sorting functions. Do not change.

void bubble_sort(int a[], int n);

void selection_sort(int a[], int n);

void insertion_sort(int a[], int n);

void display(const int a[], int n);

code is in C++

This lab asks you to modify the three sorting algorithms discussed in class. These sorting algorithms are independent from each other. Focus on one function at a time. You may choose which function you want to implement and test first. Be sure to test thoroughly with different initial array elements and look for patterns of best/worst case scenarios for each sorting algorithm. void selection_sort(int a[], int n); This function sorts the first n elements of an array into ascending order. Your task is to modify the function so that it would display the number of comparisons, the number of updates to min_index, and the intermediate array content for each pass of the outer loop. Below is one sample testing of the function: selection sort, before sorting: 18 13 11 20 14 Pass 1: 4 comparisons and 2 updates to min_index. The array is now: 11 13 18 20 14 Pass 2: 3 comparisons and O updates to min_index. The array is now: 11 13 18 20 14 Pass 3: 2 comparisons and 1 updates to min_index. The array is now: 11 13 14 20 18 Pass 4: 1 comparisons and 1 updates to min_index. The array is now: 11 13 14 18 20 End of selection sort. void bubble_sort (int a[], int n); This function is currently sorting the first n elements of an array into ascending order. That is, the smallest value would end up in a[0] while the largest value would end up in a[n - 1]. Your task is to modify the function so that it would sort the first n elements of an array into descending order. That is, the largest value would end up in a[O] while the smallest value would end up in a[n - 1). In addition, the function needs to display the number of comparisons, the number of swaps, and the intermediate array elements for each pass of the outer loop. Below is one sample testing of the function: Bubble sort, before sorting: 18 13 11 20 14 Pass 1: 4 comparisons and 2 swaps. The array is now: 18 13 20 14 11 Pass 2: 3 comparisons and 2 swaps. The array is now: 18 20 14 13 11 Pass 3: 2 comparisons and 1 swaps. The array is now: 20 18 14 13 11 End of bubble sort