# Thread: two dimensional array sorting in C/C++

1. ## two dimensional array sorting in C/C++

Hello everyone,

I have a two dimensional array. Currently, I am using the following method to sort,

1. Sort by the first dimension,
2. If the first dimension is equal, then sort by the second dimension.

For example, here is the result of the array I could get,

<result 1>

[1, 2]
[1, 3]
[1, 6]
[2, 4]
[2, 5]
[2, 7]

I want to change it to,

1. Sort by the second dimension,
2. If the second dimension is equal, then sort by the first dimension.

Here is the result I want to get,

<result 2>

[1, 2]
[1, 3]
[2, 4]
[2, 5]
[1, 6]
[2, 7]

I am wondering what is the most efficient way to get the new sorting result (result 2) by the sorting result (result 1) in old method?

George

2. You mean you want to know if your result1 can make it faster to get to result 2 ?

Hmmm...If that is the case, your best bet may be counting sort, which is a O(n) search.

3. Just use qsort() with an appropriate compare function.

4. qsort would be much better. Counting sort is pretty bad on space for larger array sizes.

5. The unintuitive thing about Quicksort is that the MORE mixed up the data is - the better it's performance will be.

IMO the best way to resort the data according to new keys, would be to just ignore the old data, and give it to Qsort.

(Which is quite the wonder, imo).

6. Thank you Happy_Reaper,

Originally Posted by Happy_Reaper
You mean you want to know if your result1 can make it faster to get to result 2 ?

Hmmm...If that is the case, your best bet may be counting sort, which is a O(n) search.
I can not imagine that applying counting sort in my application could be O(n). Could you describe your ideas in more details please?

regards,
George

7. Hi Salem,

Originally Posted by Salem
Just use qsort() with an appropriate compare function.
If use qsort in a brute-force way, I can not utilize the useful information that the two dimensional array is already sorted from left to right. I am wondering how to find a smart/efficient implementation by utilizing the information that the input two dimensional array is already sorted from left to right.

regards,
George

8. Hi kris.c,

Originally Posted by kris.c
qsort would be much better. Counting sort is pretty bad on space for larger array sizes.
If use qsort in a brute-force way, I can not utilize the useful information that the two dimensional array is already sorted from left to right. I am wondering how to find a smart/efficient implementation by utilizing the information that the input two dimensional array is already sorted from left to right.

regards,
George

9. Thank you Adak, I think ignore the existing information (columns are already sorted from left to right) would be a waste. :-)

Originally Posted by Adak
The unintuitive thing about Quicksort is that the MORE mixed up the data is - the better it's performance will be.

IMO the best way to resort the data according to new keys, would be to just ignore the old data, and give it to Qsort.

(Which is quite the wonder, imo).

If use qsort in a brute-force way, I can not utilize the useful information that the two dimensional array is already sorted from left to right. I am wondering how to find a smart/efficient implementation by utilizing the information that the input two dimensional array is already sorted from left to right.

regards,
George

10. I hear an echo, echo, echo...

11. Any good ideas, dude? :-)

Originally Posted by Wraithan
I hear an echo, echo, echo...
I reply to each one because someone is monitoring email reply then comes here. I do not want them to miss the reply if they do not come here.

regards,
George

12. Originally Posted by George2
Thank you Adak, I think ignore the existing information (columns are already sorted from left to right) would be a waste. :-)
George
What's unbelievable, is that Qsort is FASTER on sorting TOTALLY unsorted data, than it is at sorting ALMOST perfectly sorted data.

I could go on and on about the selection of the pivot point, yada, yada, yada. Instead, I'll just say "try it out, youself, and see what happens". I promise - you'll be amazed.

Perhaps someone who's better with data structures or algorithms than I, can give you better advice. I'm sure this is a well-studied area in CS, since it must be common, and also must require (seemingly), a very great deal of CS resources to re-sort data that's already been sorted by a different key.

Good luck, George2!

13. *shrug*
Code:
```#include <stdio.h>
#include <stdlib.h>

void print ( int a[][2], int n ) {
int i;
for ( i = 0 ; i < n ; i++ ) {
printf( "%d %d\n", a[i][0], a[i][1] );
}
printf("--\n");
}
int compare ( const void *pa, const void *pb ) {
int (*a)[2] = pa;
int (*b)[2] = pb;
if ( a[0][1] < b[0][1] ) return -1;
if ( a[0][1] > b[0][1] ) return +1;
return 0;
}
int main() {
int data[][2] = {
{1, 2},
{1, 3},
{1, 6},
{2, 4},
{2, 5},
{2, 7},
};
print( data, 6 );
qsort( data, 6, sizeof data[0], compare );
print( data, 6 );
return 0;
}

\$ ./a.exe
1 2
1 3
1 6
2 4
2 5
2 7
--
1 2
1 3
2 4
2 5
1 6
2 7
--```

14. Originally Posted by Adak
What's unbelievable, is that Qsort is FASTER on sorting TOTALLY unsorted data, than it is at sorting ALMOST perfectly sorted data.

I could go on and on about the selection of the pivot point, yada, yada, yada. Instead, I'll just say "try it out, youself, and see what happens". I promise - you'll be amazed.

Perhaps someone who's better with data structures or algorithms than I, can give you better advice. I'm sure this is a well-studied area in CS, since it must be common, and also must require (seemingly), a very great deal of CS resources to re-sort data that's already been sorted by a different key.

Good luck, George2!
Thank you Adak! I will try to find whether there are any better ideas, if no better ways, I will use quick sort.

regards,
George

15. Originally Posted by Salem
*shrug*
Code:
```#include <stdio.h>
#include <stdlib.h>

void print ( int a[][2], int n ) {
int i;
for ( i = 0 ; i < n ; i++ ) {
printf( "%d %d\n", a[i][0], a[i][1] );
}
printf("--\n");
}
int compare ( const void *pa, const void *pb ) {
int (*a)[2] = pa;
int (*b)[2] = pb;
if ( a[0][1] < b[0][1] ) return -1;
if ( a[0][1] > b[0][1] ) return +1;
return 0;
}
int main() {
int data[][2] = {
{1, 2},
{1, 3},
{1, 6},
{2, 4},
{2, 5},
{2, 7},
};
print( data, 6 );
qsort( data, 6, sizeof data[0], compare );
print( data, 6 );
return 0;
}

\$ ./a.exe
1 2
1 3
1 6
2 4
2 5
2 7
--
1 2
1 3
2 4
2 5
1 6
2 7
--```
Your implementation is cool. Two more comments,

1. Your implementation does not takes into account the given information that the data is already sorted in a 1st column -- 2nd column way, and just simply treat it as a normal un-sorted data. I think if we do not take fully utilization of the given information, the implementation is not optimized. Agree? Any better ideas?

2. What means "int (*a)[2]"? a is a type of int pointer points to what? It is weird to me... :-)

regards,
George

Popular pages Recent additions