Bubble Sort for 2D Array in C++ [closed]

Question

Closed. This question needs details or clarity. It is not currently accepting answers.

---

Want to improve this question? Add details and clarify the problem by editing this post.

Closed 9 years ago.

Improve this question

I'm trying to sort all 2D array elements in c++ using bubble sort, but I can't figure it out.

#include <iostream>
#include <stdio.h>
using namespace std;
int main (){    

int x[4][4],i,k,j;
for(i=0;i<4;i++)
    for(j=0;j<4;j++)
        cin>>x[i][j];

cout<<"\n\n";

for(i=0;i<4;i++)
    for(j=0;j<3;j++)
        for(k=j+1;k<4;k++)
            if(x[i][j]>x[i][k])
            {
                int temp = x[i][j];
                x[i][j] = x[i][k];
                x[i][k] = temp;
            }           

for(i=0;i<4;i++)
    {
    for(j=0;j<4;j++)
        cout<<x[i][j]<<"\t";
        cout<<"\n\n";       
    }


cout<<endl;
return 0;
}

The thing is, I'm not sure if these elements are sorting correctly. I think I should just put another for loop somewhere, but I don't know where.

Also, is it possible to minimize the code above to use only 2 for loops? I thought that I could but I wasn't exactly sure how I'd do it because the elements of 'j' must be less than 1.

My main problem here though is just sorting all of the elements.

Answer 1

You can look at the below which may be surprising, bu works fine, but using qsort instead of bubble sort...

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
int myfunction (int* i,int* j) { return (*i>*j); }
int main (){    
   int x[4][4],i,k,j;
   for(i=0;i<4;i++)
      for(j=0;j<4;j++)
         x[i][j] = random()%1000;

   qsort((void*)x, 16, sizeof(int),(int (*)(const void*,const void*))myfunction);

   for(i=0;i<4;i++) {
      for(j=0;j<4;j++)
          cout<<x[i][j]<<"\t";
      cout<<"\n\n";       
   }
}

There is a trick here, in as that we are just sorting a one-dimensional array using qsort. The trick is possible because the memory layout of x[4][4] is 16 consecutive integers, so you can access just as if it was declared as x[16] -- and you can use this fact to also implement a traditional bubble sort, just casting int y = (int)x; and then sorting y from (0..15) as it was a one dimensional array.

However I would not recommend this if you are a novice to intermediate programmer in C/C++, as you probably will get it horribly wrong -- also you probably will not get any performance gains in doing so, as the optimizer is pretty good and unrolling loops, and the modern pipe-line CPU are very fast in executing tight loops like your above.

Update

As a bubble sort, the following works with only two loops;

for(i=0;i<16;i++)
  for(j=i;j<16;j++)
    if(x[i/4][i%4]>x[j/4][j%4])
    {
        int temp = x[i/4][i%4];
        x[i/4][i%4] = x[j/4][j%4];
        x[j/4][j%4] = temp;
    }  

If you do insist on having individual loops of each dimension, then this is the right way;

for (int ia=0; ia <4; ia++)
  for (int ja=0; ja <4; ja++)
    for (int ib=0; ib <4; ib++)
      for (int jb=0; jb <4; jb++)
        if(x[ia][ib]<x[ja][jb])
        {
            int temp = x[ia][ib];
            x[ia][ib] = x[ja][jb];
            x[ja][jb] = temp;
        }  

Answer 2

This code isn't proper C++, let me point out a thing:

For this:

int temp = x[i][j];
x[i][j] = x[i][k];
x[i][k] = temp;

C++ has a built-in function, std::swap, declared in header algorithm, so you can use:

std::swap(x[i][j], x[i][k]);

Now, for the algorithm. If you input a matrix like this:

16 8 3 2
4 5 15 10
11 12 13 14
1 6 9 7

It should output

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

Nothing new.

The sorting algorithm should look something like this:

for (int i = 0; i < 4; i++) {
    for (int j = 0; j < 4; j++) {
        int m = i;
        int n = j + 1;
        while (true) {
            if (n == 4) {
                n = 0;
                m++;
                if (m == 4) break; // Stopping condition: n == 4 && m == 4
            }

            if (x[i][j] > x[m][n]) std::swap(x[i][j], x[m][n]);

            n++;
        }
    }
}