Number of exchanges in a bubble sort

S

SneakyElf

I have an array and a bubble sort, how to i keep track of the amount
of swaps that my program makes and displays it in the end?

here's my code so far. everything is done except for the count of
exchanges that are made:

#include <iostream>
using namespace std;

const int MAXSIZE = 20;

void bubbleSort ( int arr [ ], int size );
void swap ( int* x, int* y );

int main()
{
int numbers[MAXSIZE] = { 13, 5, 1, 7, 9, 11, 3, 17, 19, 15, 1,
9, 78, 4, 22, 90, 18, 65, 89, 33};
int index;

cout << "BEFORE SORT: ";
for (index = 0; index < MAXSIZE; index++)
cout << numbers[index] << " ";

bubbleSort(numbers, MAXSIZE); // perform sort routine

cout << endl << endl << "AFTER SORT.: ";
for (index = 0; index < MAXSIZE; index++)
cout << numbers[index] << " ";

cout << endl << endl;

system("PAUSE");
return EXIT_SUCCESS;
}

// bubble sort technique defined for ascending order
void bubbleSort ( int arr [ ], int size )
{
int last = size - 2;
int isChanged = 1, k;

while ( last >= 0 && isChanged )
{
isChanged = 0;
for ( k = 0; k <= last; k++ )
if ( arr[k] > arr[k+1] )
{
swap ( &arr[k], &arr[k+1] );
isChanged = 1;
}
last--;
}
}

// interchanges values of two integer variables
void swap ( int* x, int* y )
{
int temp;
temp = *x;
*x = *y;
*y = temp;

}
 
J

Jerry Coffin

I have an array and a bubble sort, how to i keep track of the amount
of swaps that my program makes and displays it in the end?

here's my code so far. everything is done except for the count of
exchanges that are made:

The number of exchanges is the number of times 'swap' gets called, so
you probably want to write a version of swap that keeps track of how
often it's called. It could (for example) return the number of times
it's been called -- even though most of the time you'd ignore the return
value. Another possibility would be to change it from a function to a
function object with another member function to return the number of
times it's been used.
 
?

=?ISO-8859-15?Q?Erik_Wikstr=F6m?=

The number of exchanges is the number of times 'swap' gets called, so
you probably want to write a version of swap that keeps track of how
often it's called. It could (for example) return the number of times
it's been called -- even though most of the time you'd ignore the return
value. Another possibility would be to change it from a function to a
function object with another member function to return the number of
times it's been used.

Or even simpler, since swap is only called from one place in bubbleSort,
is to count the number of times it is called by incrementing the counter
before/after the call to swap.
 
?

=?ISO-8859-1?Q?Erik_Wikstr=F6m?=

I have an array and a bubble sort, how to i keep track of the amount
of swaps that my program makes and displays it in the end?

here's my code so far. everything is done except for the count of
exchanges that are made:

#include <iostream>
using namespace std;

const int MAXSIZE = 20;

Generally, all uppercase names are reserved for macros.
void bubbleSort ( int arr [ ], int size );
void swap ( int* x, int* y );

int main()
{
int numbers[MAXSIZE] = { 13, 5, 1, 7, 9, 11, 3, 17, 19, 15, 1,
9, 78, 4, 22, 90, 18, 65, 89, 33};
int index;

cout << "BEFORE SORT: ";
for (index = 0; index < MAXSIZE; index++)
cout << numbers[index] << " ";

Generally you want to minimize the scope of variables so move the
declaration of the loop-variable (index) inside the for-loop:

int numbers[MAXSIZE] = { /* ... */ };

cout << "BEFORE SORT: ";
for (int index = 0; index < MAXSIZE; ++index)
cout << numbers[index];

Notice also the use of ++index, instead of index++. For a normal integer
this does not matter but when using iterators it can (putting ++ before
can be faster) so I make a habit of always using that form.

Also, I tend to name loop variables simply to i, j, etc. That way I can
see from the name that it is a loop variable and not some other kind of
variable.
bubbleSort(numbers, MAXSIZE); // perform sort routine

cout << endl << endl << "AFTER SORT.: ";
for (index = 0; index < MAXSIZE; index++)

for (int index = 0; index < MAXSIZE; ++index)
cout << numbers[index] << " ";

cout << endl << endl;

system("PAUSE");
return EXIT_SUCCESS;
}

// bubble sort technique defined for ascending order
void bubbleSort ( int arr [ ], int size )
{
int last = size - 2;
int isChanged = 1, k;

I try to make only one declaration per line, makes the code cleaner (in
my opinion) and avoids problems with pointers. Also look into the type
bool to replace the above line with:

bool isChanged = true;
while ( last >= 0 && isChanged )
{
isChanged = 0;

isChanged = false;
for ( k = 0; k <= last; k++ )

for (int k = 0; k <= last; ++k)
if ( arr[k] > arr[k+1] )
{
swap ( &arr[k], &arr[k+1] );

Look into using std::swap() said:
isChanged = 1;

isChanged = true;
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,901
Latest member
Noble71S45

Latest Threads

Top