13_Sorting.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Chapter 13: Sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 13.1 Compute the intersection of two sorted arrays"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def intersection(A, B):\n",
    "    \"\"\"\n",
    "    Finds the intersection of A and B\n",
    "    \"\"\"\n",
    "    i, j = 0, 0\n",
    "    result = []\n",
    "    while i < len(A) and j < len(B):\n",
    "        if A[i] == B[j]:\n",
    "            if i == 0 or A[i] != A[i - 1]:\n",
    "                result.append(A[i])\n",
    "            i += 1\n",
    "            j += 1\n",
    "        elif A[i] < B[j]:\n",
    "            i += 1\n",
    "        else:\n",
    "            j += 1\n",
    "    return result\n",
    "\n",
    "# Tests\n",
    "assert intersection([2, 3, 3, 5, 5, 6, 7, 7, 8, 12], [5, 5, 6, 8, 8, 9, 10, 10]) == [5, 6, 8]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 13.2 Merge two sorted arrays"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def merge_two_sorted(A, m, B, n):\n",
    "    \"\"\"\n",
    "    Merges B into A given that A has enough space for B at its end\n",
    "    \"\"\"\n",
    "    a, b, write_id = m - 1, n - 1, m + n - 1\n",
    "    while a >= 0 and b >= 0:\n",
    "        if A[a] > B[b]:\n",
    "            A[write_id] = A[a]\n",
    "            a -= 1\n",
    "        else:\n",
    "            A[write_id] = B[b]\n",
    "            b -= 1\n",
    "        write_id -= 1\n",
    "    \n",
    "    while b >= 0:\n",
    "        A[write_id] = B[b]\n",
    "        write_id, b = write_id - 1, b - 1\n",
    "    return A"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 13.5 Render a calendar"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import namedtuple\n",
    "\n",
    "# Event\n",
    "Event = namedtuple(\"Event\", (\"start\", \"end\"))\n",
    "\n",
    "# Endpoint\n",
    "Endpoint = namedtuple(\"Endpoint\", (\"time\", \"is_start\"))\n",
    "\n",
    "def find_max_simultaneous_events(events):\n",
    "    endpoints = ([Endpoint(e.start, True) for e in events] +\n",
    "                 [Endpoint(e.end, False) for e in events])\n",
    "    # Sort by time and break ties on the start endpoint coming first\n",
    "    endpoints.sort(key = lambda e: (e.time, not e.is_start))\n",
    "    \n",
    "    max_simul, curr_simul = 0, 0\n",
    "\n",
    "    for e in endpoints:\n",
    "        if e.is_start:\n",
    "            curr_simul += 1\n",
    "            max_simul = max(max_simul, curr_simul)\n",
    "        else:\n",
    "            curr_simul -= 1\n",
    "    return max_simul"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 13.7 Compute the union of intervals"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Represents an interval\n",
    "Interval = namedtuple(\"Interval\", (\"left\", \"right\"))\n",
    "\n",
    "# Represents an endpoint of an interval\n",
    "Endpoint = namedtuple(\"Endpoint\", (\"val\", \"is_closed\"))\n",
    "        \n",
    "def union_of_intervals(intervals):\n",
    "    if not intervals:\n",
    "        return []\n",
    "    \n",
    "    intervals.sort(key = lambda i: (i.left.val, not i.left.is_closed))\n",
    "    result = intervals[0]\n",
    "    \n",
    "    for i in intervals:\n",
    "        if ((i.left.val < result[-1].right.val) or \n",
    "            (i.left.val == result[-1].right.val and \n",
    "                i.left.is_closed or result[-1].right.is_closed)):\n",
    "            if (i.right.val > result[-1].right.val or\n",
    "                   (i.right.val == result[-1].right.val and i.right.is_closed)):\n",
    "                result[-1].right = i.right\n",
    "        else:\n",
    "            result.append(i)\n",
    "    return result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 13.10 Implement a fast sorting algorithm for lists"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "class ListNode():\n",
    "    \"\"\"\n",
    "    Represents a singly linked list node\n",
    "    \"\"\"\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Insertion sort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def insertion_sort(L):\n",
    "    \"\"\"\n",
    "    Performed insertion sort in ascending order on linked list L\n",
    "    \"\"\"\n",
    "    dummy_head = ListNode(next=L)\n",
    "    while L and L.next:\n",
    "        if L.next.val < L.val:\n",
    "            target, pre = L.next, dummy_head\n",
    "            while pre.next.val < target.val:\n",
    "                pre = pre.next\n",
    "            temp = pre.next\n",
    "            pre.next = target\n",
    "            L.next = target.next\n",
    "            target.next = temp\n",
    "        else:\n",
    "            L = L.next\n",
    "    return dummy_head.next"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Merge Sort (Stable):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "def merge_sorted_lists(L1, L2):\n",
    "    \"\"\"\n",
    "    Merges the given two lists in ascending order\n",
    "    \"\"\"\n",
    "    dummy_head = ListNode(next=L1)\n",
    "    curr = dummy_head\n",
    "    \n",
    "    while L1 and L2:\n",
    "        if L1.val < L2.val:\n",
    "            curr.next, L1 = L1, L1.next\n",
    "        else:\n",
    "            curr.next, L2 = L2, L2.next\n",
    "        curr = curr.next\n",
    "    curr.next = L1 or L2\n",
    "    return dummy_head.next\n",
    "\n",
    "\n",
    "def merge_sort(L):\n",
    "    \"\"\"\n",
    "    Performs merge sort in ascending order on linked list L\n",
    "    \"\"\"\n",
    "    # Base case\n",
    "    if not L or not L.next:\n",
    "        return L\n",
    "    \n",
    "    # Find the midpoint of L\n",
    "    pre_slow, slow, fast = None, L, L\n",
    "    while fast and fast.next:\n",
    "        pre_slow = slow\n",
    "        slow, fast = slow.next, fast.next.next\n",
    "    \n",
    "    # Split L\n",
    "    pre_slow.next = None\n",
    "    \n",
    "    # Recursively merge\n",
    "    return merge_sorted_lists(merge_sort(L), merge_sort(slow))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.6.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}