Sorting Diagonally

Kauto (22)
Hello, I have a question about sorting a 2D array. I've looked at many websites and solutions but none fits what Im looking for.

Lets suppose I've got the following array:

2 5 7 4 8

3 11 14 5 2

6 3 12 9 1

7 15 11 4 2

8 16 13 5 1


I would like to sort this array diagonally to make it look as the following:

[IMG]http://i40.tinypic.com/152dvk2.jpg[/IMG]


Thank you for your time
Regards
kbw (9488)
Don't think of your data structure as a 2D array (because it isn't). Instead, think of it as ordered set.

Serialize it to an array, sort it, then read it back into the structure (deserialize it).
Cubbi (4774)
you could build a view that unravels the array in that sequence and then feed it to std::sort, for example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <array>
#include <boost/iterator/permutation_iterator.hpp>

int main()
{
    int a[5][5] = {{2,  5,  7, 4, 8}, 
                   {3, 11, 14, 5, 2}, 
                   {6,  3, 12, 9, 1},
                   {7, 15, 11, 4, 2},
                   {8, 16, 13, 5, 1}}; 

    // indexes into the original array
    // (for full credit, write the function that builds these)
    std::array<std::size_t, 25> idx = {0,
                                       1,5,
                                       2,6,10,
                                       3,7,11,15,
                                       4,8,12,16,20,
                                         9,13,17,21,
                                           14,18,22,
                                              19,23,
                                                 24};

    std::sort(boost::make_permutation_iterator(&a[0][0], idx.begin()),
              boost::make_permutation_iterator(&a[0][0], idx.end()));

    for(auto& row: a) {
        for(int el: row)
            std::cout << std::setw(2) << el << ' ';
        std::cout << '\n';
    }
}

demo: http://coliru.stacked-crooked.com/a/eac4c27371caef01
Kauto (22)
I get what you're saying Cubbi though my Array is randomly filled, so is there any other way to sort it as demanded?
Here's what I wrote as code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
 
#include "stdafx.h"
#include <iostream>
#include <math.h>
#include <time.h>
#include<iomanip>
using namespace std;
const int AS = 6;
int filling(void);
void printing(int[AS][AS]);
int forsorting(int[][AS], int);


int main()

{
	int funny = 0;
	int timpa = 0;
	int counter = 0;
	int Array[AS][AS];
	srand(time(0));

	for (int i = 0; i<AS; i++)
	{
		for (int j = 0; j<AS; j++)
			Array[j] = filling();
	}

	cout << "The unsorted array is" << endl << endl;

	printing(Array);


	cout << "The sorted array is" << endl << endl;



	for (int il = 0; il<AS; il++)
	{
		for (int elle = 0; elle<AS; elle++)
			Array[il][elle] =forsorting(Array, funny);



	}

	system("PAUSE");


	return 0;

}

int filling(void)
{
	int kira;
	kira = rand() % 87 + 12;
	return kira;
}


void printing(int Array[AS][AS])
{
	int counter = 0;
	for (int i = 0; i<AS; i++)
	{
		for (int j = 0; j<AS; j++)
		{
			cout << setw(5) << Array[i][j];
			counter++;
			if (counter%AS == 0)
				cout << endl << endl;
		}
	}
}

int forsorting(int Array[AS][AS], int funny)
{
	int c, tmp, x;
	int dice = 0;
	int Brray[AS*AS];
	int timpa = 0;
	int super = 0;
	

	//Transofrming Array[][] into Brray[]
	for (int i = 0; i < AS; i++)
	{
		for (int k = 0; k < AS; k++)
		{
			Brray[timpa] = Array[i][k];
			timpa++;
		}
	}


	//Bubble sorting in Brray[]

	for (int passer = 1; passer <= AS-1; passer++)
	{
		for (int timon = 1; timon <= AS-1; timon++)
		{
			if (Brray[timpa]>Brray[timpa + 1])
			{
				super = Brray[timpa];
				Brray[timpa] = Brray[timpa + 1];
				Brray[timpa + 1] = super;
			}
		}
	}

	//Transforming Brray[] into Array[][]

	for (int e = 0; e<AS; e++)
	{
		for (int d = 0; d<AS; d++)
		{
			Brray[dice] = Array[e][d];

			dice++;
		}
	}
	
	
		[i]There's a part missing (the sorting part)



}




I hope this helps you understand my situation
kbw (9488)
permutation_iterator ... very cool. That's exactly what's required, a custom sort order.
Kauto (22)
Im still new to this, so what you said didnt make much sense to me.
If you could clarify or write it to me in codes it would be really great.

Thank you
Cubbi (4774)
what you said didnt make much sense to me.
If you could clarify or write it to me in codes

I wrote "in codes" (a complete program with a link to an online compiler that executes it).

Besides using an iterator that represents your array as a 1D random-accessible sequence for the C++ sort() function, you could also use indirection:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
    int a[5][5] = {{2,  5,  7, 4, 8},
                   {3, 11, 14, 5, 2},
                   {6,  3, 12, 9, 1},
                   {7, 15, 11, 4, 2},
                   {8, 16, 13, 5, 1}};

    // indirection array
    int* indirect_a[5*5];
    for(int row = 0, col = 0, pos = 0; pos < 5*5; pos++, ++row, --col)
    {
        if(row > 4) {
            row = col+2;
            col = 4;
        } else if(col < 0) {
            col = row;
            row = 0;
        }
        indirect_a[pos] = &a[row][col];
    }


after this, all you have to do is indirect sort: I would use 

1
2
 
    std::sort(boost::make_indirect_iterator(indirect_a),
              boost::make_indirect_iterator(indirect_a + 25));


but you could adapt your own Bubble Sort code, just dereference when comparing and swapping
Kauto (22)
Im getting an error on the boost. I think it's related to the library it's in. I have no idea where it is, if you could help me with that


Many thanks
Regards
Duthomhas (13282)
This is a variation on the 'print a diamond on the console with asterisks' assignment.

Unfortunately, it isn't that obvious...

The first thing you need to do is flatten your input to a 1D array, so that you can sort it normally. Fortunately, since you are using an actual c-style array, you can do that easily by casting to pointer:

1
2
3
4
5
 
int Array[ROWS][COLS];
// (I know that both dimensions are AS, but for exposition we
//  will not assume that the matrix is square.)

std::sort( &Array[0][0], &Array[0][0] + ROWS * COLS );

If you started with a random set of numbers in [1,9], you would now have an array sorted like this:

1 2 3
4 5 6
7 8 9

The problem, of course, is that you want it like this:

1 2 4
3 5 7
6 8 9

Let's look at that a different way. Notice the progression, the order in which the numbers are placed:

┌───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┐
│(1)    │ 1(2)  │ 1 2   │ 1 2(4)│ 1 2 4 │ 1 2 4 │ 1 2 4 │ 1 2 4 │ 1 2 4 │ 1 2 4 │
│       │       │(3)    │ 3     │ 3(5)  │ 3 5   │ 3 5(7)│ 3 5 7 │ 3 5 7 │ 3 5 7 │
│       │       │       │       │       │(6)    │ 6     │ 6(8)  │ 6 8(9)│ 6 8 9 │
└───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┘


Do you see the loops in there? Kind of like making a diamond:
(1) stuff before the diagonal
(2) the diagonal
(3) stuff after the diagonal

To reorder, you will need a temporary array -- a 1D array.
First, simply copy the Array[][]'s data over to the temporary.
Then, copy it back in the right order.

You will have to think a bit about how to put the numbers in the temporary array into the proper spots in Array[][].

Here're some hints:
- You will need an index into the 1D array containing the sorted stuff, starting at zero.
- You will need a loop to keep track of which diagonal you are working on: 0, 1, ..., COLS-1
- Inside that loop, you will need to have another loop with a 'row' and a 'col' variable, initialized to the proper spot.
- Don't forget that there are two halves to the matrix, plus the diagonal:
┌───────┬───────┬───────┐
│ * *   │     * │       │
│ *     │   *   │     * │
│       │ *     │   * * │
└───────┴───────┴───────┘


[edit] almost forgot. Inside your inner loops, you will see an assignment like this:
Array[ row++ ][ col-- ] = Flat[ n++ ];
...where n is the index into the flat, 1D array.

Hope this helps.
Last edited on
Kauto (22)
Thank you for your assistance everyone, what you said was very useful to me. I actually was able to think about clearly and came up with a way to start filling the array based on your recommendation, but one problem now, Im pretty sure that my logic is 99% right but there's a flaw somewhere. After I run my code the 2nd array isnt printed on the screen. Any help with this?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
 
    #include "stdafx.h"
    #include <iostream>
    #include <math.h>
    #include <time.h>
    #include<iomanip>
    #include<array>
    #include <algorithm>
    
    using namespace std;
    const int AS = 5;
    int filling(void);
    void printing(int[AS][AS]);
    int forsorting(int[][AS], int);
    
    
    int main()
    
    {
    	int funny = 0;
    	int timpa = 0;
    	int counter = 0;
    	int Array[AS][AS];
    	srand(time(0));
    
    	for (int i = 0; i<AS; i++)
    	{
    		for (int j = 0; j<AS; j++)
    			Array[i][j] = filling();
    	}
    
    	cout << "The unsorted array is" << endl << endl;
    
    	printing(Array);
    
    
    	cout << "The sorted array is" << endl << endl;
    
    
    
    	for (int il = 0; il<AS; il++)
    	{
    		for (int elle = 0; elle<AS; elle++)
    			Array[il][elle] =forsorting(Array, funny);
    
    		
    
    	}
    	printing(Array);
    	system("PAUSE");
    
    
    	return 0;
    
    }
    
    int filling(void)
    {
    	int kira;
    	kira = rand() % 87 + 12;
    	return kira;
    }
    
    
    void printing(int Array[AS][AS])
    {
    	int counter = 0;
    	for (int i = 0; i<AS; i++)
    	{
    		for (int j = 0; j<AS; j++)
    		{
    			cout << setw(5) << Array[i][j];
    			counter++;
    			if (counter%AS == 0)
    				cout << endl << endl;
    		}
    	}
    }
    
    int forsorting(int Array[AS][AS], int funny)
    {int n;
    	int real;
    	int dice = 0;
    	int Brray[AS*AS];
    	int timpa = 0;
    	int super = 0;
    	int median;
    	int row=0;
    	int col=AS-1;
    	
    
    	//Transofrming Array[][] into Brray[]
    	for (int i = 0; i < AS; i++)
    	{
    		for (int k = 0; k < AS; k++)
    		{
    			Brray[timpa] = Array[i][k];
    			timpa++;
    		}
    	}
    
    
    	//Bubble sorting in Brray[]
    
    	for (int passer = 1; passer <= AS-1; passer++)
    	{
    		for (int timon = 1; timon <= AS-1; timon++)
    		{
    			if (Brray[timpa]>Brray[timpa + 1])
    			{
    				super = Brray[timpa];
    				Brray[timpa] = Brray[timpa + 1];
    				Brray[timpa + 1] = super;
    			}
    		}
    	}
    
    	//Transforming Brray[] into sorted Array[][]
    
    	
    	for(int e=4;e>=0;e--)//e is the index of the diagonal we're working in
    	{
    
    	
    		if(AS%2==0)
    			{median=0.5*(Brray[AS*AS/2]+Brray[AS*AS/2-1]);
    		//We start filling at median - Brray[AS*AS/2-1]
    
    		while(row<5 && col>=0)
    
    			{real=median-Brray[AS*AS/2-1];
    		Array[row][col]=Brray[real];
    		real++;
    		col--;
    		row++;}
    		}
    	
    		else {
    			median=Brray[AS*AS/2];
    			//We start filling at Brray[AS*AS/2-AS/2]
    	
    			while(row<5 && col>=0)
    			{real=Brray[AS*AS/2-AS/2];
    			n=Array[row][col]=Brray[real];
    		real++;
    		col--;
    		row++;}
    	
    		}
    	
    	}
       
    		
    
    	return n;
    }


Thanks again for your assistance
Duthomhas (13282)
I cleaned up your code some. And I added a lot of comments for you to consider.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
 
#ifdef _MSVC
#include "stdafx.h"
#endif

#include <iostream>
//#include <cmath>
#include <ctime>    // time()
#include <iomanip>  // setw()
#include <cstdlib>  // rand(), srand()

using namespace std;
const int AS = 5;
void filling(int[AS][AS]);
void printing(int[AS][AS]);
void sorting(int[AS][AS]);


int main()
{
  int Array[AS][AS];
  srand(time(0));
  
  filling(Array);
  cout << "The unsorted array is" << endl << endl;
  printing(Array);

  sorting(Array);
  cout << "The sorted array is" << endl << endl;
  printing(Array);

  cout << "Press ENTER";
  cin.get();
  return 0;
}


void filling(int Array[AS][AS])
{
// We'll fill the array with counting numbers until we get the sorting algorithm working below
  int counter = 1;
  for (int i = 0; i < AS; i++)
  for (int j = 0; j < AS; j++)
    Array[i][j] = counter++;

/* Once the sorting algorithm below works, we'll use this to fill the array with random numbers
  for (int i = 0; i < AS; i++)
  for (int j = 0; j < AS; j++)
    Array[i][j] = rand() % 87 + 12;
*/
}


void printing(int Array[AS][AS])
{
  for (int i = 0; i<AS; i++)
  {
    for (int j = 0; j<AS; j++)
    {
      cout << setw(5) << Array[i][j];
    }
    cout << endl << endl;
  }
}

void sorting(int Array[AS][AS])
{
  int real;
  int Brray[AS*AS];
  int timpa = 0;
  int super = 0;
  int median;
  int row=0;
  int col=AS-1;


  //Transforming Array[][] into Brray[]
  for (int i = 0; i < AS; i++)
  {
    for (int k = 0; k < AS; k++)
    {
      Brray[timpa] = Array[i][k];
      timpa++;
    }
  }


  //Bubble sorting in Brray[]
  for (int passer = 1; passer <= AS-1; passer++)  // See this '<=' thing? It should be 'passer < AS;'
  {
    for (int timon = 1; timon <= AS-1; timon++)   // Same here.
    {
      if (Brray[timpa]>Brray[timpa + 1])
      {
        super = Brray[timpa];
        Brray[timpa] = Brray[timpa + 1];
        Brray[timpa + 1] = super;
      }
    }
  }

  //Transforming Brray[] into sorted Array[][]
/*
  All that follows is where you need to think.
  I don't know why you are doing calculations for 'median'.
  
  Think about how 'e' works. It should start at 0. 
  
      e         0     1     2     3        All this only fills the first half:
      diagonal  @...  .@..  ..@.  ...@        @@@@
                ....  @...  .@..  ..@.        @@@.
                ....  ....  @...  .@..        @@..
                ....  ....  ....  @...        @...
	    
  After you have reached the main diagonal, you must reconsider your method.
  This means you will need yet another loop, to fill the second half.
  
  Also, reconsider how 'real' is being used. It should start at zero, right?
  
                0...  .1..  ..3.  ...6
                ....  2...  .4..  ..7.
                ....  ....  5...  .8..
                ....  ....  ....  9...
		
  The 'row' and 'col' values depend on the current value of 'e'. So 
  make sure you set them properly inside the 'e' loop, before the 'while' 
  loop.
  
*/
  for(int e=4; e>=0; e--) //e is the index of the diagonal we're working in
  {

    if(AS%2==0)                                           // You don't need this!
    {                                                     //
      median=0.5*(Brray[AS*AS/2]+Brray[AS*AS/2-1]);       //
      //We start filling at median - Brray[AS*AS/2-1]     //
                                                          //
      while(row<5 && col>=0)                              //
                                                          //
      {                                                   //
        real=median-Brray[AS*AS/2-1];                     //
        Array[row][col]=Brray[real];                      //
        real++;                                           //
        col--;                                            //
        row++;                                            //
      }                                                   //
    }                                                     //
                                                          //
    else                                                  //
    {                                                     //
      median=Brray[AS*AS/2];
      //We start filling at Brray[AS*AS/2-AS/2]

      while(row<5 && col>=0)
      {
        real=Brray[AS*AS/2-AS/2];
        Array[row][col]=Brray[real];
        real++;
        col--;
        row++;
      }

    }                                                     //

  }
  
  // Second loop goes here
}

When you compile, tell VS to complain about everything it finds wrong. This will help you get rid of unused variables and things like that.

Also, the something changed in the forum BBCode and broke the [i] stuff -- a feature I had asked for but is problematic because everyone seems to like to use i and j as loop variable names.

Speaking of variable names, try to pick names that are descriptive and less cutesy. It is OK to reuse a name like n or j in unrelated loops in the same function, just like you reuse the name Array in every function. This is a secondary concern for you, though, so don't worry about it too much right now.

Think about the stuff in the sorting() function.

Hope this helps.
Topic archived. No new replies allowed.