bubble sort - two dimensional array - c++

[cdoublesyou]

any code for bubble sorting a two dimensional array in c++ would be greatly apreciated!

 

[ChiHappens]

a bubble sort is really simple (and quite effective)

#include <iostream>
#include <ctime>
#include <conio.h>
//---------------------------------------------------------------------------

using namespace std;
//---------------------------------------------------------------------------
// Globals
const int MAX_X = 10;
const int MAX_Y = 10;
//---------------------------------------------------------------------------
// Function Prototypes
void DisplayTheArray(const int [][MAX_Y]);
void BubbleSort(int [][MAX_Y]);
void RandomizeTheArray(int [][MAX_Y]);
//---------------------------------------------------------------------------

void DisplayTheArray(const int anArray[][MAX_Y])
{
for(int y=0; y<MAX_Y; y++)
{
for(int x=0; x<MAX_X;x++)
{
cout.width(5);
cout << anArray[x][y];
}
cout << endl;
}
cout << endl;
}
//---------------------------------------------------------------------------

void BubbleSort(int anArray[][MAX_Y])
{
int x,y;
int tItem, PassCount;
bool HasChanged;

for(PassCount=0;PassCount < (MAX_X*MAX_Y);PassCount++)
{
// first sort the Xs
for(y=0;y<MAX_Y;y++)
{
HasChanged = true;
while(HasChanged)
{
HasChanged = false;
for(x=1;x<MAX_X;x++)
{
if(anArray[x-1][y] > anArray[x][y])
{
HasChanged = true;
tItem = anArray[x-1][y];
anArray[x-1][y] = anArray[x][y];
anArray[x][y] = tItem;
}
}
}
}
// Next sort the Ys
for(x=0;x<MAX_X;x++)
{
HasChanged = true;
while(HasChanged)
{
HasChanged = false;
for(y=1;y<MAX_Y;y++)
{
if(anArray[x][y-1] > anArray[x][y])
{
HasChanged = true;
tItem = anArray[x][y-1];
anArray[x][y-1] = anArray[x][y];
anArray[x][y] = tItem;
}
}
}
}
}
}
//---------------------------------------------------------------------------

void RandomizeTheArray(int anArray[][MAX_Y])
{
for(int x=0;x<MAX_X;x++)
{
for(int y=0;y<MAX_Y;y++)
{
anArray[x][y] = (1 + rand() % 100);
}
}
}
//---------------------------------------------------------------------------

int main(void)
{
int theArray[10][10];
srand(time(0));
RandomizeTheArray(theArray);
cout << &quot;Before Bubble Sort&quot; << endl;
DisplayTheArray(theArray);
BubbleSort(theArray);
cout << &quot;After Bubble Sort&quot; << endl;
DisplayTheArray(theArray);
getch();
return 0;
}
//---------------------------------------------------------------------------


Chi Happens

Chi Happens
&quot;When you know and respect your own inner nature, you know where you belong. You also know where you don't belong&quot; - Benjamin Hoff

 

[cdoublesyou]

thanks for the help! can you show me how you would read an input file into the array?

 

[ChiHappens]

ah, it's pretty simple to open a file and read the contents. not much to that algorithm. i think i'll let you figure that out on your own.

hint: use fstream

Chi Happens

Chi Happens
&quot;When you know and respect your own inner nature, you know where you belong. You also know where you don't belong&quot; - Benjamin Hoff

 

[lionelhill]

No, I strongly recommend you don't do this. A bubble sort is effective in that it sorts your data for minimum programmer-effort, but it scales very badly as the amount of data to sort goes up. It is one of the least efficient sort algorithms in existance.

Your application looks like one that will bring out the worst in bubble-sort as 2-d arrays aquire data at quite an alarming rate as their side-length increases.

 

[ChiHappens]

lionelhill,
Certainly there are other, and more effecient sorting techniques like Radix Sort, but that isn't what was asked for.

Here is a simple chart to compare the sorts:

SORT WORST CASE AVERAGE
Selection Sort n^2 n^2
Bubble Sort n^2 n^2
Insertion Sort n^2 n^2
QuickSort n^2 n * log n
TreeSort n^2 n * log n
RadixSort n n
MegeSort n * log n n * log n
HeapSort n * log n n * log n

(note: bubble sort is listed second, but speed in among the slowest)

Chi Happens
&quot;When you know and respect your own inner nature, you know where you belong. You also know where you don't belong&quot; - Benjamin Hoff

 

[lionelhill]

ChiHappens, I'm not criticising you for answering the question, but I am questioning the questioner! Everyone's heard of bubblesort because it's in all the textbooks, but that doesn't make it good. I quote from Press et al &quot;Numerical recipes in C&quot; 2nd ed., page 330

&quot;We will draw the line, however, at the inefficient N^2 algorithm, beloved of elementary computer science texts, called bubble sort. If you know what bubble sort is, wipe it from your mind; if you don't know, make a point of never finding out!&quot;

These authors are good enough for me.

Addendum to your 2nd reply: quicksort's worst case is usually a properly sorted data set! This is worth knowing, and avoiding.

 

[ChiHappens]

lionelhill

understood. thanks for the additional info.


Chi Happens
&quot;When you know and respect your own inner nature, you know where you belong. You also know where you don't belong&quot; - Benjamin Hoff

 

[nopscti]

What does the line &quot;bool HasChanged&quot; mean?

Obviously, HasChanged is the a type of data, but what kind?
Is it a boolean variable (i.e 0 or 1)?

Thanks

nopscti

 

[ChiHappens]

Yeah its a boolean value. in c++ a boolean value is defined by the keyword bool. it can be represented as zero and non-zero, or better yet, using TRUE and FALSE.

It is used in the bubble sort to know when to exit.

Hope this helps,
Chi Happens

Chi Happens
&quot;When you know and respect your own inner nature, you know where you belong. You also know where you don't belong&quot; - Benjamin Hoff