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

  1. #1
    Registered User
    Join Date
    May 2006
    Posts
    1,579

    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

  2. #2
    Fear the Reaper...
    Join Date
    Aug 2005
    Location
    Toronto, Ontario, Canada
    Posts
    625
    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.
    Teacher: "You connect with Internet Explorer, but what is your browser? You know, Yahoo, Webcrawler...?" It's great to see the educational system moving in the right direction

  3. #3
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Just use qsort() with an appropriate compare function.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  4. #4
    Eager young mind
    Join Date
    Jun 2006
    Posts
    342
    qsort would be much better. Counting sort is pretty bad on space for larger array sizes.
    In the middle of difficulty, lies opportunity

  5. #5
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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

  6. #6
    Registered User
    Join Date
    May 2006
    Posts
    1,579
    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

  7. #7
    Registered User
    Join Date
    May 2006
    Posts
    1,579
    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

  8. #8
    Registered User
    Join Date
    May 2006
    Posts
    1,579
    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

  9. #9
    Registered User
    Join Date
    May 2006
    Posts
    1,579
    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

  10. #10
    pwns nooblars
    Join Date
    Oct 2005
    Location
    Portland, Or
    Posts
    1,094
    I hear an echo, echo, echo...

  11. #11
    Registered User
    Join Date
    May 2006
    Posts
    1,579
    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

  12. #12
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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

  13. #13
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    *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
    --
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  14. #14
    Registered User
    Join Date
    May 2006
    Posts
    1,579
    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

  15. #15
    Registered User
    Join Date
    May 2006
    Posts
    1,579
    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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Array Sorting problem
    By ___________ in forum C++ Programming
    Replies: 4
    Last Post: 07-22-2008, 12:17 AM
  2. Replies: 2
    Last Post: 07-11-2008, 07:39 AM
  3. two dimensional array
    By leisiminger in forum C Programming
    Replies: 12
    Last Post: 03-09-2008, 11:53 PM
  4. two dimensional string array question
    By Hoser83 in forum C Programming
    Replies: 8
    Last Post: 02-07-2006, 08:15 PM
  5. Type and nontype parameters w/overloading
    By Mr_LJ in forum C++ Programming
    Replies: 3
    Last Post: 01-02-2004, 01:01 AM