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?...w hats 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.