| 08 September 2024 | Challenge 284 |
Sorting Without Sort
Task 2: Relative Sort
Submitted by: Mohammad Sajid Anwar
You are given two list of integers, @list1 and @list2. The elements in the @list2 are distinct and also in the @list1.
Write a script to sort the elements in the @list1 such that the relative order of items in @list1 is same as in the @list2. Elements that is missing in @list2 should be placed at the end of @list1 in ascending order.
Example 1
Input: @list1 = (2, 3, 9, 3, 1, 4, 6, 7, 2, 8, 5)
@list2 = (2, 1, 4, 3, 5, 6)
Ouput: (2, 2, 1, 4, 3, 3, 5, 6, 7, 8, 9)
Example 2
Input: @list1 = (3, 3, 4, 6, 2, 4, 2, 1, 3)
@list2 = (1, 3, 2)
Ouput: (1, 3, 3, 3, 2, 2, 4, 4, 6)
Example 3
Input: @list1 = (3, 0, 5, 0, 2, 1, 4, 1, 1)
@list2 = (1, 0, 3, 2)
Ouput: (1, 1, 1, 0, 0, 3, 2, 4, 5)
Solution
This is a follow-up to my post for challenge 284.
While solving that task, I became obsessed with the idea of collecting the list items in a binary search tree (BST, more specifically: a balanced BST), while classifying these as members of partition 1 or partition 2. In week 284 I didn’t find a solution with an acceptable performance. Afterwards I discovered the exellent module Tree::RB::XS as the perfect solution.
We create two BSTs: one is pre-initialized with the members of @list2 and with recent tracking enabled and a second empty one.
While scanning through @list1, its members are counted in the first tree if the key exists or in the second otherwise.
The way I chose to count the elements is highly questionable.
I asked about it at PerlMonks and I’m afraid it is not commonly accepted as good practice.
In a second pass, the first tree is traversed in order of initialization and the second in key-order. Elements are repeated according to their count.
use strict;
use warnings;
use Tree::RB::XS ':cmp';
use experimental 'signatures';
sub relative_sort ($list1, $list2) {
my $part1 = Tree::RB::XS->new(compare_fn => CMP_INT, track_recent => 1);
my $part2 = Tree::RB::XS->new(compare_fn => CMP_INT);
$part1->insert($_, 0) for @$list2;
${\($part1->get($_) // $part2->get_or_add($_))}++ for @$list1;
[
map +($_->key) x $_->value,
$part1->iter_newer->next('*'),
$part2->iter->next('*')
];
}
See the full solution to task 2.
If you have a question about this post or if you like to comment on it, feel free to open an issue in my github repository.