2724. Sort By


Problem Description

In this problem, you are provided with two inputs: an array arr which can contain any type of elements, and a function fn which takes one of the elements of arr as an argument and returns a number. The task is to sort the array arr not by its actual values but by the numbers returned when each element is passed through the function fn. The output should be a new array sortedArr where the elements are ordered in ascending order based on the corresponding numbers returned from fn. It is guaranteed that fn will give a unique number for each element in the array, ensuring that there is a clear sort order.

Intuition

The given TypeScript function sortBy takes in arr and fn and uses the sort function to rearrange the elements in arr. In TypeScript and JavaScript, the sort function allows for a custom comparator, a function that takes in two elements and decides their order.

In this case, the comparator is ((a, b) => fn(a) - fn(b)). This is a function that calls fn on both elements a and b, subtracts the result of calling fn on b from the result of calling fn on a, and uses the result of the subtraction to determine their order:

  • If fn(a) - fn(b) is less than 0, a comes before b in the sorted array.
  • If fn(a) - fn(b) is greater than 0, b comes before a in the sorted array.
  • If fn(a) - fn(b) is 0 (which won't happen as fn returns unique numbers), a and b would be considered equal in terms of sorting, but this scenario is excluded per the problem assumptions.

This use of the custom comparator in the sort method achieves the goal of sorting the array by the values returned from the function fn. Since arr.sort sorts the elements of arr in place and the comparator ensures it is in ascending order by fn output, sortBy returns the correctly sorted array.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?

Solution Approach

The implementation of the solution involves using the sort method which is a built-in functionality of JavaScript and TypeScript arrays. This method sorts the elements of an array in place and can order them according to the return value of a provided function.

In our sortBy function, we use arr.sort((a, b) => fn(a) - fn(b)). Here's how it breaks down:

  • arr: This is the array of elements we need to sort.
  • .sort(): This method accepts a comparator function that determines the sort order.
  • (a, b): The comparator function receives two elements from the array at a time.
  • fn(a) - fn(b): Inside the comparator, we apply the fn function to each element a and b, then subtract the result of b from a. The resulting number is used by sort to determine their order.

Remember, the sort method by default converts elements into strings and compares their sequences of UTF-16 code units values. However, when provided with a comparator function, it behaves as per the logic you provide in that function.

For the algorithms, data structures, or patterns used:

  • Algorithm: The specific sort algorithm used by .sort() is dependent on the JavaScript engine implementation. It could be quicksort, mergesort, or another algorithm optimized for different types of arrays and sizes. However, you don't need to know these specifics to use the method.

  • Data Structures: Since we're sorting an array and not using any additional data structures, the only relevant data structure is the input array itself.

  • Patterns: A common programming pattern used here is the usage of higher-order functions. fn is a higher-order function since it takes a function as an argument (our comparator function) and returns a value based on the invocation of that function.

By using this approach, we get a sorted array based on the specified conditions using concise and effective code.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How does quick sort divide the problem into subproblems?

Example Walkthrough

Let's consider arr is an array of objects where each object has a name and an age property. We want to sort this array by the age of each person in ascending order.

1const people = [
2  { name: "Alice", age: 25 },
3  { name: "Bob", age: 20 },
4  { name: "Charlie", age: 30 }
5];
6
7function getAge(person) {
8  return person.age;
9}
10
11const sortedPeople = sortBy(people, getAge);

In the example above, our arr is the people array and our fn is the getAge function which extracts the age from an object.

Here's what happens step-by-step when our sortBy function processes the people array using the getAge function as fn:

  1. The sortBy function calls arr.sort((a,b) => fn(a) - fn(b)), passing in our custom comparator.
  2. The sort method begins to compare elements in the array using the comparator function:
    • It compares two elements of people, say Alice and Bob, by calling getAge(Alice) which returns 25 and getAge(Bob) which returns 20.
    • The computation fn(a) - fn(b) translates to 25 - 20, which is 5. Since the result is positive, Bob will come before Alice in the sorted array.
  3. This process repeats for each pair of elements in the array, effectively organizing the entire people array according to the ages of the people in ascending order.
  4. The sortBy function returns a new array sortedPeople:
    • [ { name: "Bob", age: 20 }, { name: "Alice", age: 25 }, { name: "Charlie", age: 30 } ]

After the execution of sortBy, the sortedPeople array is sorted by the age property. This walk-through illustrates the elegant and efficient use of the sort method with a custom comparator function to sort objects by their specified properties.

Solution Implementation

1from typing import List, Callable
2
3def sort_by(array: List[T], comparator: Callable[[T], int]) -> List[T]:
4    """
5    Sorts an array based on a provided comparator function.
6  
7    :param array: The array to be sorted.
8    :param comparator: A function that takes an item and returns a number,
9                       representing that item's position in the sort order.
10    :return: The sorted array.
11    """
12  
13    # Use the list's sort method by providing a lambda that calls
14    # the comparator function to determine the sort order.
15    # In Python, the sort method sorts the list in place.
16  
17    array.sort(key=comparator)
18    return array
19
1import java.util.Collections;
2import java.util.Comparator;
3import java.util.List;
4
5/**
6 * Sorts a list based on a provided comparator function.
7 * @param <T> The type of elements in the list.
8 * @param list The list to be sorted.
9 * @param comparator A Comparator that compares two elements.
10 * @return The sorted list.
11 */
12public static <T> List<T> sortBy(List<T> list, Comparator<T> comparator) {
13    // Use the Collections.sort method, passing in the list and the comparator.
14    Collections.sort(list, comparator);
15    return list;
16}
17
1#include <vector>
2#include <algorithm>
3
4/**
5 * Sorts a vector based on a provided comparator function.
6 * @param array The vector to be sorted.
7 * @param comparator A function or functor that takes an item and returns a number,
8 * representing that item's position in the sort order.
9 * @returns The sorted vector.
10 */
11template<typename T>
12std::vector<T> sortBy(std::vector<T> array, const std::function<int(T)> &comparator) {
13    // Use the standard library's sort function, passing in a lambda that uses the
14    // comparator to determine the sort order.
15    std::sort(array.begin(), array.end(), [&comparator](const T &a, const T &b) {
16        return comparator(a) < comparator(b);
17    });
18    return array;
19}
20
1/**
2 * Sorts an array based on a provided comparator function.
3 * @param {T[]} array The array to be sorted.
4 * @param {(item: T) => number} comparator A function that takes an item and returns a number,
5 * representing that item's position in the sort order.
6 * @returns {T[]} The sorted array.
7 */
8function sortBy<T>(array: T[], comparator: (item: T) => number): T[] {
9    // Use the array sort function, passing in a lambda that uses the
10    // comparator to determine the sort order.
11    return array.sort((a, b) => comparator(a) - comparator(b));
12}
13
Not Sure What to Study? Take the 2-min Quiz:

A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".

What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?

Time and Space Complexity

The time complexity of the sortBy function largely depends on the implementation of the .sort() method in JavaScript's V8 engine (used in Chrome and Node.js). This method generally uses the TimSort algorithm for arrays that have more than a certain number of elements, which has a time complexity of O(n log n) on average and in the worst case. For smaller arrays, it may use an algorithm similar to insertion sort, which has a worst case time complexity of O(n^2).

The space complexity for TimSort is O(n). This is due to the need for allocating temporary arrays for storing merged sequences during the sorting process.

A key consideration here is the complexity of the fn function that is being used to compare elements. If the complexity of this function is O(f(n)), it should be multiplied by the sorting complexity. The overall time complexity would then become O(n log n * f(n)) for large arrays.

In summary:

  • TimSort time complexity: O(n log n)
  • TimSort space complexity: O(n)
  • Overall time complexity (including fn): O(n log n * f(n))
Fast Track Your Learning with Our Quick Skills Quiz:

Which two pointer technique does Quick Sort use?


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫