A simple bubble sort algorithm is inefficient for large arrays because it continues to pass
through all elements of the array even when many of them have been sorted. Find out about
simple bubble sort algorithms (easily found on web or programming books). Write a routine
to sort the ten-number list shown in ‘Sample Screen Output’ below, and then make the
following modifications to improve the performance of the bubble sort:
a) After the first pass, the largest number is guaranteed to be in the highest-numbered element
of the array; after the second pass, the two highest numbers are “in place,” and so on. Instead
of making nine comparisons on every pass, modify the bubble sort to make eight comparisons
on the second pass, seven on the third pass, and so on.
The data in the array may already be in the proper order or near-proper order, so why make
nine passes if fewer will suffice? Modify the sort to check at the end of each pass if any swaps
have been made. If none have been made, then the data must already be in the proper order, so
the program should terminate. If swaps have been made, then at least one more pass is
needed.
I AM NOT GETTING THIS REQUIRED OUTPUT AS:
Data items in original order
2 6 4 8 10 12 89 68 45 37
After pass 0: 2 4 6 8 10 12 68 45 37 89
After pass 1: 2 4 6 8 10 12 45 37 68
After pass 2: 2 4 6 8 10 12 37 45
After pass 3: 2 4 6 8 10 12 37
After pass 4: 2 4 6 8 10 12
After pass 5: 2 4 6 8 10
After pass 6: 2 4 6 8
After pass 7: 2 4 6
After pass 8: 2 4
Data items in ascending order
2 4 6 8 10 12 37 45 68 89
Number of comparisons = 45
THIS IS WHAT I HAVE DONE SO FAR::::
CODE
#include <iostream>
#include <stdlib.h>
#include <iomanip>
using std::cout;
using std::cin;
using std::endl;
using std::setw;
int main()
{
const int size = 10;
int a[size] = {2,6,4,8,10,12,89,68,45,37};
int numberofcomparisons = 0;
//int compare;
//bool swapcheck = true;
cout << "Data items in original order\n";
for (int i =0; i<size; ++i)
cout << setw(4) << a[i];
cout <<"\n\n";
for (int count=0; count < 9; count++)
{
int temp = 0;
for (int p=0; p < 9-count; p++)
{
int q = p + 1;
if (a[p] > a[q])
{
temp = a[q];
a[q] = a[p];
a[p] = temp;
}
numberofcomparisons = numberofcomparisons +1;
}
for (int x = 0; x<size-count; ++x)
cout << setw(4)<<a[x];
}
cout << "\nData in ascending order\n";
for (int j =0; j <size; ++j)
cout << setw(4) << a[j];
cout << "\n\nNumber of comparisons = " << numberofcomparisons <<endl;
printf ("\nPress ENTER to continue.\n");
getchar ();
return 0;
}
28 Jan, 2008 - 07:20 AM
| 