Bubble sort algorithm doesn't work...

[EZX]

Im trying to make a bubble sort algorithm for this excersise about massives but it just doesn't work. Think i have lost like 3 hours on this one, seriously.

Here is the code:

#include <iostream.h>
#include <conio.h>
#include <math.h>
#include <stdlib.h>
int main ()
{
randomize();
int a[50][50];
int i,j, n, m;
int pag;
 cout<<"Input N : ";
   cin>>n;
   cout<<"Input M: ";
   cin>>m;
   for(i=0; i<n; i++){
   	for(j=0; j<n; j++){
      a[i][j]=random(10);
      cout<<a[i][j]<<" ";
        }
      cout<<"\n";
        }

   for(i=0; i<n; i++){
      for(j=0; j<n; j++){
        if (a[i][j] > a[i][j+1])
      {
       pag = a[i][j+1];
        a[i][j+1] = a[i][j];
        a[i][j] = pag;
        }
        }
        }
    for(i=0; i<n; i++){
      for(j=0; j<n; j++){
     cout<<a[i][j]<<" ";
     }
     }

getch();
}

What should i fix to make it work?

[toum]

I never understood why teachers always use bubble sort as an example. Algorithms like insertion sort or the "min sort" (don't know the real name) are easier to understand.

The problem in your code happens when you swap two elements. After the swap, the element at index [i][j] is smaller than the element at [i][j+1], but it's not necessarily bigger than all the elements before.

An example will make it clear :
Let's say our array contains 3 values : 3 2 1
First comparison : 3 and 2. Since 3 > 2, you swap them. Your array becomes 2 3 1.
Next comparison : 3 and 1. Since 3 > 1, you swap them. You array becomes 2 1 3.
The algorithm ends. The only correctly ordered element is the biggest one.

In a more general case, the only thing your code guarantees is that the biggest element will be placed at the last position.

If you want to sort the whole array, you have to repeat your sorting loop as many times as there are elements in your array.

Also, you should note that your code reads a[i][n], which it shouldn't.
If j+1 must be smaller than n, then j must be smaller than n-1.

Here is a code that should work :

int k;
for(i=0; i<n; i++){
    for(k=0; k<n; k++){
        for(j=0; j<n-1; j++){
            if (a[i][j] > a[i][j+1])
           {
                pag = a[i][j+1];
                a[i][j+1] = a[i][j];
                a[i][j] = pag;
           }
        } // loop on j
    } // loop on k
}

ps:
the "min sort" algorithm mentionned is this one :
- find the smallest value of your array. It is the first ordered value.
- remove it from the array
- find the smallest value of the remaining values. It is the second ordered value.
- remove it from the array
- ...

in pseudo C-code:

for(k=0;k<n;k++)
{
    // find the smallest element between indices k and n-1
    // swap it with element at index k
}

I find it much simpler to understand.
It's also a good programming exercise because you can write it both iteratively and recursively.



Edit : what I called "min sort" is in fact known as Selection Sort