Sorting and Unique

Argsort

Produce the index ordering that would sort a 6-element list. The naive version builds (value, index) pairs, sorts them, then extracts the indices — keeping the sort structure visible without a nested loop. The trace shows pairs growing, then reordering in one step, then order filling with the extracted indices.

By hand

Build a list of [value, index] pairs. Sort the pairs (Python sorts lists lexicographically, so they sort by value then by index). Extract the second element of each sorted pair into order.

naive.py
Replay: real traced execution (multi-file project)
values = [3, 1, 4, 2, 5, 0]
pairs = []
for i in range(len(values)):
    pairs.append([values[i], i])
pairs.sort()
order = []
for p in pairs:
    order.append(p[1])
print('RESULT:', order)

  1. values ← [3, 1, 4, 2, 5, 0]

    1values = [3, 1, 4, 2, 5, 0]2pairs = []
    values this step[3, 1, 4, 2, 5, 0]values

  2. pairs ← []

    1values = [3, 1, 4, 2, 5, 0]2pairs = []3for i in range(len(values)):
    values this step[]pairs

  3. i ← 0, pairs ← [[3, 0]]

    pass 1 of 6
    2pairs = []3for i in range(len(values)):4    pairs.append([values[i], i])5pairs.sort()
    values this step0i[] → [[3, 0]]pairs
    All 6 passes — pass 1 is the card above
    passipairs
    10[] → [[3, 0]]
    20 → 1[[3, 0]] → [[3, 0], [1, 1]]
    31 → 2[[3, 0], [1, 1]] → [[3, 0], [1, 1], [4, 2]]
    42 → 3[[3, 0], [1, 1], [4, 2]] → [[3, 0], [1, 1], [4, 2], [2, 3]]
    53 → 4[[3, 0], [1, 1], [4, 2], [2, 3]] → [[3, 0], [1, 1], [4, 2], [2, 3], [5, 4]]
    64 → 5[[3, 0], [1, 1], [4, 2], [2, 3], [5, 4]] → [[3, 0], [1, 1], [4, 2], [2, 3], [5, 4], [0, 5]]

  4. for i in range(len(values)):

    2pairs = []3for i in range(len(values)):4    pairs.append([values[i], i])

  5. pairs ← [[0, 5], [1, 1], [2, 3], [3, 0], [4, 2], [5, 4]]

    4    pairs.append([values[i], i])5pairs.sort()6order = []
    values this step[[3, 0], [1, 1], [4, 2], [2, 3], [5, 4], [0, 5]] → [[0, 5], [1, 1], [2, 3], [3, 0], [4, 2], [5, 4]]pairs

  6. order ← []

    5pairs.sort()6order = []7for p in pairs:
    values this step[]order

  7. p ← [0, 5], order ← [5]

    pass 1 of 6
    6order = []7for p in pairs:8    order.append(p[1])9print('RESULT:', order)
    values this step[0, 5]p[] → [5]order
    All 6 passes — pass 1 is the card above
    passporder
    1[0, 5][] → [5]
    2[0, 5] → [1, 1][5] → [5, 1]
    3[1, 1] → [2, 3][5, 1] → [5, 1, 3]
    4[2, 3] → [3, 0][5, 1, 3] → [5, 1, 3, 0]
    5[3, 0] → [4, 2][5, 1, 3, 0] → [5, 1, 3, 0, 2]
    6[4, 2] → [5, 4][5, 1, 3, 0, 2] → [5, 1, 3, 0, 2, 4]

  8. for p in pairs:

    6order = []7for p in pairs:8    order.append(p[1])

  9. stdout ← RESULT: [5, 1, 3, 0, 2, 4]

    8    order.append(p[1])9print('RESULT:', order)
    values this stepRESULT: [5, 1, 3, 0, 2, 4]stdout

With NumPy

np.argsort(a) returns an array of integer indices such that a[indices] gives a in ascending order.

library.py 
import numpy as np

values = [3, 1, 4, 2, 5, 0]
a = np.array(values)
result = np.argsort(a)
print('a: shape:', a.shape, 'dtype:', a.dtype, 'values:', a.tolist())
print('result: shape:', result.shape, 'dtype:', result.dtype, 'values:', result.tolist())
print('RESULT:', result.tolist())

a: shape: (6,) dtype: int64 values: [3, 1, 4, 2, 5, 0]
result: shape: (6,) dtype: int64 values: [5, 1, 3, 0, 2, 4]
RESULT: [5, 1, 3, 0, 2, 4]

Implementation notes

  • Verify: a[[5, 1, 3, 0, 2, 4]] = [0, 1, 2, 3, 4, 5] — applying the argsort indices to a yields the sorted values (see fancy-index for index-array selection).
  • Argsort is useful to reorder a parallel array: if names and scores share the same positional index, argsort(scores) gives the index order to sort names by score without losing alignment.
  • For the rank-assignment pattern (each element gets its sorted rank) see rank-assign in the python-data-basics book.
  • Shape, dtype, and values are shown explicitly here because ndarray.__repr__ output varies with NumPy version and print options.