Sorting, unique values and searching

Intermediate

Introduction

Ranking students, finding the most common values, placing a new reading into the right time slot: these are everyday tasks on data, and they all rest on sorting and searching. NumPy does them in compiled code, and adds a few tools that plain Python lacks, such as argsort, which tells you where each value came from.

How it works

Sorting. np.sort(a) returns a sorted copy; a.sort() sorts a itself and returns None. For 2-D arrays, the default sorts each row (axis=-1); axis=0 sorts each column. For descending order, reverse the result: np.sort(a)[::-1].

argsort. np.argsort(a) returns the positions that would sort a:

a = np.array([30, 10, 20])
print(np.argsort(a))            # [1 2 0]
names = np.array(["Ann", "Ben", "Cy"])
print(names[np.argsort(a)])     # ['Ben' 'Cy' 'Ann']

This is how you sort one array by another: students by their marks, products by their price. The default algorithm does not promise any order for equal values; pass kind="stable" when ties must keep their original order.

Unique values. np.unique(a) returns the sorted distinct values. With return_counts=True it also returns how many times each appears, a quick frequency table:

values, counts = np.unique([3, 1, 3, 3], return_counts=True)
print(values, counts)           # [1 3] [1 3]

Searching. In a sorted array, np.searchsorted(a, v) uses binary search to find where v would be inserted. side="left" (the default) gives the position before any equal values, side="right" the position after them, so the difference counts how many times v appears. It also works with an array of values, and for a million elements it needs only about 20 comparisons per value.

s = np.array([1, 2, 2, 3])
print(np.searchsorted(s, 2), np.searchsorted(s, 2, side="right"))   # 1 3

Example

# Sorting and searching modelled in plain Python.
import bisect

a = [30, 10, 20, 10, 40]
print("np.sort:", sorted(a))
print("np.argsort (stable):", sorted(range(len(a)), key=lambda i: a[i]))
values = sorted(set(a))
print("np.unique:", values, "counts:", [a.count(v) for v in values])
s = sorted(a)
print("searchsorted 20 left:", bisect.bisect_left(s, 20), " right:", bisect.bisect_right(s, 20))
Open in compiler

Line by line

  1. sorted(a) models np.sort, returning a new sorted list.
  2. Sorting the positions by their values models a stable argsort; the two 10s keep their order.
  3. sorted(set(a)) with counts models np.unique(..., return_counts=True).
  4. Python's bisect module does the same binary search as searchsorted with side="left" and side="right".

Expected result

np.sort: [10, 10, 20, 30, 40]
np.argsort (stable): [1, 3, 2, 0, 4]
np.unique: [10, 20, 30, 40] counts: [2, 1, 1, 1]
searchsorted 20 left: 2  right: 3

In the real world

Leaderboards and rankings use argsort. Histograms and percentiles start by sorting. searchsorted puts timestamps into time buckets and maps values into bins for histograms, and np.unique with counts is the quickest way to see the categories in a column.

Common mistakes

  • Writing a = a.sort(), which sets a to None.
  • Calling searchsorted on unsorted data, which gives meaningless positions without any error.
  • Relying on tie order without kind="stable".
  • Using argsort's result as the sorted values rather than as positions.

Best practices

  • Use argsort to reorder several related arrays consistently.
  • Sort once, then search many times with searchsorted.
  • Use np.unique with return_counts=True for a quick frequency table.

Summary

np.sort returns a sorted copy and a.sort() sorts in place. argsort gives the positions that sort an array, used to reorder related data; np.unique gives distinct values and their counts; and searchsorted finds insertion positions in sorted arrays by binary search.

Quick check

1. What is np.argsort([5, 1, 3])?
2. What does a.sort() return?
3. For s = [1, 2, 2, 3], what is np.searchsorted(s, 2, side='right')?
4. What must be true before using searchsorted?

Key takeaways

  • np.sort returns a sorted copy; a.sort() sorts in place.
  • argsort gives positions, which can reorder other arrays the same way.
  • searchsorted needs sorted input and finds positions in logarithmic time.

Practice problems for this lesson

My notes

Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.