how to sort parallel arrays in c++?

Discussion in 'C++' started by Xiaozhu, Aug 31, 2004.

  1. Xiaozhu

    Xiaozhu Guest

    say, if you had parallel arrays containing the sales person id, the month, and
    the sales figures (for that person in that month), sorting on sales figure and
    preserve the order of figures within the data about the same person:

    Original Data:
    id month sales
    +-----+ +-----+ +-----+
    | 432 | | 8 | | 89 |
    +-----+ +-----+ +-----+
    | 123 | | 8 | | 116 |
    +-----+ +-----+ +-----+
    | 555 | | 8 | | 203 |
    +-----+ +-----+ +-----+
    | 432 | | 9 | | 105 |
    +-----+ +-----+ +-----+
    | 123 | | 9 | | 143 |
    +-----+ +-----+ +-----+
    | 555 | | 9 | | 187 |
    +-----+ +-----+ +-----+

    Sorted by sales:
    id month sales
    +-----+ +-----+ +-----+
    | 432 | | 8 | | 89 |
    +-----+ +-----+ +-----+
    | 432 | | 9 | | 105 |
    +-----+ +-----+ +-----+
    | 123 | | 8 | | 116 |
    +-----+ +-----+ +-----+
    | 123 | | 9 | | 143 |
    +-----+ +-----+ +-----+
    | 555 | | 9 | | 187 |
    +-----+ +-----+ +-----+
    | 555 | | 8 | | 203 |
    +-----+ +-----+ +-----+

    is that possible to do this in c++? Thanks!
     
    Xiaozhu, Aug 31, 2004
    #1
    1. Advertising

  2. Xiaozhu wrote:
    > say, if you had parallel arrays containing the sales person id, the month, and
    > the sales figures (for that person in that month), sorting on sales figure and
    > preserve the order of figures within the data about the same person:
    >
    > Original Data:
    > id month sales
    > +-----+ +-----+ +-----+
    > | 432 | | 8 | | 89 |
    > +-----+ +-----+ +-----+
    > | 123 | | 8 | | 116 |
    > +-----+ +-----+ +-----+
    > | 555 | | 8 | | 203 |
    > +-----+ +-----+ +-----+
    > | 432 | | 9 | | 105 |
    > +-----+ +-----+ +-----+
    > | 123 | | 9 | | 143 |
    > +-----+ +-----+ +-----+
    > | 555 | | 9 | | 187 |
    > +-----+ +-----+ +-----+
    >
    > Sorted by sales:
    > id month sales
    > +-----+ +-----+ +-----+
    > | 432 | | 8 | | 89 |
    > +-----+ +-----+ +-----+
    > | 432 | | 9 | | 105 |
    > +-----+ +-----+ +-----+
    > | 123 | | 8 | | 116 |
    > +-----+ +-----+ +-----+
    > | 123 | | 9 | | 143 |
    > +-----+ +-----+ +-----+
    > | 555 | | 9 | | 187 |
    > +-----+ +-----+ +-----+
    > | 555 | | 8 | | 203 |
    > +-----+ +-----+ +-----+
    >
    > is that possible to do this in c++? Thanks!


    Your problem is not defined enough. There is ambiguity. What
    should happen if the initial data are

    +-----+ +-----+ +-----+
    | 432 | | 8 | | 89 |
    +-----+ +-----+ +-----+
    | 123 | | 8 | | 116 |
    +-----+ +-----+ +-----+
    | 555 | | 8 | | 203 |
    +-----+ +-----+ +-----+
    | 432 | | 9 | | 105 |
    +-----+ +-----+ +-----+
    | 123 | | 9 | | 103 | ** different than yours
    +-----+ +-----+ +-----+
    | 555 | | 9 | | 187 |
    +-----+ +-----+ +-----+

    ?

    My answer is this: I'd not have "parallel arrays". I'd put all
    the values in a structure

    struct salesdata {
    int id;
    int month;
    int value;
    };

    and sorted the array of these structs based on some criteria.

    Victor
     
    Victor Bazarov, Aug 31, 2004
    #2
    1. Advertising

  3. Xiaozhu

    osmium Guest

    Xiaozhu writes:

    > say, if you had parallel arrays containing the sales person id, the month,

    and
    > the sales figures (for that person in that month), sorting on sales figure

    and
    > preserve the order of figures within the data about the same person:


    That's a severe problem with parallel arrays and is one of the many reasons
    you need structures.
     
    osmium, Aug 31, 2004
    #3
  4. * Xiaozhu:
    > say, if you had parallel arrays containing the sales person id, the month, and
    > the sales figures (for that person in that month), sorting on sales figure and
    > preserve the order of figures within the data about the same person:
    >
    > Original Data:
    > id month sales
    > +-----+ +-----+ +-----+
    > | 432 | | 8 | | 89 |
    > +-----+ +-----+ +-----+
    > | 123 | | 8 | | 116 |
    > +-----+ +-----+ +-----+
    > | 555 | | 8 | | 203 |
    > +-----+ +-----+ +-----+
    > | 432 | | 9 | | 105 |
    > +-----+ +-----+ +-----+
    > | 123 | | 9 | | 143 |
    > +-----+ +-----+ +-----+
    > | 555 | | 9 | | 187 |
    > +-----+ +-----+ +-----+
    >
    > Sorted by sales:
    > id month sales
    > +-----+ +-----+ +-----+
    > | 432 | | 8 | | 89 |
    > +-----+ +-----+ +-----+
    > | 432 | | 9 | | 105 |
    > +-----+ +-----+ +-----+
    > | 123 | | 8 | | 116 |
    > +-----+ +-----+ +-----+
    > | 123 | | 9 | | 143 |
    > +-----+ +-----+ +-----+
    > | 555 | | 9 | | 187 |
    > +-----+ +-----+ +-----+
    > | 555 | | 8 | | 203 |
    > +-----+ +-----+ +-----+
    >
    > is that possible to do this in c++? Thanks!


    Well the problem has nothing to do with parallell arrays (because you can
    always just sort an array of indices to the real arrays), but it has to do
    with availability of a _stable_ sort, one which preserves the order of
    records with equal keys.

    You can implement a stable sort yourself, but I gather the question is
    whether the built-in sorting algorithms in the standard library are stable.

    list::sort is documented as stable in §23.2.2.4/31, and also <algorithm>
    has a stable sort called, suprise!, std::stable_sort (§25.3.1.2).

    --
    A: Because it messes up the order in which people normally read text.
    Q: Why is it such a bad thing?
    A: Top-posting.
    Q: What is the most annoying thing on usenet and in e-mail?
     
    Alf P. Steinbach, Aug 31, 2004
    #4
  5. Xiaozhu

    Mabden Guest

    "Xiaozhu" <> wrote in message
    news:...
    > say, if you had parallel arrays containing the sales person id, the month,

    and
    > the sales figures (for that person in that month), sorting on sales figure

    and
    > preserve the order of figures within the data about the same person:
    >
    > Original Data:
    > id month sales
    > +-----+ +-----+ +-----+
    > | 432 | | 8 | | 89 |
    > +-----+ +-----+ +-----+
    > | 123 | | 8 | | 116 |
    > +-----+ +-----+ +-----+
    > | 555 | | 8 | | 203 |
    > +-----+ +-----+ +-----+
    > | 432 | | 9 | | 105 |
    > +-----+ +-----+ +-----+
    > | 123 | | 9 | | 143 |
    > +-----+ +-----+ +-----+
    > | 555 | | 9 | | 187 |
    > +-----+ +-----+ +-----+
    >
    > Sorted by sales:
    > id month sales
    > +-----+ +-----+ +-----+
    > | 432 | | 8 | | 89 |
    > +-----+ +-----+ +-----+
    > | 432 | | 9 | | 105 |
    > +-----+ +-----+ +-----+
    > | 123 | | 8 | | 116 |
    > +-----+ +-----+ +-----+
    > | 123 | | 9 | | 143 |
    > +-----+ +-----+ +-----+
    > | 555 | | 9 | | 187 |
    > +-----+ +-----+ +-----+
    > | 555 | | 8 | | 203 |
    > +-----+ +-----+ +-----+
    >
    > is that possible to do this in c++? Thanks!


    Perhaps I'm missing something, but it seems to me a linked list of pointers
    would do what you want quite easily. Something like:

    struct StrSales {
    StrSales *next;
    int *id;
    int *month;
    int *sales;
    };

    This can then be made into a list that points to the original arrays so they
    are not changed, but you can sort them anyway you wish by stepping through
    the linked list.

    I wonder if I explained that right, but I hope you see the concept.

    --
    Mabden
     
    Mabden, Sep 1, 2004
    #5
  6. Xiaozhu wrote:
    >
    > say, if you had parallel arrays containing the sales person id, the month, and
    > the sales figures (for that person in that month), sorting on sales figure and
    > preserve the order of figures within the data about the same person:
    >
    > Original Data:
    > id month sales
    > +-----+ +-----+ +-----+
    > | 432 | | 8 | | 89 |
    > +-----+ +-----+ +-----+
    > | 123 | | 8 | | 116 |
    > +-----+ +-----+ +-----+
    > | 555 | | 8 | | 203 |
    > +-----+ +-----+ +-----+
    > | 432 | | 9 | | 105 |
    > +-----+ +-----+ +-----+
    > | 123 | | 9 | | 143 |
    > +-----+ +-----+ +-----+
    > | 555 | | 9 | | 187 |
    > +-----+ +-----+ +-----+
    >
    > Sorted by sales:
    > id month sales
    > +-----+ +-----+ +-----+
    > | 432 | | 8 | | 89 |
    > +-----+ +-----+ +-----+
    > | 432 | | 9 | | 105 |
    > +-----+ +-----+ +-----+
    > | 123 | | 8 | | 116 |
    > +-----+ +-----+ +-----+
    > | 123 | | 9 | | 143 |
    > +-----+ +-----+ +-----+
    > | 555 | | 9 | | 187 |
    > +-----+ +-----+ +-----+
    > | 555 | | 8 | | 203 |
    > +-----+ +-----+ +-----+
    >
    > is that possible to do this in c++? Thanks!


    Sure.
    It's not that hard, if you write the sorting function
    on your own.
    Every sort algorithm needs to do 2 things:
    compare array elements
    eventually swap array elements

    The first one is easy: Just code in on what array wou
    want the comparison be based.
    The second one is easy to: Instead of just swapping
    the entries of a single array, you swap the elements
    of all the parallel arrays at the same index positions:

    ....
    temp = sales;
    sales = sales[j];
    sales[j] = temp;

    temp = month;
    month = month[j];
    month[j] = temp;

    temp = id;
    id = id[j];
    id[j] = temp;
    ....

    The idea is: Whatever you do to one array, you do to all
    of the parallel arrays. This way they stay always in sync.


    *But* - The bigger question is:
    Why do you have parallel arrays in the first place? You
    should have a struct which models a single entry consisting
    of id, month and sales and then have an array of those.

    --
    Karl Heinz Buchegger
     
    Karl Heinz Buchegger, Sep 1, 2004
    #6
  7. Xiaozhu

    Rich Grise Guest

    On Tuesday 31 August 2004 09:53 am, Xiaozhu did deign to grace us with the
    following:

    > say, if you had parallel arrays containing the sales person id, the month,
    > and the sales figures (for that person in that month), sorting on sales
    > figure and preserve the order of figures within the data about the same
    > person:
    >
    > Original Data:
    > id month sales
    > +-----+ +-----+ +-----+
    > | 432 | | 8 | | 89 |

    ....
    > is that possible to do this in c++? Thanks!


    I'm only a C++ n00b, but I've copied and pasted my fair share of code ;-),
    and the first thing that jumped out at me was "spreadsheet."

    My comment would put the thread OT for the NG, but isn't there a facility
    to bring in objects from other apps' libraries? Just instantiate some kind
    of spreadsheet class. But that's implementation-dependent, so I'll go
    flog myself now. ;-)

    Cheers!
    Rich
     
    Rich Grise, Sep 9, 2004
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Soren
    Replies:
    4
    Views:
    1,341
    c d saunter
    Feb 14, 2008
  2. Philipp
    Replies:
    21
    Views:
    1,181
    Philipp
    Jan 20, 2009
  3. Vivek Menon
    Replies:
    5
    Views:
    3,491
    Paul Uiterlinden
    Jun 8, 2011
  4. Vivek Menon
    Replies:
    0
    Views:
    1,801
    Vivek Menon
    Jun 10, 2011
  5. Navin
    Replies:
    1
    Views:
    761
    Ken Schaefer
    Sep 9, 2003
Loading...

Share This Page