-
Modified bubble sort
ok, so i have to do this
"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 son. 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"
here is the program...just looking to modify my bubblesort function.
insert
Code:
#include <iostream>
using::cout;
using::endl;
#include <iomanip>
using::setw;
int bubblesort(int[], int);
void display(int[], int);
int main()
{
const int arraySize = 10; // size of array a
int a[ arraySize ] = { 2, 6, 4, 8, 10, 12, 89, 68, 45, 37 };
cout << "Data items in original order\n";
display (a, arraySize);
bubblesort(a, arraySize);
cout << "\nData items in ascending order\n";
display (a, arraySize);
cout << endl;
return 0; // indicates successful termination
} // end main
void display(int a[], int arraySize)
{
for ( int k = 0; k < arraySize; k++ )
cout << setw( 4 ) << a[ k ];
}
int bubblesort(int a[], int arraySize)
{
int hold; // temporary location used to swap array elements
for ( int pass = 0; pass < arraySize - 1; pass++ )
{
// loop to control number of comparisons per pass
for ( int j = 0; j < arraySize - 1; j++ )
{
// compare side-by-side elements and swap them if
// first element is greater than second element
if( a[j] > a[j+1] )
{
hold = a[j];
a[j] = a[j+1];
a[j+1] = hold;
}
}
}
}
-
so what is your question?...
-
Good to see that you are posting code with code tags and have made some attempt to indent your code, but please try to keep your indentation consistent :)
Anyway, this is the crux of the matter:
Code:
int bubblesort(int a[], int arraySize)
{
int hold; // temporary location used to swap array elements
for ( int pass = 0; pass < arraySize - 1; pass++ )
{
// loop to control number of comparisons per pass
for ( int j = 0; j < arraySize - 1; j++ )
{
// compare side-by-side elements and swap them if
// first element is greater than second element
if( a[j] > a[j+1] )
{
hold = a[j];
a[j] = a[j+1];
a[j+1] = hold;
}
}
}
}
Clearly, if you want to reduce the number of comparisons, you need to modify the number of times the inner loop is run. Currently, the inner loop always runs (arraySize - 1) - 0 + 1 = arraySize times. You need to reduce this by one after each iteration of the outer loop.
-
so how would i change the bubblesort function....i really don't understand arrays
-
See this post. If you understand that algorithm, it will get you to the answer you need. http://cboard.cprogramming.com/showp...03&postcount=4
Todd