Sorting Benchmarks:

The purpose of this program is to sort two identical arrays of numbers in ascending order using the bubble sort and selection sort algorithms.

Using the Searching and Sorting Source Code

//

// Lesson #11: Searching and Sorting

//

// Purpose: Code for searching and sorting arrays

// that is used for Lesson #11 and will

//#include "stdafx.h

#include

#include

#include

using namespace std;

// Function prototypes

void printArray (int array [], int size);

void initArray (int array[], int size);

int linearSearch (int array[], int size, int value);

int binarySearch (int array[], int size, int value);

void swap (int &a, int &b);

void bubbleSort (int array [], int size);

void selectionSort (int array[], int size);

int main()

{

const int ARRAY_SIZE = 20;

int numbers [ARRAY_SIZE];

// Generate array of numbers from 1 to ARRAY_SIZE

initArray(numbers, ARRAY_SIZE);

// Print out Array

printArray (numbers, ARRAY_SIZE);

// Insert code for searching and sorting

// the "numbers" array.

return 0;

}

/******************************

* Print out array elements

******************************/

void printArray (int array[], int size)

{

for (int i=0; i

cout << "array [" << i << "] = " << array [i] << endl;

cout << endl;

}

/******************************

* Initialize array with random numbers

******************************/

void initArray (int array[], int size)

{

unsigned seed = time (0);

srand(seed);

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

array [i] = 1 + rand() % size;

}

/******************************

* Linear Search

******************************/

int linearSearch (int array[], int size, int value)

{

int index = 0;

int position = -1;

bool found = false;

while (index < size && !found)

{

if (array[index] == value)

{

found = true;

position = index;

}

index++;

}

return position;

}

/******************************

* Binary Search

******************************/

int binarySearch (int arr[], int size, int value)

{

int first = 0;

int last = size -1, middle;

int position = -1;

bool found = false;

while (!found && first <= last)

{

middle = (first + last)/2;

if (arr[middle] == value)

{

found = true;

position = middle;

}

else if (arr[middle] > value)

last = middle - 1;

else

first = middle + 1;

}

return position;

}

/******************************

* Swap two values

******************************/

void swap (int &a, int &b)

{

int temp = a;

a = b;

b = temp;

}

/******************************

* Bubble Sort Algorithm

******************************/

void bubbleSort (int array [], int size)

{

int maxElement;

int index;

for (maxElement = size - 1; maxElement > 0; maxElement--)

for (index = 0; index < maxElement; index++)

if (array [index] > array [index + 1])

swap (array [index], array [index + 1]);

}

/******************************

* Selection sort algorithm

******************************/

void selectionSort (int array[], int size)

{

int minIndex, minValue;

for (int start = 0; start < (size - 1); start++)

{

minIndex = start;

minValue = array[start];

for (int index = start+1; index < size; index++)

{

if (array[index] < minValue)

{

minValue = array[index];

minIndex = index;

}

}

swap (array[minIndex], array [start]);

}

}

, modify the MAIN source code to first generate a random array of integers from 1 to 100 with 100 elements. To help you, the source code that I provide has a function called initArray that will do that for you. Create a copy of the array that gets generated so that you have two identical arrays to be sorted by both sorting functions.

Next, call the bubbleSort function with one of the arrays and report back how many exchanges were done to complete the sort (you will need to modify the bubbleSort function to keep track of the number of exchanges). Second, it should call the selectionSort function with the second (identical) array and report back how many exchanges were done to complete the sort. The results should be displayed on the screen for the user.

Make sure you include and .

#include #include #include

using namespace std;

//Bubble sort int bubbleSort(double arr[], int n) { int i, j, swapCnt=0; double temp;

//Iterating over array for (i = 0; i < n-1; i++) { // Iterating over remaining array for (j = 0; j < n-i-1; j++) { //Comparing values if (arr[j] > arr[j+1]) { //Swapping values temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp;

//Incrementing number of swaps swapCnt += 1; } } }

return swapCnt; }

//Selection sort int selectionSort(double arr[], int n) { int i, j, mIdx, swapCnt=0; double temp;

//Iterating over array for (i = 0; i < n-1; i++) { // Assume starting index is minimum mIdx = i; for (j = i+1; j < n; j++) { //Comparing and updating min index if (arr[j] < arr[mIdx]) { mIdx = j; } }

//Swapping values temp = arr[mIdx]; arr[mIdx] = arr[i]; arr[i] = temp;

//Incrementing number of swaps swapCnt += 1; }

return swapCnt; }

//Main function int main() { double l=0, h=1; double arr[200], arr1[200]; int i, bCnt, sCnt;

//Seeding random generator srand(time(NULL));

//Generating random values for(i=0; i<200; i++) { arr[i] = l + (rand() / ( RAND_MAX / (h-l) ) ); arr1[i] = arr[i]; }

//Bubble sort bCnt = bubbleSort(arr, 200); sCnt = selectionSort(arr1, 200);

cout << " For Bubble Sort, It took " << bCnt << " exchanges... "; cout << " For Selection Sort, It took " << sCnt << " exchanges... ";

return 0; }