Sorting an Array of 2-D Records

In summary, the sorting algorithm used on an array of records can result in the order (4,5), (2,5), (4,3).
  • #1
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)
 
Technology news on Phys.org
  • #2
Welcome to PF.

Sorry, does "stable" have some definition in the context of sorting algorithms? I don't remember it from my software classes.
 
  • #3
No, it just means any normal sorting algorithm
 
  • #4
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).
 
  • Like
Likes berkeman
  • #5
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.
 
  • Like
Likes berkeman
  • #6
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.
 
  • #7
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.
 
  • Like
Likes jim mcnamara

Suggested for: Sorting an Array of 2-D Records

Back
Top