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?


thanks in advance,
George

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.

Just use qsort() with an appropriate compare function.

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

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).

Adak

Thank you Happy_Reaper,

Quote:

---

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

Hi Salem,

Quote:

---

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

Hi kris.c,

Quote:

---

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

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

Quote:

---

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).

Adak

---

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

I hear an echo, echo, echo...

Any good ideas, dude? :-)

Quote:

---

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

Quote:

---

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!
Adak

*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
--

---

Quote:

---

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!
Adak

---

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

Quote:

---

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

1. Salem's compare() function does most of the work: it sorts with respect to the second column only. If you write a compare function that sorts in a "first column, second column way" than qsort() will work for you as well. You can also write a function that checks whether an array is already sorted by looping through it and returning an appropriate value before you start the algorithm.

2, int (*a)[2] is a pointer to an array of two integers, iirc.

> that the data is already sorted in a 1st column
But does knowing that actually help in any way?
You can see the '1 6' result is nowhere near the rest of the '1 x' values.

Like it you have
1 10
2 9
3 8
4 7
5 6
6 5
Then the whole array ends up being reversed!
Yes, your example suggests something, but my counter example suggests something else.

Maybe you can exploit the existing order in some way, but that's gonna take weeks or months of research with no obvious sign of success at the end of it.