{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "dadc0d8a-33ec-4335-b1f7-08644bbe79ad",
   "metadata": {},
   "source": [
    "### <center>San Jose State University<br>Department of Applied Data Science<br><br>**DATA 200<br>Computational Programming for Data Analytics**<br><br>Spring 2024<br>Instructor: Ron Mak</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1f5b3f8d-fbc8-4569-aefb-309584c154b1",
   "metadata": {},
   "source": [
    "# Insertion sort with a trace\n",
    "#### Perform insert sorts with a printed trace of each pass. For a list of *n* values, perform *n*-1 passes."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ae8b9553-65ec-4d32-b231-432e12f250ba",
   "metadata": {},
   "source": [
    "## Printing functions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "90748922-e4e1-4e8e-97f3-759af311ec92",
   "metadata": {},
   "outputs": [],
   "source": [
    "def print_underline(count):\n",
    "    print('         ', end='')\n",
    "    for i in range(count): print('-----', end='')\n",
    "    print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5361759e-5ac7-4e32-8c44-37de1e6b67ed",
   "metadata": {},
   "outputs": [],
   "source": [
    "def print_array(a, p, index, count, new_pass=False):\n",
    "    if new_pass: \n",
    "        print()\n",
    "        print(f'Pass {p:2}: ', end='')\n",
    "    else:        \n",
    "        print('         ', end='')\n",
    "\n",
    "    for k in range(len(a)):\n",
    "        if k != index: print(f'  {a[k]:2} ', end='')\n",
    "        else:          print(f' ({a[k]:2})', end='')\n",
    "\n",
    "    print()\n",
    "    print_underline(count)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0214db40-fbd2-43af-b64a-c4aff6713125",
   "metadata": {},
   "source": [
    "## Insertion sort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6e8435a2-d9b6-4735-b24d-ff2f3762a915",
   "metadata": {},
   "outputs": [],
   "source": [
    "def verify_sorted(a):\n",
    "    \"\"\"\n",
    "    Verify that the data list a\n",
    "    has been successfully sorted.\n",
    "    \"\"\"\n",
    "    for k in range(1, len(a)):\n",
    "        value = a[k]\n",
    "        prev  = a[k - 1]\n",
    "        \n",
    "        if value < prev:\n",
    "            raise Exception('Sort error: '\n",
    "                            f'{value} < {prev} at {k}')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0944a35f-a375-45d6-abb4-12b6fcc75fe0",
   "metadata": {},
   "source": [
    "#### If there are *n* elements in the array `a`, the sort consists of *n*-1 passes. Variable `p` is the pass number, from 1 through *n*-1:\n",
    "- #### At the start of each pass, initialize index variable `j` to the value of `p`.\n",
    "- #### Until a swap is not required or `j` has reached the left end of the list:\n",
    "  - #### Examine adjacent value pairs `a[j-1]` and `a[j]`, and if the pair is out of order, swap their values.\n",
    "  - #### Move `j` to the left (i.e., decrement `j` by 1).\n",
    "#### When all *n*-1 passes are done, the list will be sorted in ascending order.\n",
    "#### This algorithm is called an ***insertion sort*** because during each pass, the sorted part of the list grows by one element. The value to the right of the sorted part \"filters into\" the sorted part to reach its correct position."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "463812da-8492-42c5-a309-e922de198ade",
   "metadata": {},
   "outputs": [],
   "source": [
    "def insertion_sort(a):\n",
    "    \"\"\"\n",
    "    Perform an insertion sort with tracing. At the start\n",
    "    of each cycle, print the cycle index above the right\n",
    "    end of the interval being sorted. At each step of the\n",
    "    cycle, print brackets around the pair of values being\n",
    "    checked.\n",
    "    \"\"\"\n",
    "    for p in range(1, len(a)):\n",
    "        j = p\n",
    "\n",
    "        print_array(a, p, p, p, new_pass=True);\n",
    "        \n",
    "        while (j > 0) and (a[j] < a[j-1]):\n",
    "            a[j-1], a[j] = a[j], a[j-1]  # swap\n",
    "            j -= 1\n",
    "\n",
    "        print_array(a, p, j, p + 1)\n",
    "\n",
    "    verify_sorted(a)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2e542427-8e1c-48b7-b97f-8912016fd0c1",
   "metadata": {},
   "source": [
    "## Test"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c54a6fda-ce63-49bf-9aba-0837fb223984",
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "ARRAY_SIZE = 12\n",
    "\n",
    "a = [random.randint(10, 99) for _ in range(ARRAY_SIZE)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "aacaca79-b153-44f3-ad08-0edc590398b3",
   "metadata": {},
   "outputs": [],
   "source": [
    "insertion_sort(a)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "25a45ab7-6d7e-4520-968f-6af82ede0335",
   "metadata": {},
   "source": [
    "#### (c) 2024 by Ronald Mak"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "88d4fd4b-d217-47bc-aeca-ed7444f0a08f",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}