By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
445,918 Members | 2,225 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 445,918 IT Pros & Developers. It's quick & easy.

how to sort parallel arrays in c++?

P: n/a
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!
Jul 22 '05 #1
Share this Question
Share on Google+
6 Replies


P: n/a
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
Jul 22 '05 #2

P: n/a
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.
Jul 22 '05 #3

P: n/a
* 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?
Jul 22 '05 #4

P: n/a
"Xiaozhu" <ge********@gmail.com> wrote in message
news:f8**************************@posting.google.c om...
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
Jul 22 '05 #5

P: n/a
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[i];
sales[i] = sales[j];
sales[j] = temp;

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

temp = id[i];
id[i] = 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
kb******@gascad.at
Jul 22 '05 #6

P: n/a
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

Jul 22 '05 #7

This discussion thread is closed

Replies have been disabled for this discussion.