5 Best Ways to Perform a Relative Sort in Python

by

💡 Problem Formulation: Suppose you have two arrays – the first is to be sorted based on the order defined by the second. Given arr1 = [2, 3, 1, 4, 5] and arr2 = [5, 4, 3], the goal is to sort elements of arr1 according to the order defined in arr2, the result should look like [5, 4, 3, 1, 2] where elements not in arr2 follow in ascending order.

Method 1: Custom Sort Function with sorted()

To achieve a relative sort, one can use the built-in sorted() function with a custom sort key that prioritizes the order defined by the second array and then default to natural ordering. The approach leverages dict.get() to assign indices from the second array as prioritized values, applying a sufficiently large index for items not in the array to ensure they appear at the end, sorted naturally.

Here’s an example:

arr1 = [2, 3, 1, 4, 5]
arr2 = [5, 4, 3]
order_index = {value: index for index, value in enumerate(arr2)}
sorted_arr1 = sorted(arr1, key=lambda x: order_index.get(x, len(arr1) + x))
print(sorted_arr1)

Output:

[5, 4, 3, 1, 2]

This snippet defines a custom sort key where each element’s position is dictated first by its presence in arr2 followed by its value. This method is elegant and uses Python’s language features to solve the problem with ease.

Method 2: Using the Counter from collections

Another way to achieve relative sorting is to use the Counter class from Python’s collections module to count occurrences in arr1, then reconstruct arr1 by iterating through arr2 followed by the remaining items sorted in ascending order.

Here’s an example:

from collections import Counter

arr1 = [2, 3, 1, 4, 5]
arr2 = [5, 4, 3]
counter = Counter(arr1)
sorted_arr1 = [num for num in arr2 if num in counter for _ in range(counter[num])] + \
              sorted([num for num in arr1 if num not in arr2])
print(sorted_arr1)

Output:

[5, 4, 3, 1, 2]

In this example, Counter is used to count elements in arr1 which allows for constructing the sorted array by repeating each number based on its count. This method handles duplicate values well and gives a clear separation of the two sorting phases.

Method 3: Overloading the __lt__() Method in a Custom Class

By creating a custom class representing an element with a custom __lt__() method to overload the less-than operator based on the desired sort order, Python’s sort will act as if it is sorting in that particular order. This method encapsulates comparison logic and is useful in complex sorting scenarios.

Here’s an example:

class RelativeSortElement:
    def __init__(self, value, priority):
        self.value = value
        self.priority = priority

    def __lt__(self, other):
        if self.priority != other.priority:
            return self.priority < other.priority
        return self.value < other.value

arr1 = [2, 3, 1, 4, 5]
arr2 = [5, 4, 3]
priority_map = {val: idx for idx, val in enumerate(arr2)}
sorted_arr1 = sorted(
    [RelativeSortElement(x, priority_map.get(x, float('inf'))) for x in arr1],
    key=lambda el: el
)
sorted_arr1 = [el.value for el in sorted_arr1]
print(sorted_arr1)

Output:

[5, 4, 3, 1, 2]

In the provided code snippet, we define a RelativeSortElement class that determines ordering based on the presence in arr2 using custom comparison logic. Then, the sorted() function applies the override to achieve the desired order.

Method 4: Using NumPy’s Advanced Indexing

NumPy offers powerful array operations and advanced indexing. For relative sorting, one could map arr1 to indices in arr2, use argsort to sort by these indices, and then sort the remaining items by their values.

Here’s an example:

import numpy as np

arr1 = np.array([2, 3, 1, 4, 5])
arr2 = np.array([5, 4, 3])
sorter_index = dict(zip(arr2, range(len(arr2))))
default_index = len(arr2)

indices = [sorter_index.get(val, default_index) for val in arr1]
sorted_arr1 = arr1[np.argsort(indices)]

print(sorted_arr1)

Output:

[5 4 3 1 2]

Here, argsort() from NumPy is used to obtain the indices that would sort the array according to our custom condition. This operates at C speed due to NumPy’s optimized implementation which can be significantly faster on large datasets.

Bonus One-Liner Method 5: Utilizing List Comprehension and Sorting

The one-liner approach uses list comprehension and chaining of sorting methods to achieve relative sorting. Although less readable, it is a quick method to write the sorting logic compactly without verbose explanations.

Here’s an example:

arr1 = [2, 3, 1, 4, 5]
arr2 = [5, 4, 3]
sorted_arr1 = sorted((num for num in arr2 if num in arr1), key=arr1.index) + sorted(set(arr1) - set(arr2))
print(sorted_arr1)

Output:

[5, 4, 3, 1, 2]

This approach utilizes Python’s comprehensions and built-in functions to construct a sorted array with prioritized elements followed by the rest sorted naturally. It combines filtering and sorting in one succinct expression.

Summary/Discussion

  • Method 1: Custom Sort Function with sorted(). Uses Python language features elegantly. Not as efficient for large datasets due to Python’s overhead.
  • Method 2: Counter. Good for dealing with duplicates and is more explicit than method 1 but requires two discrete steps for sorting.
  • Method 3: Custom Class and __lt__(). Offers clear encapsulation of sorting logic but could be an overkill for simple tasks.
  • Method 4: NumPy’s Advanced Indexing. Very efficient on large datasets. However, thus it introduces a dependency on NumPy.
  • Method 5: One-Liner using List Comprehension. Quick and easy for small arrays, but lacks readability and can get complex for intricate sorting conditions.