how to sort parallel arrays in c++?

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

 

[Victor Bazarov]

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

 

[osmium]

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.

 

[Alf P. Steinbach]

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

 

[Mabden]

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.

 

[Karl Heinz Buchegger]

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.

 

[Rich Grise]

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