np.argsort() for sort indices in NumPy - Time & Space Complexity

Time Complexity: np.argsort() for sort indices

O(n log n)

Understanding Time Complexity

We want to understand how the time needed to find sorted indices changes as the input array grows.

Specifically, how does np.argsort() behave when sorting larger arrays?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np

arr = np.random.rand(1000)
sorted_indices = np.argsort(arr)

This code creates an array of 1000 random numbers and finds the indices that would sort the array.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The sorting algorithm compares and rearranges elements to find the order.
• How many times: The sorting process involves multiple comparisons and swaps, repeating many times depending on array size.

How Execution Grows With Input

As the array size grows, the number of operations grows faster than just a simple increase.

Input Size (n)	Approx. Operations
10	About 30 to 40 operations
100	About 600 to 700 operations
1000	About 10,000 to 12,000 operations

Pattern observation: The operations grow faster than the input size itself, roughly multiplying by a bit more than n each time.

Final Time Complexity

Time Complexity: O(n log n)

This means the time needed grows a bit faster than the size of the array, but not as fast as checking every pair individually.

Common Mistake

[X] Wrong: "Sorting indices with np.argsort() takes time proportional to the array size only (O(n))."

[OK] Correct: Sorting requires comparing elements multiple times, so it takes more time than just looking at each element once.

Interview Connect

Knowing how sorting scales helps you explain performance when working with data. It shows you understand how algorithms behave with bigger inputs.

Self-Check

"What if we used np.argpartition() instead of np.argsort()? How would the time complexity change?"

Practice

1. What does the np.argsort() function return when applied to a numpy array?

easy

A. The sum of all elements in the array

B. The sorted array itself

C. The maximum value in the array

D. An array of indices that would sort the original array

Solution

1. Step 1: Understand the purpose of np.argsort()

   This function does not sort the array directly but returns the indices that would sort the array.

2. Step 2: Differentiate from sorting functions

   Unlike np.sort() which returns the sorted array, np.argsort() returns the order of indices to achieve that sorting.

3. Final Answer:

   An array of indices that would sort the original array -> Option D

4. Quick Check:

   np.argsort() = indices order [OK]

Hint: Remember: argsort returns indices, not sorted values [OK]

Common Mistakes:

• Confusing argsort with sort and expecting sorted values
• Thinking argsort returns the maximum or minimum value
• Assuming argsort returns a scalar instead of an array

2. Which of the following is the correct syntax to get the indices that would sort the array arr using a NumPy function?

easy

A. arr.sort()

B. np.argsort(arr)

C. np.sort(arr)

D. arr.argsort()

Solution

1. Step 1: Identify the numpy function for argsort

   The function np.argsort() is called with the array as argument: np.argsort(arr).

2. Step 2: Differentiate from other methods

   arr.argsort() is an array method (not the NumPy function), while np.sort(arr) returns sorted values, and arr.sort() sorts in place.

3. Final Answer:

   np.argsort(arr) -> Option B

4. Quick Check:

   Correct function call = np.argsort(arr) [OK]

Hint: Use np.argsort(array), the NumPy function, to get sort indices [OK]

Common Mistakes:

• Using arr.argsort() (array method instead of NumPy function)
• Confusing np.sort() with np.argsort()
• Using arr.sort() which sorts in place and returns None

3. Given the code:

import numpy as np
arr = np.array([40, 10, 30, 20])
indices = np.argsort(arr)
print(indices)

What will be the output?

medium

A. [1 3 2 0]

B. [3 2 1 0]

C. [0 1 2 3]

D. [1 2 3 0]

Solution

1. Step 1: Understand the array and sorting order

   The array is [40, 10, 30, 20]. Sorting it ascending gives [10, 20, 30, 40].

2. Step 2: Find indices that sort the array

   10 is at index 1, 20 at index 3, 30 at index 2, and 40 at index 0. So, indices are [1, 3, 2, 0].

3. Final Answer:

   [1 3 2 0] -> Option A

4. Quick Check:

   Sorted indices = [1 3 2 0] [OK]

Hint: Match sorted values to original indices for argsort output [OK]

Common Mistakes:

• Confusing sorted values with indices
• Reversing the order of indices
• Using sorted array instead of indices

4. What is wrong with this code snippet?

import numpy as np
arr = np.array([3, 1, 2])
indices = arr.argsort()
print(indices)

medium

A. The code will run correctly and print the sorted indices

B. The method argsort() does not exist for numpy arrays

C. The array must be sorted before calling argsort()

D. The print statement is missing parentheses

Solution

1. Step 1: Check if argsort() is a valid numpy array method

   In numpy, arrays do have an argsort() method, so arr.argsort() is valid.

2. Step 2: Verify code correctness

   The code will run and print the indices that sort the array, which are [1, 2, 0].

3. Final Answer:

   The code will run correctly and print the sorted indices -> Option A

4. Quick Check:

   arr.argsort() is valid and works [OK]

Hint: Remember numpy arrays have argsort() method too [OK]

Common Mistakes:

• Assuming argsort() is only in np module, not array method
• Thinking array must be sorted before argsort()
• Confusing Python 2 print syntax with Python 3

5. You have two related numpy arrays:

names = np.array(['apple', 'banana', 'cherry', 'date'])
prices = np.array([3.5, 2.0, 4.0, 1.5])

You want to list the fruit names sorted by their prices in ascending order. Which code snippet correctly achieves this?

hard

A. sorted_names = np.argsort(names)[prices]

B. sorted_names = np.sort(names)[np.argsort(prices)]

C. sorted_names = names[np.argsort(prices)]

D. sorted_names = names[np.sort(prices)]

Solution

1. Step 1: Use np.argsort(prices) to get indices that sort prices

   This returns indices that sort prices ascending.

2. Step 2: Use these indices to reorder names

   Indexing names with these indices sorts names by price.

3. Final Answer:

   sorted_names = names[np.argsort(prices)] -> Option C

4. Quick Check:

   Index names by argsort(prices) to sort by price [OK]

Hint: Index names by argsort of prices to sort related arrays [OK]

Common Mistakes:

• Trying to sort names directly without using indices
• Using np.sort(names) which sorts names alphabetically
• Indexing with sorted prices instead of indices