I am having trouble sorting an array.

[ThrasherK]

I need to write a function that sorts a two-dimensional array using this header:

void sort(int m[][2], int numberOfRows)

my code is supposed to primarily sort the rows and secondarily sort the columns. The program is supposed to take ten points entered by the user and sort them.

I cannot seem to get my code to compile and I am unsure why.

Here is what I have so far:

#include <iostream>
#include <cmath>
using namespace std;

void sort(int m[][2], int numberOfRows)
{
	//Sort the rows first.
	for (int i = 0; i < numberOfRows; i++)
	{
		//Find the minimum in the rows list.
		int currentMinRows = m[i][0];
		int currentMinIndexRows = i;

		for (int j = i + 1; j < numberOfRows; j++)
		{
			if (currentMinRows > m[j][0])
			{
				currentMinRows = m[j][0];
				currentMinIndexRows = j;
			}
		}
	//Swap m[i][0] with m[currentMinIndexRows][0] if necessary.
	if (currentMinIndexRows != i)
	{
		m[currentMinIndexRows][0] = m[i][0];
		m[i][0] = currentMinRows;
	}
	}
	//Sort the columns next.
	for (int i = 0; i < numberOfRows; i++)
	{
		//Find the minimum in the columns list.
		int currentMinColumns = m[i][1];
		int currentMinIndexColumns = i;

		for (int j = i + 1; j < numberOfRows; j++)
		{
			if (currentMinColumns > m[j][1])
			{
				currentMinColumns = m[j][1];
				currentMinIndexColumns = j;
			}
		}
	//Swap m[i][1] with m[currentMinIndexColumns][1] if necessary.
	if (currentMinIndexColumns != i)
	{
		m[currentMinIndexColumns][1] = m[i][1];
		m[i][1] = currentMinColumns;
	}

}
}

int main()
{
	cout << "Enter ten points in the format of x and y coordinates to be sorted: " << endl;
	cout << "For example: 1 2 and push enter. next line 3 4 and push enter ect." << endl;
	int m[10][2];
	for (int i = 0; i < 10; i++)
	{
		cin >> m[i][0] >> m[i][1];
	}
	cout << "The points are sorted by row and then by column are as follows:" << endl;
	cout << sort(m[][2],10) << endl;
	return 0;
}

Any suggestions? Please, be nice. ;)

[ThrasherK]

I also wanted to add that I feel like I need to completely re-do this code. If I am way off someone please tell me!!!

[mrnutty]

wait are you supposed to sort the rows first, and if there is any collision, like
2 values are the same in the rows, then you use the columns to resolve the conflict if
possible?

[ThrasherK]

Yes. I am trying to sort the numbered pairs (x,y) coordinates like I would sort words in alphabetical order just like the dictionary.

[mrnutty]

Can you the library sort method?

[ThrasherK]

As far as I know. There is nothing in the problem that states that I cannot.

[mrnutty]

Ok, I guess the easiest way to do this is to make your own data structure and insert it into a vector and sort it, then copy it back. So first create a struct to hold the elements.

struct Elem{
	int row;
	int col;
	Elem(int r, int c): row(r), col(c){}	
};

then create a compare function for the Elem struct:

bool elemComp(const Elem& lhs, const Elem& rhs){
	if(lhs.row < rhs.row) return true;
	else if(lhs.row > rhs.row) return false;
	//else both row are equal
	//so compare the column
	else if(lhs.col < rhs.col) return true;
	else return false;
}

now this will be your sort function:

void sortIt(int Array[][2], const int rowSize){
 //...
}

Now inside you are going to create a vector of elems like so :

std::vector< Elem > vecArray;

Now copy the array passed in, into the vecArray like so:

for(int i = 0; i < rowSize; ++i){
	vecArray.push_back( Elem(Array[i][0],Array[i][1]) );
}

Now all you got to do is call the std::sort function on it like so:

std::sort(vecArray.begin(),vecArray.end(),elemComp);

Now the vecArray is sorted the way you wanted it to be sorted. All thats left
is to copy it back into the original array like so :

for(int i = 0; i < rowSize; ++i){
	Array[i][0] = vecArray[i].row;
	Array[i][1] = vecArray[i].col;
}

So now the passed in Array is sorted by its x-axis, and secondary to its y-axis.

[ThrasherK]

The only problem with this is that these methods have not been discussed in the chapter thus far. The only sort algorithms that the book has mentioned are the selection sort and the insertion sort. The only problem that I am having is calling the function after I used the code that I posted above. I am sorry to be such a bother.

[mrnutty]

You should call it like so:

sort(m,10); //call your sort method
//print the results:

for(int row = 0; row != 10; ++row){
  cout << "(" << m[0][0] << "," << m[0][1] << ")" << endl;
}

[mike_2000_17]

Are you sure that your sort algorithm is doing what you want? or what is asked?

In my understanding, you have to take each pair (x,y) and sort them from lowest row-index (which is x) to highest and if x's are the same then put the pair with the lowest column-index (y) first. That is what I understand by "primarily sort by row" and "secondarily by column".

Now what your algorithm does is sort all row-indices (x) and then sort all column-indices (y). That will scramble all the pairs (x,y) so it doesn't make sense to me.

Imagine the problem as if you have a bunch of points on a graph, each point has a position (x,y). If you want to draw a line from one point to another, you would have to sort them from left to right (from lowest x to highest x) and points that coincide in x should be sorted from bottom to top (lowest y to highest y). But you shouldn't break up the pairs.

Well, that is just how I understand it, I could very well be wrong.

@firstPerson: why do you even suggest using a built-in sort function? You know this is for a course exercise, what kind of dumb professor would allow you to use a built-in sort function when the point of the exercise is to learn how to write this basic algorithm. If he didn't say that you cannot use it, it's because it's _implied_ that you cannot use it.

Hmm? If your array is a key/value pair then is this what you're looking for?

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

using namespace std;

void sort(int m[][2], int numberOfRows) {

	for (int x = 0; x<numberOfRows; ++x) {
		for (int y = x+1; y<numberOfRows; ++y) {
			if (m[x][0] > m[y][0]) {
				swap(m[x][0], m[y][0]);
				swap(m[x][1], m[y][1]);
			}
		}
	}
	
}

int main (int argc, char * const argv[]) {
	int array[10][2];
	
	// Populate array
	srand ( time(NULL) );
	for (int c = 0; c<2; ++c) {
		for (int r = 0; r<10; ++r) {
			array[r][c] = rand() % 50;
		}
	}

	// Print array
	cout << "Unsorted array:" << endl;
	for (int r = 0; r<10; ++r) {
		cout << "(" << array[r][0] << "," << array[r][1] << ") ";
	}
	cout << endl;
	
	// Sort it man!
	sort(array, 10);

	// Print array
	cout << "Sorted array:" << endl;
	for (int r = 0; r<10; ++r) {
		cout << "(" << array[r][0] << "," << array[r][1] << ") ";
	}
	cout << endl;
}

[mike_2000_17]

@stevee: you shouldn't post complete code like that, he can just grab it and hand it in as the assignment solution. Especially since there is one mistake:

Line 11 in the above should be:

if ((m[x][0] > m[y][0]) || ((m[x][0] == m[y][0]) && (m[x][1] > m[y][1]))) {

That is for primary sort by row ([0] values) and secondary sort by column ([1] values).

@stevee: you shouldn't post complete code like that, he can just grab it and hand it in as the assignment solution. Especially since there is one mistake:

Line 11 in the above should be:

if ((m[x][0] > m[y][0]) || ((m[x][0] == m[y][0]) && (m[x][1] > m[y][1]))) {

That is for primary sort by row ([0] values) and secondary sort by column ([1] values).

Oops, points taken mike!

[ThrasherK]

Thank you firstperson for showing me what I was doing wrong when I called it. Mike 2000 17...yes you are right, I didn't think about the fact that I would be scrambling the pairs up. I guess I need to re-write like I originally thought. Thanks again. I might get it this time. :)

[ThrasherK]

Also...
@Stevee1984. I worked more on this last night and came up with code that has some similarities to yours but a big difference is that I have to have the user input the points. I can't use a random array.
@mike 2000 17. I am female. :) and I did figure that line eleven was incorrect so at least I know that I am learning something from this (which makes me feel better about the entire situation). I know that others may plagiarize but I have no intentions of doing that. I want to actually learn this and understand it. I really do appreciate your ongoing help.

[ThrasherK]

You should call it like so:

sort(m,10); //call your sort method
//print the results:

for(int row = 0; row != 10; ++row){
  cout << "(" << m[0][0] << "," << m[0][1] << ")" << endl;
}

I wouldn't need to put the int row in the output somewhere?? Like maybe:

for(int row = 0; row != 10; ++row)
{
cout << "(" << m[row][0] << "," << m[row][1] << ")" << endl;
}

[ThrasherK]

I wouldn't need to put the int row in the output somewhere?? Like maybe:

for(int row = 0; row != 10; ++row)
{
cout << "(" << m[row][0] << "," << m[row][1] << ")" << endl;
}

It is supposed to be that way. I just changed the code that I wrote last night and ran it and it worked. Thanks for all of your help. Problem solved. :)