For this C++ program I have to compute the compelete pass of the bubble sort. If
ID: 3592561 • Letter: F
Question
For this C++ program I have to compute the compelete pass of the bubble sort.
If the array is 6 5 3 8
after the first pass the array should be 3 6 5 8
Can you modify my code, there is something wrong in displaying the array?
#include <iostream>
#include <iomanip>
using namespace std;
const int SIZE = 10;
const int MAX_RANGE = 30;
const int MIN_RANGE = 10;
unsigned int seed = 7;
void print_array(int []);
void bubble_sort(int []);
void swap(int&, int&);
void initialize(int []);
double random(unsigned int&);
int main ()
{
int a[SIZE];
initialize(a);
cout << " Original Array" << endl;
print_array(a);
cout << endl;
cout << " Passes Of The Bubble Sort" << endl;
bubble_sort(a);
cout << endl;
cout << " Final Array" << endl;
print_array(a);
cout << endl;
return 0;
}
void initialize(int a[])
{
for (int i = 0; i < SIZE; ++i)
a[i] = int (MIN_RANGE + (MAX_RANGE - MIN_RANGE + 1) * random(seed));
}
void swap(int &x, int &y)
{
int temp;
temp = x;
x = y;
y = temp;
}
void bubble_sort (int a[])
{
bool swapped;
do
{
swapped = false;
for (int i = 0; i < SIZE - 1; ++i)
{
if (a[i] > a [i + 1])
{
swap(a[i], a[i + 1]);
swapped = true;
}
print_array(a);
}
}while(swapped);
}
void print_array(int a[])
{
for (int i = 0; i < SIZE; ++i)
cout << setw(4) << a[i];
cout << endl;
}
double random (unsigned int & seed)
{
const int MODULUS = 15749;
const int MULTIPLIER = 69069;
const int INCREMENT = 1;
seed = ((MULTIPLIER * seed) + INCREMENT) % MODULUS;
return double (seed) / double (MODULUS);
}
Explanation / Answer
Answer. Actually, In case of bubble sort, after the first pass, the largest element should be at the last position.
If the array is 6 5 3 8, after the first pass the array should be 5 3 6 8.
As the name suggests, after each iteration, the lighter elements bubble up and the heaviest (largest) sinks down.
Also, I have done a minor change in the code to print the array after each pass.
void bubble_sort (int a[])
{
bool swapped;
do
{
swapped = false;
for (int i = 0; i < SIZE - 1; ++i)
{
if (a[i] > a [i + 1])
{
swap(a[i], a[i + 1]);
swapped = true;
}
}
print_array(a); //Moved this outside the loop
}while(swapped);
}