Sorting an Array of 2-D Records

  • #1
logical3902490
2
0
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)
 

Answers and Replies

  • #2
berkeman
Mentor
64,147
15,360
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
logical3902490
2
0
No, it just means any normal sorting algorithm
 
  • #4
36,685
8,680
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
FactChecker
Science Advisor
Homework Helper
Gold Member
7,590
3,314
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
pbuk
Science Advisor
Homework Helper
Gold Member
4,031
2,367
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
berkeman
Mentor
64,147
15,360
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

Replies
32
Views
1K
Replies
20
Views
776
  • Last Post
Replies
6
Views
542
Replies
1
Views
509
Replies
10
Views
853
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
23
Views
565
Replies
6
Views
870
Top