🎓 A1Learner
🔍

DSA Why Sorting Helps

Sorting is putting values in order from smallest to largest. Sorted data makes searching and grouping much cheaper.

Order at a glance

A sorted list places values in order from smallest to largest. Equal values end up side by side in that order.

scores = [42, 17, 88, 17, 59]
print(sorted(scores))

Duplicates sit together

Sorted data places equal values next to each other. One neighbour scan then finds every duplicate value.

scores = [17, 17, 42, 59, 88]
for i in range(1, len(scores)):
    if scores[i] == scores[i - 1]:
        print("duplicate:", scores[i])

Halving needs order

Binary search is the halving search from the searching entry. It only works when the data is already sorted.

def find(scores, target):
    steps = 0
    lo = 0
    hi = len(scores) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        steps += 1
        if scores[mid] == target:
            return steps
        if scores[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return steps

data = [17, 17, 42, 59, 88]
print(find(data, 88))

Example

def linear_count(data, target):
    steps = 0
    for value in data:
        steps += 1
        if value == target:
            return True, steps
    return False, steps

def binary_count(data, target):
    steps = 0
    lo = 0
    hi = len(data) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        steps += 1
        if data[mid] == target:
            return True, steps
        if data[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return False, steps

raw = [73, 12, 91, 45, 67, 12, 84, 29, 56, 91, 38, 60]
targets = [91, 29, 50, 73]
total_raw = 0
for target in targets:
    found, steps = linear_count(raw, target)
    total_raw += steps
    print("raw", target, found, steps)
ordered = sorted(raw)
print("sorted:", ordered)
total_sorted = 0
for target in targets:
    found, steps = binary_count(ordered, target)
    total_sorted += steps
    print("sorted", target, found, steps)
print("total raw steps:", total_raw)
print("total sorted steps:", total_sorted)

Key points

  • Sorting arranges values so each value is no smaller than the one before it.
  • Preprocessing is work done once before the main task begins.
  • Sorting is preprocessing that later searches and scans can reuse.
  • Binary search needs sorted data before it can halve the range.
  • A sorted list places equal values together, so duplicates are neighbours.

In this example, four targets are searched for in one list of twelve scores. The raw searches walk the unsorted list and spend 24 steps in total. The list is then sorted once with the built-in sorted function. The sorted searches halve the range each step and spend 11 steps in total. Both routes give the same four answers, so the order is what saves the steps.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

A list of scores is sorted once, and then many searches run on it. Which job becomes cheaper because of that order?