Searching and sorting

Part of the free LogicWiz Python course, Pack B: College Semester Pack. The examples and practice run in the app.

The exam cell has 1,200 roll numbers. Finding one by checking each takes up to 1,200 looks; binary search needs 11. But it only works on sorted data, so first you sort, and the lab exam asks you to show every pass.

You'll learn to

• Write linear search and binary search, and say when each works
• Trace bubble, selection and insertion sort pass by pass
• Compare the three sorts: comparisons, swaps, best case, stability

Learn

Two ways to search

Linear search checks items one by one. Works on any list. Worst case: n looks.

Binary search needs a sorted list. Look at the middle: if the target is smaller, throw away the right half, else the left half. Each look halves what's left.

In Big-O: linear is O(n), binary is O(log n).

Linear search

def linear_search(items, target):
    for i in range(len(items)):
        if items[i] == target:
            return i
    return -1


marks = [67, 82, 45, 91, 58]
print(linear_search(marks, 91))
print(linear_search(marks, 100))

Binary search, the loop version

def binary_search(items, target):
    lo, hi = 0, len(items) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        print(f"lo={lo} hi={hi} mid={mid} -> {items[mid]}")
        if items[mid] == target:
            return mid
        elif items[mid] < target:
            lo = mid + 1          # target is to the right
        else:
            hi = mid - 1          # target is to the left
    return -1


rolls = [101, 104, 108, 112, 115, 119, 123, 130]
print("index", binary_search(rolls, 119))

while lo <= hi (with the =) so a one-item range is still checked. mid + 1 and mid - 1, never just mid, or the loop can get stuck.

Bubble sort: big ones bubble to the end

def bubble_sort(a):
    a = a[:]                          # sort a copy
    n = len(a)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):    # the last i items are already in place
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True
        print("pass", i + 1, a)
        if not swapped:               # no swaps: already sorted, stop early
            break
    return a


bubble_sort([5, 1, 4, 2, 8])

Compare neighbours and swap if out of order. After pass 1 the biggest is at the end. The swapped flag makes it stop early on sorted data: best case O(n).

Selection sort: pick the smallest

def selection_sort(a):
    a = a[:]
    for i in range(len(a) - 1):
        min_i = i
        for j in range(i + 1, len(a)):
            if a[j] < a[min_i]:
                min_i = j
        a[i], a[min_i] = a[min_i], a[i]     # one swap per pass
        print("pass", i + 1, a)
    return a


selection_sort([64, 25, 12, 22, 11])

Find the smallest of the unsorted part and swap it to the front. Always O(n²) comparisons, but at most n-1 swaps.

Insertion sort: like sorting cards in your hand

def insertion_sort(a):
    a = a[:]
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:     # shift bigger items right
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key                   # drop the card in its place
        print("pass", i, a)
    return a


insertion_sort([12, 11, 13, 5, 6])

Take the next item and slide it left into its place among the already-sorted items. Very fast on nearly sorted data.

The three sorts side by side

Lab mapping. Linear search, binary search, and bubble/selection/insertion sort are standard programs in the VTU, Anna (GE3171), JNTU, AKTU, DU and Mumbai first-year Python labs. Exams often give a list and ask for the list after each pass, so practise writing the passes by hand.

Viva: "Why does binary search need sorted data?" "Best case of bubble sort?" (O(n), with the swapped flag) "Which sort makes fewest swaps?" (selection) "What sort does Python's sorted() use?" (Timsort, O(n log n), stable).

In one line

Linear search works anywhere (O(n)); binary search needs sorted data (O(log n)); bubble swaps neighbours, selection picks the minimum, insertion slides each item into place (all O(n²)).