C++

In the bubble sort algorithm, smaller values gradually "bubble" their way upward to the top of the array like air bubbles rising in water, while the larger values sink to the bottom. The bubble sort makes several passes through the array. On each pass, successive pairs of elements are compared. If a pair is in increasing order (or the values are identical), we leave the values as they are. If a pair is in decreasing order, their values are swapped in the array.

You are given an incomplete code for this assignment. You need to complete the following tasks.

1. Implement bubble sort algorithm in the following function.

void bubbleSort(vector & v);

2. Complete test cases 3 and 4, respectively in the main() function.

for pass = 0 to size - 2

{

set Boolean variable swapped to false

for j = 0 to size 2 pass

{

if v[j] is greater than v[j+1]

{

swap v[j] with v[j+1]

set swapped to true

}

}

if no elements being swapped

break out of the loop

}

here is what i got

#include

#include

#include

using namespace std;

//Function prototypes

void bubbleSort(vector & v);

void verifyOrder(const vector & v);

void randomArray(vector & v, int size);

int main()

{

//Seed the random number generator

srand(time(0));

//Generate test array 1 of size 100

//Sort the array using bubble sort

//Verify if the sorted result is in ascending order

cout << "Testing case 1 ...... ";

vector test1;

randomArray(test1, 100);

bubbleSort(test1);

verifyOrder(test1);

//Generate test array 2 of size 500

//Sort and verify if it is in ascending order

cout << " Testing case 2 ...... ";

vector test2;

randomArray(test2, 500);

bubbleSort(test2);

verifyOrder(test2);

//Generate test array 3 of size 1000

//Sort and verifiy if it is in ascending order

cout << "Testing case 3 ...... ";

vector test3;

randomArray(test3, 1000);

bubbleSort(test3);

verifyOrder(test3);

//Generate test array 4 of size 5000

//Sort the verify if it is in ascending order

cout << "Testing case 4 ...... ";

vector test4;

randomArray(test4, 5000);

bubbleSort(test4);

verifyOrder(test4);

system("pause");

return 0;

}

//Define bubble sort here

void bubbleSort(vector & v)

{

/* Your code goes here*/

}

void verifyOrder(const vector & v)

{

bool inorder = true;

for(int i = 0; i < v.size() - 1 && inorder; i++)

{

if(v[i] > v[i+1])

inorder = false;

}

cout << "There are " << v.size() << " elements in the array. ";

if(inorder)

cout << "Passed. Your list is in order. ";

else

cout << "Failed. Your list is out of order. ";

}

//This function generate a random array of specified size

//Each element is a random value from 0 to 999

void randomArray(vector & v, int size)

{

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

v.push_back(rand() % 1000);

}