Partial sorting with np.partition() in NumPy - Step-by-Step Execution

Concept Flow - Partial sorting with np.partition()

Input array and k

↓

Call np.partition(arr, k)

↓

Partition array so elements < kth are left

↓

Elements >= kth are right

↓

Return reference to partitioned array (not in-place)

np.partition() rearranges the array so that the element at index k is in its sorted position, with smaller elements before it and larger after, without fully sorting.

Execution Sample

NumPy

import numpy as np
arr = np.array([7, 2, 5, 3, 9])
result = np.partition(arr, 2)
print(arr)
print(result)

This code partially sorts the array so the element at index 2 is in correct sorted position. 'result' is a new array with the partitioned result; 'arr' remains unchanged.

Execution Table

Step	Input Array	k	Partitioned Array	Explanation
1	[7, 2, 5, 3, 9]	2	[3, 2, 5, 7, 9]	np.partition places element at index 2 (5) correctly; smaller elements left, larger right (order within partitions not guaranteed)
2	[3, 2, 5, 7, 9]	2	[2, 3, 5, 7, 9]	Illustrative: further partitioning may reorder within left partition, but single np.partition call produces one such arrangement
3	[2, 3, 5, 7, 9]	2	[2, 3, 5, 7, 9]	Final output: element at index 2 is 5, smaller elements left, larger right
Exit				Partitioning complete; array partially sorted around index 2

💡 np.partition stops after placing kth element correctly; no full sort done. Does NOT modify input in-place.

Variable Tracker

Variable	Start	After Step 1	After Step 2	Final
arr	[7, 2, 5, 3, 9]	[7, 2, 5, 3, 9]	[7, 2, 5, 3, 9]	[7, 2, 5, 3, 9]
k	2	2	2	2
result	None	[3, 2, 5, 7, 9]	[2, 3, 5, 7, 9]	[2, 3, 5, 7, 9]

Key Moments - 2 Insights

Why isn't the entire array fully sorted after np.partition?

np.partition only guarantees the element at index k is in the correct sorted position; elements before and after are not fully sorted, just partitioned. See execution_table step 1 and 2.

Does np.partition change the original array or return a new one?

np.partition returns a new array with the partitioned result; the original array remains unchanged. In the example, 'arr' is unchanged and 'result' is the partitioned array. See variable_tracker.

Visual Quiz - 3 Questions

Look at the execution_table at step 1, what is the element at index 2 in the partitioned array?

A 5

B 3

C 7

D 2

💡 Hint

Check the 'Partitioned Array' column at step 1 in execution_table

At which step does the array become [2, 3, 5, 7, 9]?

A Step 1

B Step 3

C Step 2

D Exit

💡 Hint

Look at the 'Partitioned Array' column for each step in execution_table

If k was changed to 0, what would np.partition guarantee about the array?

A The largest element is at index 0

B The smallest element is at index 0

C The array is fully sorted

D No change to the array

💡 Hint

np.partition places the kth element in sorted position; k=0 means smallest element at index 0

Concept Snapshot

np.partition(array, k)
- Partially sorts array
- Element at index k is in sorted position
- Elements before k are smaller or equal
- Elements after k are larger or equal
- Does NOT fully sort the array
- Returns a new array; original unchanged

Full Transcript

np.partition takes an array and an index k. It returns a new array rearranged so that the element at position k is the same as if the array was fully sorted. Elements before k are smaller or equal, and elements after k are larger or equal. The array is not fully sorted, only partitioned around the kth element. This is useful when you want to find the kth smallest element quickly without sorting everything. The example shows an array [7, 2, 5, 3, 9] partitioned at k=2. The output array has the element 5 at index 2, with smaller elements on the left and larger on the right. The order inside partitions is not guaranteed. np.partition does NOT modify the input array in-place; it returns a new array.