Sorting a Multidimensional Array

[k88]

hi I've been stuck trying to figure out how to sort with the bubble sort method and without using pointers this multimendional array that is filled with random numers, I dont want to use the sort function. But I still dont know whats wrong with this code. What i can't seem to figure out is how to repeat examining the array to swap values and get an ordered array until there's no more value to swap since its already sorted.

here's my code:

#include <iostream>
#include<stdlib.h>
#include<time.h>

using namespace std;

int main()
{
int n,m,temp;
int sum=0;
cout<<"n"<<endl;
cin>>n;
cout<<" m"<<endl;
cin>>m;
int arr[n][m];
srand(time(NULL));
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
arr[i][j]=rand()%100;
cout<<arr[i][j]<<" ";
}
cout<<endl;
}
for(int i=0;i<n;i++)
{
do{
sum=0;

for(int j=0;j<m;j++)
{
if(arr[i][j]>arr[i+1][j+1])
{
temp=arr[i][j];
arr[i][j]=arr[i+1][j+1];
arr[i+1][j+1]=temp;
sum++;
}
}
}while(sum>0);

}
cout<<endl;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cout<<arr[i][j]<<" ";
}
cout<<endl;
}
return 0;
}

[Ganado]

First, please format your code. Edit your post and put [code] and [/code] around your code snippet.

Second, what is wrong? Is it not compiling? Does it get the wrong result? Be specific.

Third, what does it mean to sort a multidimensional array? It's ambiguous what you want.

For example, if the input is
{ {7, 5, 3}, {8, 3, 2} }, what should the output be?

{ {2, 3, 8}, {3, 5, 7} } ?
{ {2, 3, 3}, {5, 7, 8} } ?

The program will do exactly what you tell it to do. But you have to know what you want to tell it.

[tpb]

What exactly do you mean by "sort a multidimensional array"?

If the original array is:

 6 10  7  2
 9  3 12 11
 5  8  4  1

what would the output be?

[k88]

Sorry for not being specific .

This is what I mean:

1 2 3 4
5 6 7 8
9 10 11 12


oh and I forgot to mention , i dont want to use the function sort ,I wanted to try and do it without using it.
And the problem is that i keep getting the wrong result.

[poteto]

Can't you treat the 2d array as a 1d array since it is a continuous block of memory, and just plug the pointers int std::sort from <algorithm>, and use std::greater or std::less to make it sort the way you want.

Unless if you have some crazy sort function that goes around radially around the 2d space or something.

this should do it:

int *arr2 = &arr[0][0];
std::sort(arr2, arr2+n*m, std::less<int>());

Also next time try to use [code] insert code here like html [/code]. This keeps the spaces and makes your code readable.

[jonnin]

yes, if its a 2d ARRAY you can just sort it normally for his requirement. It will NOT work if he ever needs to do ** or vector<vector< though, as those won't be one block.

do you need to support ** K88? Or just [][] ?

for ** I would sort all the *s (each row) the usual way and then do a merge-sort type algorithm across the rows. That is really easy to do. Trying to do it all as once 2-d entity is going to be convoluted and probably less efficient esp since each row can be a threaded sort, as can the merges, merge 2, merge 2 of those is 4 rows, merge 2 of those is 8 rows, etc... and sets of those are threaded also, looks like a tree building back to the final answer.

[keskiverto]

It will NOT work if he ever needs to do **

Depends.

auto foo = new T* [Rows];
foo[0] = new T [Rows*Cols];
// set the rest of foo to point to elements into
// the continuous block of foo[0] 

There are essentially two separate tasks:

1. How to sort an array of values. std::sort, or something else.

2. How to approach/treat/convert multidimensional array into sortable 1D array.

[poteto]

If k88 has a VLA compatible compiler (not VS), his above code works fine, as long as the lifetime of the exists inside the scope.

Also I would avoid ** arrays like the plague, it really isn't the right too for the job.

2d arrays on the stack look like 1d arrays with syntactic sugar, that's how it should look like on the heap too.

If you don't wanna pass the width and height as parameters of an array, just write a class with a 1d array vector and the width and height, then just make a function use the operator() for index using (y * height) + x.

[k88]

I use code blocks and it has GNU GCC compiler.

[poteto]

k88 I saw the topic you posted in general, but I reported it and deleted it because it is a duplicate and doing that is silly, no hard feelings.

You probably wanted to make code syntax work, and did some weird javascript attempt, but you can edit your orginal post to try the [code]code here[/code] to work.

My orginal solution by the way is 100% legitimate and will function and even if you are learning bubble sort, you should try to get my code to work as well.

If you desperately need to use bubble sort you can use the std::sort equivalent:

//taken from https://codereview.stackexchange.com/questions/167422/sorting-algorithms-bubble-sort
template<typename Iterator, typename Comparator>
void bs2(Iterator begin, Iterator end, Comparator cmp) {
    for (auto j=end; j != begin; --j) {
        for (auto i = begin + 1; i != j; ++i) {
            auto& val0 = *i;
            auto& val1 = *(i - 1);
            if (cmp(val0, val1)) {
                std::swap(val1, val0);
            }
        }
    }
}

You can use it the same way I have shown. If you try and fail, you can tell me where the problem is and I can help.

[dhayden]

if(arr[i][j]>arr[i+1][j+1])
{
    temp=arr[i][j];
    arr[i][j]=arr[i+1][j+1];
    arr[i+1][j+1]=temp;
    sum++;
}

You are comparing arr[i][j] with arr[i+1][j+1]. e.g., arr[2][11] with arr[3][12]. Now picture the 2D array. Where are these elements in relation to each other? arr[i+1][j+1] is diagonally down and to the left of arr[i][j].

So you are sorting diagonals! I doubt this is what you intended.

Also watch out for those bounds. Since you're accessing with i+1 and j+1, the for loops should be for (i=0; i<n-1; i++) and for (j=0; j<m-1; j++)

Now, back to the problem at hand. You have a 2D array. You want to sort it as though it was 1D with an index from 0 to n*m-1. So let's make a little function that allows us to do that. Along the way, I'll convert the code to use vector<vector<int>>

// Given a 2D array and a 1D index, return a reference to the given
// element
int &oneD(vector<vector<int> > &arr, unsigned idx)
{
    unsigned i = idx / arr[0].size();
    unsigned j = idx % arr[0].size();
    return arr[i][j];
}

It's very important that your return a reference to the element because we're going to use oneD() to write the elements as well as read them.
You can create the array like this:

    cout << "n" << endl;
    cin >> n;
    cout << " m" << endl;
    cin >> m;
    vector<int> dummy(m);
    vector<vector<int>> arr(n, dummy);

Your existing code to populate it is fine.

Now you can modify your code to do a traditional bubble sort using oneD() to access the i'th element:

    do {
        sum = 0;

        for (unsigned i = 0; i < n*m-1; i++) {
            if (oneD(arr,i) > oneD(arr,i+1)) {
                temp = oneD(arr,i);
                oneD(arr,i) = oneD(arr,i+1);
                oneD(arr,i+1) = temp;
                ++sum;
            }
        }
    } while (sum > 0);

Note that std::swap(oneD(arr,i), oneD(arr,i+1)) is a less error prone way to swap the items.

[k88]

yes poteto you're right lol , I was trying to rewrite a more readable code and I made a mess ,sorry I'm kinda new to all this .

thank you for your solution I'm gonna try it and see !

[k88]

dhayden thank you too! In fact I was kind of sceptical about that part of the code and now it makes sense, I was working with diagonals !