C++ 2D Array Sorting

[crispy]

Salutations cplusplus users,
I'm having a bit of trouble with my sorting algorithm, I've looked on other sites and for simple sorting codes and I've read that bubble sort was the simplest (albeit very inefficient). Well I've tried using an algorithm from another site and adjusting it to my particular program but I keep getting an error "'num' cannot be used as a function".

I am still new to C++ so if there's something obvious I've missed feel free to rip at it, but I'm stumped. I'm creating an 8*8 RNG sorted in descending order that will show in a the highest and lowest number, and the number of times both occurred. Any tips are appreciated!

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

int i, j;
int matrix[8][8]; //Creates an 8*8 Matrix or a 2-dimensional array

void sort(int &num)
{
int flag = 1;
int temp, x, y;
int numLength;
for(x = 1; (x<8) && flag; x++)
{
flag = 0;
for (y=0; y<(8 -1); y++)
{
if (num(y+1) > num(y))
{
temp = num(y);
num(y) = num(y+1);
num(y+1) = temp;
flag = 1;
}
}
}
return; //arrays are passed to functions by address; nothing is returned
}

void fillmatrix ()
{
srand ((unsigned)time(0)); //Links the random number generator to the clock
for (i=0; i<8; i++){
cout<<endl;
for (j=0; j<8; j++){
matrix[i][j]=rand()%(99) + 1; //Produces a random number between 1-100
sort (matrix[i][j]);
cout << matrix[i][j]<<" ";
}}}

int main ()
{
cout<<"Here is your randomly generated 8*8 Matrix"<<endl;
fillmatrix ();
cout<<endl<<endl;
system ("pause");
return 0;
}

[TheDestroyer]

Rather than wasting your time in writing a new sorting function, try from algorithm.h the function std::sort. All you have to do is define the functor that defines the sorting rule you want to do. it's very simple, and way easier than rewriting an algorithm for sorting all over from the beginning.

[crispy]

I looked up what you meant destroyer, and while that does seem simpler I believe my professor is looking for a separate function

[TheDestroyer]

I, personally, prefer merge sort. It took me like 2 hours to implement its function. It's simple and fast and stable. I can't take a look on your code, it's messy. I'm sorry.

[crispy]

Well I've worked on it a little more and I tried cleaning it up, here's what I've got now

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

int i, j;
int matrix[8][8];

void sort(int x, int y)//Bubble sort function
{
for(x=0;x<8;x++)
{
for(y=0;y<x;y++)
{
if(x>y)
{
int temp=x; //swap
x=y;
y=temp;
}}}}

void fillmatrix ()
{
srand ((unsigned)time(0));
for (i=0; i<8; i++){
cout<<endl;
for (j=0; j<8; j++){
matrix[i][j]=rand()%(99) + 1;
sort (matrix[i][j]);
cout << matrix[i][j]<<" ";
}}}

int main ()
{
cout<<"Here is your randomly generated 8*8 Matrix"<<endl;
fillmatrix ();
cout<<endl<<endl;
system ("pause");
return 0;
}

If you look at the sort function it's a little tidier, but the problem I'm having, or at least that I think I'm having is when I call on the "sort" function in my "fillmatrix" function, the "sort" function isn't accepting matrix[i][j]. I have a feeling it's because I'm trying to sort an 8*8 array of random numbers in a one at a time bubble sort. How would I go about sorting an 8*8 matrix though?

[TheDestroyer]

1- Use [code][ /code] wrapper.
2- Use indents
3- Explain exactly what kind of error it's

That's what clean means, my friend :)

[TheDestroyer]

Your sort function doesn't access the array... what are you doing in that sort function? use the [] operator to access the matrix elements.

something like matrix[x][y]

[crispy]

I didn't understand exactly what you said but I worked on it a little more but here's where I am now. I shortened the program a little further, and right now I have my sorting function. The problem is when I put "a" in the sort function C++ freaks out and opens an entirely new page.

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

int i,j,a;
int array[8][8];

void sort(int array)
{
    for(i=0;i<8;i++)
    {
        for(j=0;j<8;j++)
        {
            if(array[i]>array[j])
            {
                int temp=array[i];
                array[i]=array[j];
                array[j]=temp;
            }
        }
    }
}

int main ()
{
srand ((unsigned)time(0));
      for (i=0; i<8; i++)
      {
          for (j=0; j<8; j++)
          {   int a=rand()%(99) + 1;
              cout<<a<<" ";
          }
      cout<<endl;
      }
sort (a);
cout<<endl<<endl;
system ("pause");
return 0;
}

The error is "invalid types `int[int]' for array subscript". The rest of the program runs fine, I have my 8*8 2d array but it's not sorted in descending order!
I feel like I am making a simple mistake but I can't wrap my head around it. Also, even though my problem isn't solved I've learned a bit about C++ and this site. Thanks for your help and patience Destroyer :)

[TheDestroyer]

You're welcome. That's quiet fine.

Now let me ask the following question. What's the point of passing a to that function? you're not using it at all!!

I think it would make more sense if you could pass the array to your function. So soemthing like:

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

void sort(int MyArray[8][8]) //you're telling the function that it should expect an 8x8 array as a parameter
{
    for(int row = 0; row < 8; row++)
    {
        for(int i=0;i<8;i++)
        {
            for(int j=i;j<8;j++)
            {
                if(MyArray[row][i]<MyArray[row][j]) //the condition was flipped in the program you gave me, notice that would have sorted them ascendingly
                {
                    int temp=MyArray[row][i];
                    MyArray[row][i]=MyArray[row][j];
                    MyArray[row][j]=temp;
                }
            }
        }
    }
}

void print(int MyArray[8][8]) //you're telling the function that it should expect an 8x8 array as a parameter
{
    for (int i=0; i<8; i++)
    {
        for (int j=0; j<8; j++)
        {
            cout<<MyArray[i][j]<<" ";
        }
        cout<<endl;
    }
}

int main ()
{
    srand ((unsigned)time(0));
    int array[8][8]; //you don't have to define stuff in the global scope, defining your array here is fine
    for (int i=0; i<8; i++)
    {
        for (int j=0; j<8; j++)
        {
            array[i][j]=rand()%(99) + 1; //fill the array with elements
        }
    }
    print(array); //print before sorting
    sort (array); //sort
    print(array); //print after sorting
    cout<<endl<<endl;
    system ("pause");
    return 0;
}

Now the question is, what kind of result do you expect? Do you expect each row to be sorted? or all your 8x8 elements to be sorted from top-left to bottom-right?

The correction I did does each row. Read the comments, and if you have questions, don't hesitate.

Good luck :)

[crispy]

Wow, the last thing that spun as fast as my head when I saw this came from the movie Twister. Looking at your sort function, it looks so simple and practical (not to mention organized!). The reason I was trying to use "a" in the other program was because I felt like matrix[i][j] would not be accepted because of the brackets.

What I aim for is to sort the elements from top-left to bottom-right. I like how you cleaned up the matrix generator. It now creates the matrix all at once in the int main and prints it by calling on your print function, rather than printing it as the for loop functioned (as the error with mine).

Rather than generating and printing in one swipe you generated, printed, sorted, and printed again. Of course there's no need for me to tell you this, but it's fascinating to say the least!

My one question pertains to the sort for loop though. When you nested a for loop inside a nested for loop, the second and third are to sort every element from left to right, correct? While the first for loop says after sorting this row we stop and start over on the next. Is this the merge sort you spoke about before? I have seen the merge sort on (http://mathbits.com/mathbits/compsci/arrays/Merge.htm) but that looks nothing like the one you have shown here.

Also, if I am correct that the first for loop sorts one row at a time, would adding a forth for loop for columns make it sort from top-left to bottom-right?

[TheDestroyer]

crispy wrote:

My one question pertains to the sort for loop though. When you nested a for loop inside a nested for loop, the second and third are to sort every element from left to right, correct? While the first for loop says after sorting this row we stop and start over on the next.

Yes, this is exactly what it does. Row after row, I sort. Notice that in the third loop I'm starting from (j = i). (it has to be j = i +1, btw, I was just in a hurry).

crispy wrote:

Is this the merge sort you spoke about before? I have seen the merge sort on (http://mathbits.com/mathbits/compsci/arrays/Merge.htm) but that looks nothing like the one you have shown here.

No actually, this has nothing to do with merge sort. Merge sort is way faster, and has a sorting time of O(n log(n)) if I remember correctly (but harder to implement). The one I used here is the most typical-easy sorting algorithm (and is almost the slowest, I don't really know the name). Its sorting time scale is O(n^2). So if there are too many elements, the sorting becomes slower and slower in a quadratic behaviour.

crispy wrote:

Also, if I am correct that the first for loop sorts one row at a time, would adding a forth for loop for columns make it sort from top-left to bottom-right?

No. I don't think so. I think if you wanna do it that way it'll become really very expensive and it'll need an iterative approach.
The way to sort it from top-left to bottom-right is by going through all the numbers from top-left to bottom-right as if they were a single array.

I'm gonna explain how you could do that, but this is gonna be a little confusing. So concentrate, and read carefully:

Now, to sort a single row, you had a first variable i that holds (lets call it holder) at a single number, while another variable j slides (let's call it slider) through the other variables till it finishes one cycle, and then the holder proceeds by 1 element so that the slider could cycle again.

If you wanna sort them from top-left to bottom-right, you have to have a holder which consists of 2 variables, lets call them ir and ic (i row and i column), and a slider that consists of 2 variables, jr and jc.

With exactly the same concept, rather than having 2 loops to cycle through the holder and slider, you have to have 4 loops. First 2 are the holder, and second 2 are the slider. Those 2x2 loops together have to act exactly like if there were no rows and columns, but only a single "long" list of numbers from 0 to (8x8-1) = 63. So they have to run (hypothetically) from the frist top-left to the bottom-right, while they internally are going through rows and columns.

Got the idea? hope it helps. Good luck :)

[crispy]

Almost got it and it helps a lot man! My last question is, you said instead of having 2 loops to cycle through it I would need four, does this include the original for(int row = 0; row < 8; row++)? It doesn't seem like you would since you're using ir, ic and jr, jc for the rows and columns but I'm not 100% sure

[TheDestroyer]

No. You would not need that anymore. Because your holder and slider are already going through all rows.

[crispy]

Thank you a lot destroyer, your assistance has been truly invaluable! If you know anything about calipers on cars, my break calipers locked up and only the rear breaks were functional. As such I had to miss some college classes but your guidance has helped tremendously! Thanks again! :)

Also, here is my final code for anyone that may want to see

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

void sort(int MyArray[8][8])
{
     for(int ir=0;ir<8;ir++)
     {
        for(int ic=0;ic<8;ic++)
        {
            for(int jr=0;jr<8;jr++)  
            {
                    for(int jc=0;jc<8;jc++)
                    {        
                if(MyArray[ir][jr]>MyArray[ic][jc])
                {
                    int temp=MyArray[ir][jr];
                    MyArray[ir][jr]=MyArray[ic][jc];
                    MyArray[ic][jc]=temp;
                    }
                }
            }
        }
    }
}
void print(int MyArray[8][8])
{
    for (int i=0; i<8; i++)
    {
        for (int j=0; j<8; j++)
        {
            cout<<MyArray[i][j]<<" ";
        }
        cout<<endl;
    }cout<<endl;
}

int main ()
{
    srand ((unsigned)time(0));
    int array[8][8];
    for (int i=0; i<8; i++)
    {
        for (int j=0; j<8; j++)
        {
            array[i][j]=rand()%(99) + 1; //fill the array with elements
        }
    }
    print (array);
    sort (array); //sort
    print(array); //print after sorting
    cout<<endl<<"The Maximum value in the matrix is "<<array[0][0];
    cout<<endl<<"The Minimum value in the matrix is "<<array[7][7]<<endl;
    cout<<endl;
    system ("pause");
    return 0;
}

[TheDestroyer]

You're welcome.

Does this code sort correctly? You're doing a terrible mistake there that doubles the time of sorting. Notice in my code, the third loop is initialised as:

for(int j = i;...)

this you have to do in your program as well!!!! I know you flipped the inequality sign to solve this problem, but you're wasting 50% of your program's processing time to do it. Think about it, and find out why the following code is the correct one:

void sort(int MyArray[8][8])
{
     for(int ir=0;ir<8;ir++)
     {
        for(int ic=0;ic<8;ic++)
        {
            for(int jr=ir+1;jr<8;jr++)  
            {
                for(int jc=ic+1;jc<8;jc++)
                {        
                    if(MyArray[ir][jr]<MyArray[ic][jc])
                    {
                        int temp=MyArray[ir][jr];
                        MyArray[ir][jr]=MyArray[ic][jc];
                        MyArray[ic][jc]=temp;
                    }
                }
            }
        }
    }
}

Best regards, and good luck with your car's breakes :)