Sorting an Array of 2-D Records

• logical3902490
In summary, the sorting algorithm used on an array of records can result in the order (4,5), (2,5), (4,3).

logical3902490

I've just started learning sorting algorithms on arrays of records and wanted to ensure I'm not doing it wrong so I have a basic question.

I am sorting an array of records, where the records have two components, A and B. For example a record (3,2) has an A value of 3 and a B value of 2.

The input array has the following records in this order: (4,5), (2, 5), (4,3)

If I use any stable sorting algorithm to sort the records in increasing A values, and then use the same algorithm to sort the result of the first sort into increasing B values, will the resulting records be in this order:

(4,3) (2,5) (4,5)

Welcome to PF.

Sorry, does "stable" have some definition in the context of sorting algorithms? I don't remember it from my software classes.

No, it just means any normal sorting algorithm

logical3902490 said:
The input array has the following records in this order: (4,5), (2, 5), (4,3)

If I use any stable sorting algorithm to sort the records in increasing A values, and then use the same algorithm to sort the result of the first sort into increasing B values, will the resulting records be in this order:

(4,3) (2,5) (4,5)
Maybe not.
After sorting on the A values, you could end up with (2, 5), (4, 5), (4, 3).
After sorting this new list on the B values, the sort routine could swap the first and third tuples, and leave the one in the middle alone, resulting in (4, 3), (4, 5), (2, 5).

berkeman
Your algorithm must determine which field is the primary sort field and which is secondary. The primary sort field determines the greatest overall sort and the secondary field is a sort within the primary field values.

berkeman
berkeman said:
Sorry, does "stable" have some definition in the context of sorting algorithms? I don't remember it from my software classes.
Yes, a stable sort keeps entries that compare equal in their original order. But the OP appears to have been edited.

pbuk said:
Yes, a stable sort keeps entries that compare equal in their original order. But the OP appears to have been edited.
Ah, thanks for the heads-up. This thread is now locked with the original version of the OP restored.

@logical3902490 -- If you want to ask an updated question, please start a new thread. It is against the PF rules to substantially alter your original post, since it is completely confusing to the flow of the discussion thread. Thank you.

jim mcnamara