Need a little help--- 2d array selection sort

[sunhater]

Ok, the program below sorts the individual rows. I need it to sort all the numbers in each position, not just the rows. Any help would be appreciated.



#include <iostream>
using namespace std;


const int rows = 3;
const int cols = 10;

void select_sort( );

int array[rows][cols]={
{15, 40, 25, 100, 16, 1, 10, 42, 35, 23},
{122, 14, 3, 19, 156, 45, 2, 99, 74, 65},
{0, 34, 39, 109, 176, 20, 7, 18, 29, 12}
};

// ------------------------------------------------------------------
// ------------------------------------------------------------------

int main()
{

int i, j;

cout << &quot;SELECTION SORT PROGRAM&quot; << endl << endl;

cout << &quot;First the unsorted array...&quot; << endl << endl;
for(i=0; i<rows; i++)
{
for(j=0; j<cols; j++)
{
cout<<array[ i ][ j ]<<&quot;\t &quot;;
}
cout<<endl;
}


// -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --

select_sort( );

// -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --

cout<<endl;

cout << &quot;Now the sorted array...&quot; << endl << endl;

for(i=0; i<rows; i++)
{
for(j=0; j<cols; j++)
{
cout<<array[ i ][ j ]<<&quot;\t &quot;;
}
cout<<endl;
}


cout<<endl;

return 0;
}

// ------------------------------------------------------------------
// ------------------------------------------------------------------

void select_sort( )
{
int min;
int b;
for(int h=0; h<rows; h++)
{
for(int a=0; a<cols;a++)
{
b=a;
min=array[h];
for(int j=a+1; j<cols;j++)
{
if(array[h][j]<min)
{
b=j;
min=array[h];
}
}
array[h]=array[h][a];
array[h][a]=min;
}
}
return;
}

// ------------------------------------------------------------------
// ------------------------------------------------------------------

 

[kmfna]

Hey,

What exactly do you want sorted and how?

Kevin

 

[sunhater]

int array[rows][cols]={
{15, 40, 25, 100, 16, 1, 10, 42, 35, 23},
{122, 14, 3, 19, 156, 45, 2, 99, 74, 65},
{0, 34, 39, 109, 176, 20, 7, 18, 29, 12}
};

This is what I want sorted. I want to use the selection sort method. I know there are easier ways, but this is what was required. I just want it to be sorted like this

0, 1, 2, 3, 7, 10, 14....a[0][9]
a[1][0]..................a[1][9]
a[2][0]..................a[2][9] all in sorted order


right now it sorts the rows, but won't sort everything.
Example
1, 10, 15, 16, 23, 25, 35, 40, 42, 100
2, 3, 14, 19, 45, 65, 74, 99, 122, 156
0, 7, 12, 18, 20, 29, 34, 39, 109, 176

I seem to be on the right track as I have sorted the rows, just need to find out why its not comparing the rows with each other.

 

[kmfna]

Ok, so, before I try to come up with an answer, let me clarify, you want to put Everything in numerical order, so, as your example goes, it would be:

array[1][col] {0, 1, 2, 3, 7, 10, 12, 14, 15, 16}
array[2][col] {18, 19, 20, 23, 25, 29, 34, 35, 39, 40}
array[3][col] {42, 45, 65, 74, 99, 100, 109, 122, 156, 176}

Is this what you're looking for??

I would try creating another 2Darray and then use similar logic to what you have, only, loop through the entire original 2Darray and load the new array in numerical order. You could also use it for reverse numerical order. This is not nearly completed, it will be missing a loop and some further comparison, but it should give you a starting point.

Psuedo code:

for(int h=0; h<rows; h++)
{
for(int j=a+1; j<cols;j++)
{
if(array[h][j]<min)
{
min=array[h];
}
if ((h = 2) and (j = 9)) //Start Psuedo Code
{
new array[count1][count2] = min
if count2 = 9
if count1 = 2
Finished with loop
else
count1 + 1
count2 = 0
else
count2 + 1

} //End Psuedo Code
}
}

 

[sunhater]

array[1][col] {0, 1, 2, 3, 7, 10, 12, 14, 15, 16}
array[2][col] {18, 19, 20, 23, 25, 29, 34, 35, 39, 40}
array[3][col] {42, 45, 65, 74, 99, 100, 109, 122, 156, 176}

Is this what you're looking for??

Yes, that is what I want to do. I'll look at the other part now

 

[obislavu]

Hi,
You should look the array[][] as a vector by taking a pointer to the array and after that index it as a vector:

Example:

int *pToArray = &array[0][0];
The value of an element of the array would be :

*(pToArray+i*cols +j) where i is 1...rows and j is 1...cols
Or
p[i*cols +j] where i is 1...rows and j is 1...cols


For example these loops travers sequential the array
for (int i=0;i<rows;i++)
{
for (int j=0;j<cols;j++)
cout<<pToArray[ i*cols + j]<<&quot;,&quot;;
}
Now go in select_sort() and applly the algorithm that you now for a 1D array which is pToArray!!!
The same method you could apply for the 3D array.

-obislavu-

 

[sunhater]

obislavu

Unfortunately I have no idea what vectors or pointers are yet. Actually I think vectors are what is up next in my class.

kmfna

I sort of followed the second part. I'll study it some more and see if I can't come up with something.

Thanks for the responses.

 

[obislavu]

Hi,
A vector is nothing else than an 1D array.
Take a look of the following code (corrected):

void main()
{
int rows = 3;
int cols = 4;
int array[][4]={{4,3,2,1},{8,7,6,5},{12,11,10,9}};
int *p =&array[0][0];

cout<< &quot;Original Array&quot;<<endl;
for (int i=0;i<rows;i++)
{
for (int j=0;j<cols;j++)
cout<<p[ i*cols + j]<<&quot;,&quot;;
}
// Select_Sort()
int min;
int b;
for(int h=0; h<rows; h++)
{
for(int a=0; a<cols;a++)
{
b=a;
min=array[h];
for(int j=a+1; j<cols;j++)
{
if(array[h][j]<min)
{
b=j;
min=array[h];
}
}
array[h]=array[h][a];
array[h][a]=min;
}
}
// end Select_Sort()
cout<<&quot; Array sorted&quot;<<endl;
for ( i=0;i<rows;i++)
{
for (int j=0;j<cols;j++)
cout<<p[ i*cols + j]<<&quot;,&quot;;
}
return;
}
It produces the following results:

Original Array
4,3,2,1,8,7,6,5,12,11,10,9,
Array sorted
1,2,3,4,5,6,7,8,9,10,11,12,

And I hope you understand how to look a 2D array[n][m] as an 1D array where elements are indexed with one index from 1...m*n.

-obislavu-

 

[kmfna]

Don't forget, if you plan to use vectors, you need to include the vector library.

vector.h

 

[PerFnurt]

If you use vector sorting is super easy.

#include <vector>
#include <algorithm>

std:vector<int> v;
// Add elements
...
std::sort(v.begin(), v.end());
//Wheee

/Per

_{if (typos) cout << &quot;My fingers are faster than my brain. Sorry for the typos.&quot;;}

 

[obislavu]

Hi,
The code that I provided previously has no need for any include!!! It is not using vector class defined in STD or somewhere mentioned by PenFnurt.
By the way , your code is working and will sort the 2D array with the following changes:

// Select_Sort()
{
int min;
int b;
for(int h=0; h<rows; h++)
{
for(int a=0; a<cols;a++)
{
b=a;
min=array[h];
for(int j=a+1; j<cols;j++)
{
if(array[h][j]<min)
{
b=j;
min=array[h];
}
}
array[h]=array[h][a];
array[h][a]=min;
}

}
-obislavu-

 

[PerFnurt]

>The code that I provided previously has no need for any include...It is not using vector class

Ah, you mean this is a good thing? There are other reasons for using vector besides the free sorting that comes with std::sort like exception safety and dynamic allocation.

Actually...I cant think of a reson NOT to use vector instead of a C array.

Btw, which code snippet do you find is easiest to maintain/understand:
A) 1 line of std::sort
B) ~20 lines of home made sorting.



/Per

_{if (typos) cout << &quot;My fingers are faster than my brain. Sorry for the typos.&quot;;}