2-dimensional array bubble sort

[Acolyte]

Hey, I'm working on a project that involves sorting a two-dimensional array of integers using bubble sort. I've got it semi-working, my only issue is that it seems to be 'losing' values, I'm assuming when it gets to the end of a line in the array. It also has to run several times to get the values it keeps in completely correct order.
Here's what I've got so far:

int SortArray (int Array[][N], int a, int b)
{
        int r, c;
        float temp;
        for (r = 0; r <= a; r ++)
        {
                for (c = 0; c <= b; c ++)
                {
 
                                if (Array[r][c] > Array[r + 1][c] && r + 1 <= a)
                                {
                                temp = Array[r][c];
                                Array[r][c] = Array[r + 1][c];
                                Array[r + 1][c] = temp;
                                }
                                else if (Array[r][c] > Array[r][c + 1] && c + 1 <= b)
                                {
                                temp = Array[r][c];
                                Array[r][c] = Array[r][c + 1];
                                Array[r][c + 1] = temp;
                                }
                                else if (Array[r][c] > Array[r + 1][c + 1] && r + 1 <= a && c + 1 <= b)
                                {
                                temp = Array[r][c];
                                Array[r][c] = Array[r + 1][c + 1];
                                Array[r + 1][c + 1] = temp;
                                }
                }
        }
        PrintArray(Array, a, b);
}
 

[Ganon11]

I'm not sure about sorting 2D arrays, but I think you'll have to reconsider your algorithm. As far as I can tell, this algorithm looks at every 2x2 'block' in the array and moves the smallest value to the top left - but this isn't necessarily the smallest value in the entire array. You should be searching through the entire 2D array to find the smallest value, and switch it with the first element, then continue with the next.

Also, are a and b corresponding to the size of your array? If you have an array 10x10, are a and b 10 or 9? If they are 10, you will be accessing out of bounds areas of your array with array[10][10] (the 11th row, 11th column). If they are 9, you should be fine.

[RedSon]

Can you (in psudocode or words) describe how your algorithm is supposed to work. And please let me know what your pre and post conditions are. Like, will you accept input that is 3x4 or 8x5? How will your output be sorted?

[AdrianH]

You should compare your code against that in here. And you may want to reconsider using buble sort. :)

Also, when you say sort a 2D array, what do you mean? That the smallest numbers are put in the 0th row sorted by column until it is filled and then put the next smallest into the 1st row and so on? If so, there's no point, just make a 1D array, sort that and then access that like a 2D array.

Hope this helps.


Adrian

[RedSon]

You should compare your code against that in here. And you may want to reconsider using buble sort. :)

Also, when you say sort a 2D array, what do you mean? That the smallest numbers are put in the 0th row sorted by column until it is filled and then put the next smallest into the 1st row and so on? If so, there's no point, just make a 1D array, sort that and then access that like a 2D array.

Hope this helps.


Adrian

Hence, my question above. Can you describe what you are trying to get this algorithm to do? Also, it may be a class requirement to use bubble sort. I'm sure we can all agree that there are much better sorting algorithms.

[Acolyte]

Yeah, bubble sort is a requirement, else I'd use something more efficient.

It's a 2D array, in that is starts off as an X by Y array of random variables (The row and column variables are passed in as a and b, respectively.) I'm trying to get it to sort in increasing order.

Anyways, here's what I'm trying to get it to do:

While (cycling through the array)
If (Array[x][y] > Array(Next variable, be it next in line, or in the next row, and x + 1or y + 1 is less or equal to the length of the array)
Switch them

[RRick]

A bubble sort on a 1-D array takes 2 for loops to work. Each iteration of the inner loop takes the bottom value and filters it upward (I'm assuming a lesser to greater sort,here). Generally, this is an n ** 2 problem but there are some short cuts. For example, after the first pass, you know the last entry is correct, after the second loop, the last two entries are correct, etc.

For your 2-D case, it looks like you're going to need 4 for loops!! The inner two loops work their way through the complete matrix just once. This will force the correct value all the way to the end of the matrix. Now, you will have to do this for every cell in the array, which is what the outer two loops do. Whew!

You'll need some special logic for the last col and the last row in the matrix. You still have to check those cells but checking for cols or rows outside the matrix will only result in bugs. Also be careful who you compare the cell to. You want to compare to cells whose rows and cols are equal or one more than the current cell.

[AdrianH]

Hey, I'm working on a project that involves sorting a two-dimensional array of integers using bubble sort. I've got it semi-working, my only issue is that it seems to be 'losing' values, I'm assuming when it gets to the end of a line in the array. It also has to run several times to get the values it keeps in completely correct order.
Here's what I've got so far:

int SortArray (int Array[][N], int a, int b)
{
        int r, c;
        float temp;
        for (r = 0; r <= a; r ++)
        {
                for (c = 0; c <= b; c ++)
                {
 
                                if (Array[r][c] > Array[r + 1][c] && r + 1 <= a)
                                {
                                temp = Array[r][c];
                                Array[r][c] = Array[r + 1][c];
                                Array[r + 1][c] = temp;
                                }
                                else if (Array[r][c] > Array[r][c + 1] && c + 1 <= b)
                                {
                                temp = Array[r][c];
                                Array[r][c] = Array[r][c + 1];
                                Array[r][c + 1] = temp;
                                }
                                else if (Array[r][c] > Array[r + 1][c + 1] && r + 1 <= a && c + 1 <= b)
                                {
                                temp = Array[r][c];
                                Array[r][c] = Array[r + 1][c + 1];
                                Array[r + 1][c + 1] = temp;
                                }
                }
        }
        PrintArray(Array, a, b);
}
 

Yeah, bubble sort is a requirement, else I'd use something more efficient.

It's a 2D array, in that is starts off as an X by Y array of random variables (The row and column variables are passed in as a and b, respectively.) I'm trying to get it to sort in increasing order.

Anyways, here's what I'm trying to get it to do:

While (cycling through the array)
If (Array[x][y] > Array(Next variable, be it next in line, or in the next row, and x + 1or y + 1 is less or equal to the length of the array)
Switch them

So an array transform like this:

8 4 3    1 2 3
7 6 5 -> 2 3 7
1 2 3    5 6 8
 

An this:

1 2 3    1 1 3
1 1 3 -> 1 2 3
7 8 9    7 8 9
 

Interesting. I think I see why the use of Bubble sort. I think it is to make it faster and easier. Basic algorithm would be: Move the smallest number in each row to the left, then move the smallest number in each column to the top. Now do this to its sub-matrix who's top left is one column to the right and one column down from the original matrix. This is a recursive algorithm and it would be easiest to code it as one.

The sort time would be O(sum(n**2, where n=m to 0)) which is O(n**3) for large n. This could be better to implement it as a different sort and then fill the array from the top left outward which would be O(n log(n)) for sorting and O(n**2) for filling which would end up O(n**3 + (1 + log(n))) which would be O(n**3) for large n. However, for small n (if I have done the math right) using the bubble sort algorithm I suggested is faster, since n**2 is the over powering factor in the first and n**3 is the over powering factor in the second.

This was very interesting. Hope this helps you,


Adrian

[AdrianH]

So an array transform like this:

8 4 3    1 2 3
7 6 5 -> 2 3 7
1 2 3    5 6 8
 

An this:

1 2 3    1 1 3
1 1 3 -> 1 2 3
7 8 9    7 8 9
 

Interesting. I think I see why the use of Bubble sort. I think it is to make it faster and easier. Basic algorithm would be: Move the smallest number in each row to the left, then move the smallest number in each column to the top. Now do this to its sub-matrix who's top left is one column to the right and one column down from the original matrix. This is a recursive algorithm and it would be easiest to code it as one.

The sort time would be O(sum(n**2, where n=m to 0)) which is O(n**3) for large n. This could be better to implement it as a different sort and then fill the array from the top left outward which would be O(n log(n)) for sorting and O(n**2) for filling which would end up O(n**3 + (1 + log(n))) which would be O(n**3) for large n. However, for small n (if I have done the math right) using the bubble sort algorithm I suggested is faster, since n**2 is the over powering factor in the first and n**3 is the over powering factor in the second.

This was very interesting. Hope this helps you,


Adrian

Er, I was sort of right with the Big-O analysis. Sort time of 2D matrix sort using the algorithm I suggested would be O(sum(2*(m**2 - m), where m=2 to n)) which doesn't change the rest of my analysis.

Oh, an n represents the dimention of the array assuming that it is square. If rectangular, the Big-O results would be more complex but I'm pretty sure it would still work out better.

Adrian

[RedSon]

So an array transform like this:

8 4 3    1 2 3
7 6 5 -> 2 3 7
1 2 3    5 6 8
 

An this:

1 2 3    1 1 3
1 1 3 -> 1 2 3
7 8 9    7 8 9
 

Interesting. I think I see why the use of Bubble sort. I think it is to make it faster and easier. Basic algorithm would be: Move the smallest number in each row to the left, then move the smallest number in each column to the top. Now do this to its sub-matrix who's top left is one column to the right and one column down from the original matrix. This is a recursive algorithm and it would be easiest to code it as one.

The sort time would be O(sum(n**2, where n=m to 0)) which is O(n**3) for large n. This could be better to implement it as a different sort and then fill the array from the top left outward which would be O(n log(n)) for sorting and O(n**2) for filling which would end up O(n**3 + (1 + log(n))) which would be O(n**3) for large n. However, for small n (if I have done the math right) using the bubble sort algorithm I suggested is faster, since n**2 is the over powering factor in the first and n**3 is the over powering factor in the second.

This was very interesting. Hope this helps you,


Adrian

Given Adrian's analysis, it appears the recursive nature of this problem would lend it self to a divide-and-conquer algorithm. If you must use bubble sort, you must, but I think a more intuitive solution would be a merge sort. At least in my mind I can clearly see the logic path to get merge sort to work, whereas using for loops and bubble sorts would be a bit more...arcane?, convoluted?...whats the word I'm looking for here? Somebody help me out! Anyway, it would still be an interesting exercise to solve it with merge sort, and doing so would set you up nicely for later projects in your course where bubble sort is going to be worthless.

[AdrianH]

Given Adrian's analysis, it appears the recursive nature of this problem would lend it self to a divide-and-conquer algorithm. If you must use bubble sort, you must, but I think a more intuitive solution would be a merge sort. At least in my mind I can clearly see the logic path to get merge sort to work, whereas using for loops and bubble sorts would be a bit more...arcane?, convoluted?...whats the word I'm looking for here? Somebody help me out! Anyway, it would still be an interesting exercise to solve it with merge sort, and doing so would set you up nicely for later projects in your course where bubble sort is going to be worthless.

Actually RedSon, given my analysis, it clearly shows that Bubble Sort is not necessarily a worthless algorithm, and in fact for small n on a 2D array, it is faster and takes up less memory as it can be done in the provided memory.

When doing sorting, or anything for that matter, you should use the best tools available for the job.


Adrian

[RedSon]

Actually RedSon, given my analysis, it clearly shows that Bubble Sort is not necessarily a worthless algorithm, and in fact for small n on a 2D array, it is faster and takes up less memory as it can be done in the provided memory.

When doing sorting, or anything for that matter, you should use the best tools available for the job.


Adrian

You misunderstand me, for this particular application it is not worthless as you have demonstrated, but I am speaking to later topics in the course that this person is taking. They will soon find out that bubble sort it usually the worst algorithm for the job.

[AdrianH]

You misunderstand me, for this particular application it is not worthless as you have demonstrated, but I am speaking to later topics in the course that this person is taking. They will soon find out that bubble sort it usually the worst algorithm for the job.

Oh, ok. But it is sometimes a good idea to look at 'worthless' algorithms because they sometimes can have their uses. :)


Adrian

[teamphil06]

hi can anyone help me about my proj??
i'm 4th year h.s student...
my instructor hav me a special proj. for my failing grades...
here is my proj.
::Array of names at least 5 names, sorted alphabetically::
i'll for the response...

[RedSon]

hi can anyone help me about my proj??
i'm 4th year h.s student...
my instructor hav me a special proj. for my failing grades...
here is my proj.
::Array of names at least 5 names, sorted alphabetically::
i'll for the response...

If you have an unrelated question you need to start a new thread. Also, we are not going to do your work for you so you'd better post what you have already done to solve this problem and where you are having problems.

[Ganon11]

I think the main complication is that he's sorting a 2D array - with a 1D array, merge sort, bubble sort, quicksort, they're really all about as complicated (at least in my mind). Some are more efficient than others, but they're all about the same difficulty level for understanding.

With a 2D array, I'm not eve sure how this is supposed to be sorted yet...are each row and each column supposed to be sorted ascending from left to right/top to bottom? Is it supposed to be ascending as you read the values from left to right, top to bottom? The trouble will be defining what 'sorted' is for a 2D array, and then developing an algorithm based off a 1D sort technique.

[AdrianH]

I think the main complication is that he's sorting a 2D array - with a 1D array, merge sort, bubble sort, quicksort, they're really all about as complicated (at least in my mind). Some are more efficient than others, but they're all about the same difficulty level for understanding.

With a 2D array, I'm not eve sure how this is supposed to be sorted yet...are each row and each column supposed to be sorted ascending from left to right/top to bottom? Is it supposed to be ascending as you read the values from left to right, top to bottom? The trouble will be defining what 'sorted' is for a 2D array, and then developing an algorithm based off a 1D sort technique.

From what I gathered, a cell must contain a value less than or equal to the cells to the right of it and below it.

Anyways, here's what I'm trying to get it to do:

While (cycling through the array)
If (Array[x][y] > Array(Next variable, be it next in line, or in the next row, and x + 1or y + 1 is less or equal to the length of the array)
Switch them

Adrian

[Acolyte]

That would be correct.

[RRick]

I think the word you're looking for is slow. If bubble sorts are n**2 for 1-D arrays then they are (n**2)**2 = n**4 for 2-D arrays. The rest of you might wonder about the volumes of gab and ink about O(nlog(n)), but it comes down to one factor: speed.

You will remember the first time you run into a n**2 problem because you'll think the program hung. How could it take so long to run? The reason is because the n**2 algorithm that runs in 1 second with a 1000 entries will take almost two weeks to run with a million entries. I'm not kidding.

I had to dump a design and several days worth of work because of that misunderstanding. I started the program before the weekend and was amazed by how little was done by Monday. The next week was not a happy one, while I tried to make up for lost time.

[RedSon]

Actually I'm pretty sure I meant worthless. Re: Wikipedia

Due to its simplicity, bubble sort is often used to introduce the concept of an algorithm, or a sorting algorithm, to introductory computer science students. However, some researchers such as Owen Astrachan have gone to great lengths to disparage bubble sort and its continued popularity in computer science education, recommending that it no longer even be taught.

The Jargon file, which famously calls bogosort "the archetypical perversely awful algorithm", also calls bubble sort "the generic bad algorithm". Donald Knuth, in his famous The Art of Computer Programming, concluded that "the bubble sort seems to have nothing to recommend it, except a catchy name and the fact that it leads to some interesting theoretical problems", some of which he discusses therein.

[AdrianH]

I think the word you're looking for is slow. If bubble sorts are n**2 for 1-D arrays then they are (n**2)**2 = n**4 for 2-D arrays. The rest of you might wonder about the volumes of gab and ink about O(nlog(n)), but it comes down to one factor: speed.

You will remember the first time you run into a n**2 problem because you'll think the program hung. How could it take so long to run? The reason is because the n**2 algorithm that runs in 1 second with a 1000 entries will take almost two weeks to run with a million entries. I'm not kidding.

I had to dump a design and several days worth of work because of that misunderstanding. I started the program before the weekend and was amazed by how little was done by Monday. The next week was not a happy one, while I tried to make up for lost time.

Yes, but in this case, Bubble Sort appears to be as good or better for small n where n is the length and width of the array. The sort time would be O(sum(2*(m**2) - m, where m=2 to n)).

Where as to do the same using a O(n lg n) sort algorithm, it would be O(n**2 lg (n**2)) to sort of n**2 values + O(n**2) for the copy, which is O(2(n**2) (lg n**2)).

We are spitting hairs here because I'm not getting rid of the constants but for an n of 10 elements (i.e. a small number like I was speaking of) complexity of Bubble sort becomes 190+153+120+91+66+45+28+15+6=714 where the complexity of a 1D O(n ln n) sort with copy would be 2*100*lg(100) which is approx equal to 1329.

Not much, but not bad.


Adrian

PS sorry for post 8 in this thread, there shouldn't have been a multiplication of the Big-O for O(n log n) sort and move calculation. It should have been addition.

Also, O(n log n) is actually incorrect (looked it up in my Introduction to Algorithms text aka The Great White Whale, cuz it is friggin big white and was like our nemesis at University :)). The actual Big-O is in lg (log base 2) not the regular log base 10. O(n log n) is usually cited because for large n, it really doesn't matter.