Sponsored
Sponsored
This approach utilizes the built-in sorting functionality available in most programming languages, which allows for custom sorting based on a key extracted from each element. The function fn is used to transform each element to its sorting key during the sort operation.
Time Complexity: O(n log n), where n is the length of the array, due to the sort operation.
Space Complexity: O(n), as sorted() creates a new list.
1using System;
2using System.Collections.Generic;
class Program {
static void Main() {
List<int> arr = new List<int> {5, 4, 1, 2, 3};
Func<int, int> fn = x => x;
arr.Sort((a, b) => fn(a).CompareTo(fn(b)));
foreach (int num in arr) {
Console.Write(num + " ");
}
}
}C#'s List.Sort() method is employed along with a lambda comparator. Elements are compared based on keys derived using fn.
This approach involves first creating a map of the computed keys from fn for all the elements in the array. These keys are then used to guide the sorting of the original array.
Time Complexity: O(n log n), owing to the sort operation.
Space Complexity: O(n), due to the additional storage in the form of key_map.
1def sort_by(arr, fn):
2 key_map = {x: fn(x) for x in arr}
3 arr.sort(key=lambda x: key_map[x])
4 return arr
5
6# Example usage
7arr = [5, 4, 1, 2, 3]
8fn = lambda x: x
9print(sort_by(arr, fn))key_map stores the result of applying fn to each element. The array is sorted based on look-up from this dictionary during the sorting phase, providing a precomputed sort key per element.