{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Grokking Algorithms \u2014 Sorting & Search\n",
    "\n",
    "Hands-on companion to the **Searching** and **Sorting** sections of\n",
    "[grokking_algorithms.html](grokking_algorithms.html).\n",
    "\n",
    "Every code cell is preceded by a **\ud83d\udc0d Python in this cell** note and\n",
    "has per-line comments inside.\n",
    "\n",
    "**Covered in this notebook:**\n",
    "1. Binary search\n",
    "2. Selection sort\n",
    "3. Merge sort\n",
    "4. Quicksort\n",
    "5. Timing all three sorts head to head"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. Binary search\n",
    "\n",
    "Look at the middle of a sorted list. Target smaller? Throw the right\n",
    "half away. Target bigger? Throw the left half away. Otherwise found.\n",
    "Each step halves the search space \u2014 a billion items take ~30 guesses."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> \ud83d\udc0d **Python in this cell:** `while condition:` repeats as long as condition is true. `//` is **integer division** (floor): `7 // 2 == 3`, never `3.5`. `return None` explicitly returns the no-value sentinel. Comma assignment `lo, hi = 0, len(arr) - 1` sets two variables at once."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def binary_search(arr, target):\n",
    "    lo, hi = 0, len(arr) - 1              # search range [lo, hi] inclusive\n",
    "    while lo <= hi:                       # keep going as long as range is non-empty\n",
    "        mid = (lo + hi) // 2              # integer midpoint\n",
    "        if arr[mid] == target:\n",
    "            return mid                    # found! return its index\n",
    "        if arr[mid] < target:\n",
    "            lo = mid + 1                  # target is in the upper half\n",
    "        else:\n",
    "            hi = mid - 1                  # target is in the lower half\n",
    "    return None                           # exhausted the range \u2014 not in list\n",
    "\n",
    "nums = [1, 3, 5, 7, 9, 11, 13, 15]\n",
    "print(\"Find 7:\",  binary_search(nums, 7))\n",
    "print(\"Find 15:\", binary_search(nums, 15))\n",
    "print(\"Find 10:\", binary_search(nums, 10))   # not in list \u2192 None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Watch it converge\n",
    "\n",
    "Add a print so you can see how the search range shrinks each step."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> \ud83d\udc0d **Python in this cell:** Same algorithm as above, plus a `step` counter and prints inside the loop. `f\"...{step:>3}...\"` right-aligns step in 3 spaces. `\\n` inside a string is a newline character."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def binary_search_verbose(arr, target):\n",
    "    lo, hi = 0, len(arr) - 1\n",
    "    step = 0                              # how many guesses we've made\n",
    "    while lo <= hi:\n",
    "        step += 1                         # one more guess\n",
    "        mid = (lo + hi) // 2\n",
    "        print(f\"step {step}: lo={lo:>3} hi={hi:>3} mid={mid:>3} arr[mid]={arr[mid]}\")\n",
    "        if arr[mid] == target:\n",
    "            return mid\n",
    "        if arr[mid] < target:\n",
    "            lo = mid + 1\n",
    "        else:\n",
    "            hi = mid - 1\n",
    "    return None\n",
    "\n",
    "big_list = list(range(0, 1000, 7))        # 0, 7, 14, 21, ..., 994 \u2014 sorted\n",
    "idx = binary_search_verbose(big_list, 763)\n",
    "print(f\"\\nFound at index {idx}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Linear vs binary \u2014 how big is the gap really?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> \ud83d\udc0d **Python in this cell:** `break` exits a loop early. `1e6` is scientific notation for `1,000,000`. We compute elapsed time in microseconds by multiplying by `1e6`. `max(x, 0.1)` avoids dividing by zero when measurement was too fast to register."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "\n",
    "n = 1_000_000\n",
    "sorted_data = list(range(n))              # one million sorted integers\n",
    "target = n - 1                            # worst case: last element\n",
    "\n",
    "t0 = time.perf_counter()\n",
    "for i, x in enumerate(sorted_data):       # linear scan\n",
    "    if x == target:\n",
    "        break                             # stop as soon as found\n",
    "linear = (time.perf_counter() - t0) * 1e6 # microseconds\n",
    "\n",
    "t0 = time.perf_counter()\n",
    "binary_search(sorted_data, target)\n",
    "binary = (time.perf_counter() - t0) * 1e6\n",
    "\n",
    "print(f\"linear search:  {linear:>8.1f} \u00b5s\")\n",
    "print(f\"binary search:  {binary:>8.1f} \u00b5s\")\n",
    "print(f\"binary is ~{linear / max(binary, 0.1):.0f}\u00d7 faster\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Selection sort\n",
    "\n",
    "Walk the list, find the smallest, swap it to the front. Easy to\n",
    "understand, always O(n\u00b2)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> \ud83d\udc0d **Python in this cell:** `range(start, stop)` generates integers `start, start+1, ..., stop-1` (stop NOT included). `arr[i], arr[j] = arr[j], arr[i]` is Python's one-line tuple swap. `len(arr)` returns the length of any sequence."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def selection_sort(arr):\n",
    "    n = len(arr)\n",
    "    for i in range(n - 1):                # i marks the next slot to fill\n",
    "        min_idx = i                       # assume current is smallest\n",
    "        for j in range(i + 1, n):         # scan the unsorted tail\n",
    "            if arr[j] < arr[min_idx]:\n",
    "                min_idx = j               # found a smaller one\n",
    "        arr[i], arr[min_idx] = arr[min_idx], arr[i]   # swap into place\n",
    "    return arr\n",
    "\n",
    "print(selection_sort([5, 2, 8, 1, 4]))\n",
    "print(selection_sort([64, 25, 12, 22, 11]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**See it slow down.** Time random lists of growing sizes. Expect the\n",
    "time to roughly *quadruple* every time size doubles."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> \ud83d\udc0d **Python in this cell:** `random.random()` returns a float in [0.0, 1.0). Multiplying elapsed seconds by 1000 converts to milliseconds (ms)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random, time\n",
    "\n",
    "random.seed(0)                            # reproducible runs\n",
    "print(f\"{'size':>8}  {'time':>10}\")\n",
    "for n in [500, 1000, 2000, 4000, 8000]:   # double each time\n",
    "    data = [random.random() for _ in range(n)]    # random list of floats\n",
    "    t0 = time.perf_counter()\n",
    "    selection_sort(data)\n",
    "    elapsed = time.perf_counter() - t0\n",
    "    print(f\"{n:>8}  {elapsed*1000:>8.1f} ms\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. Merge sort\n",
    "\n",
    "Cut the list in half, recursively sort each half, then merge. Always\n",
    "O(n log n) and **stable** (equal elements keep their original order)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> \ud83d\udc0d **Python in this cell:** Slicing: `arr[:mid]` is everything before index `mid`; `arr[mid:]` is everything from `mid` onwards. Both create new lists. `i = j = 0` assigns 0 to both variables. `result.extend(seq)` appends every element of seq to result."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def merge_sort(arr):\n",
    "    if len(arr) <= 1:\n",
    "        return arr                        # base case: already sorted\n",
    "    mid = len(arr) // 2\n",
    "    left  = merge_sort(arr[:mid])         # recursively sort left half\n",
    "    right = merge_sort(arr[mid:])         # recursively sort right half\n",
    "    return merge(left, right)             # merge two sorted halves\n",
    "\n",
    "def merge(left, right):\n",
    "    result = []\n",
    "    i = j = 0                             # i indexes left, j indexes right\n",
    "    while i < len(left) and j < len(right):\n",
    "        if left[i] <= right[j]:           # <= keeps it stable\n",
    "            result.append(left[i]); i += 1\n",
    "        else:\n",
    "            result.append(right[j]); j += 1\n",
    "    result.extend(left[i:])               # pour in whatever's left over\n",
    "    result.extend(right[j:])\n",
    "    return result\n",
    "\n",
    "print(merge_sort([38, 27, 43, 3, 9, 82, 10]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Proving stability\n",
    "\n",
    "Sort `(grade, name)` tuples by grade only. A stable sort keeps\n",
    "same-grade students in their original alphabetical order."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> \ud83d\udc0d **Python in this cell:** Tuples like `(\"B\", \"alice\")` compare element-by-element by default. When we compare tuples in `merge`, Python compares the first elements first \u2014 that's why sorting by tuple sorts primarily by grade."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "students = [(\"B\", \"alice\"), (\"A\", \"bob\"), (\"B\", \"charlie\"),\n",
    "            (\"A\", \"dave\"), (\"B\", \"eve\")]\n",
    "\n",
    "# Sort by tuple \u2014 primarily by grade (first element).\n",
    "sorted_students = merge_sort(students)\n",
    "for s in sorted_students:\n",
    "    print(s)\n",
    "\n",
    "# A-students should appear in original (alice ahead of dave)... wait, here A is bob then dave.\n",
    "# B-students should stay alice, charlie, eve \u2014 original order \u2014 because the sort is STABLE."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4. Quicksort\n",
    "\n",
    "Pick a pivot. Partition into \"smaller than pivot\" and \"larger than\n",
    "pivot\". Recurse on each side. Average O(n log n)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> \ud83d\udc0d **Python in this cell:** List comprehension with a condition: `[x for x in seq if test(x)]` builds a new list of all `x` in `seq` for which `test(x)` is True. `arr[1:]` is everything except the first element. List concatenation with `+` joins two lists."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def quicksort(arr):\n",
    "    if len(arr) < 2:\n",
    "        return arr                                    # 0 or 1 element is already sorted\n",
    "    pivot = arr[0]                                    # pick first element as pivot\n",
    "    less    = [x for x in arr[1:] if x <= pivot]      # elements \u2264 pivot\n",
    "    greater = [x for x in arr[1:] if x >  pivot]      # elements > pivot\n",
    "    return quicksort(less) + [pivot] + quicksort(greater)   # sort both sides, sandwich pivot\n",
    "\n",
    "print(quicksort([3, 6, 1, 8, 2, 4]))\n",
    "print(quicksort([64, 25, 12, 22, 11, 90, 4, 18, 33, 7]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### See the partitioning\n",
    "\n",
    "Add print statements to watch quicksort carve up the list at each\n",
    "level of recursion."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> \ud83d\udc0d **Python in this cell:** `depth=0` is a default parameter value. `\"  \" * depth` repeats two spaces `depth` times \u2014 useful to visually indent recursion levels."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def quicksort_verbose(arr, depth=0):\n",
    "    indent = \"  \" * depth                             # one indent per recursion level\n",
    "    if len(arr) < 2:\n",
    "        if arr:\n",
    "            print(f\"{indent}base: {arr}\")\n",
    "        return arr\n",
    "    pivot = arr[0]\n",
    "    less    = [x for x in arr[1:] if x <= pivot]\n",
    "    greater = [x for x in arr[1:] if x >  pivot]\n",
    "    print(f\"{indent}pivot={pivot}  less={less}  greater={greater}\")\n",
    "    return quicksort_verbose(less, depth + 1) + [pivot] + quicksort_verbose(greater, depth + 1)\n",
    "\n",
    "print(quicksort_verbose([3, 6, 1, 8, 2, 4]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5. Head-to-head \u2014 all three sorts on the same data\n",
    "\n",
    "Time each sort plus Python's built-in `sorted()` (Timsort) on the\n",
    "same random list. Watch selection sort fall behind as size grows."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> \ud83d\udc0d **Python in this cell:** We pass functions around like regular values: `time_sort(selection_sort, data)` calls our helper with the function itself as an argument. Inside the helper, `fn(...)` calls whichever function was passed in. `list(data)` makes a copy so each sort gets a fresh list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random, time\n",
    "\n",
    "def time_sort(fn, data):\n",
    "    t0 = time.perf_counter()\n",
    "    fn(list(data))                        # call the passed-in function on a fresh copy\n",
    "    return (time.perf_counter() - t0) * 1000   # milliseconds\n",
    "\n",
    "random.seed(0)\n",
    "print(f\"{'size':>6}  {'selection':>10}  {'merge':>8}  {'quick':>8}  {'sorted()':>10}\")\n",
    "for n in [500, 1000, 2000, 4000]:\n",
    "    data = [random.random() for _ in range(n)]\n",
    "    sel = time_sort(selection_sort, data)\n",
    "    mrg = time_sort(merge_sort,     data)\n",
    "    qck = time_sort(quicksort,      data)\n",
    "    blt = time_sort(sorted,         data)            # Python's built-in Timsort\n",
    "    print(f\"{n:>6}  {sel:>8.1f} ms  {mrg:>6.1f} ms  {qck:>6.1f} ms  {blt:>8.2f} ms\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**The takeaway:** Python's `sorted()` wins handily \u2014 it's implemented\n",
    "in C and exploits patterns in real data. Never write your own sort in\n",
    "production."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python",
   "version": "3.x"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}