day 67 - linked-list mergesort.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from types import SimpleNamespace\n",
    "from random import randint"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def _merge(p, q):\n",
    "    r, s = [Node()] * 2\n",
    "    \n",
    "    while p or q:\n",
    "        if not q or p and p.value < q.value:\n",
    "            r.next = p\n",
    "            r, p = r.next, p.next\n",
    "        else:\n",
    "            r.next = q\n",
    "            r, q = r.next, q.next\n",
    "\n",
    "    return s.next"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### recursive"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def mergesort_recursive(head):\n",
    "    # list is sorted\n",
    "    if not (head and head.next):\n",
    "        return head\n",
    "\n",
    "    # make equal split\n",
    "    p, q, r = head, head.next, None\n",
    "    while q:\n",
    "        p, q, r = p.next, q.next and q.next.next, p\n",
    "    r.next = None\n",
    "\n",
    "    # sort recursively\n",
    "    p = mergesort_recursive(p)\n",
    "    q = mergesort_recursive(head)\n",
    "\n",
    "    # merge\n",
    "    return _merge(p, q)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### iterative"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def mergesort_iterative(head):\n",
    "    splits = []\n",
    "\n",
    "    while head:\n",
    "        # sorted list of length 1\n",
    "        head, p = head.next, head\n",
    "        p.next = None\n",
    "        splits.append((1, p))\n",
    "\n",
    "        while len(splits) > 1:\n",
    "            (i, p), (j, q) = splits[-2:]\n",
    "            if i != j and head:\n",
    "                break\n",
    "            \n",
    "            # merge\n",
    "            splits[-2:] = [(i + j, _merge(p, q))]\n",
    "\n",
    "    return splits and splits[0][1] or None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## utilities"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "Node = SimpleNamespace"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def random_linked_list(size, r):\n",
    "    head = None\n",
    "    for i in range(size):\n",
    "        head = Node(value=randint(0, r), next=head)\n",
    "    return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def print_list(head):\n",
    "    def _iter(head):\n",
    "        while head:\n",
    "            yield head.value\n",
    "            head = head.next\n",
    "\n",
    "    print(list(_iter(head)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## run"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[10, 9, 2, 9, 0, 6, 4, 9, 1, 7, 10, 9, 9, 3, 0, 5, 7, 5, 1, 0]\n"
     ]
    }
   ],
   "source": [
    "head = random_linked_list(size=20, r=10)\n",
    "print_list(head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[]\n",
      "[4, 5, 10]\n",
      "[3, 4, 5, 5, 6, 9]\n",
      "[0, 1, 3, 3, 4, 4, 8, 8, 8]\n",
      "[1, 1, 4, 5, 6, 6, 6, 6, 6, 6, 9, 9]\n",
      "[0, 1, 2, 2, 3, 3, 4, 5, 5, 6, 7, 7, 9, 9, 10]\n",
      "[0, 1, 2, 3, 4, 4, 4, 5, 6, 6, 6, 7, 7, 7, 8, 8, 9, 10]\n",
      "[0, 1, 1, 1, 1, 1, 2, 3, 3, 4, 4, 5, 5, 7, 8, 8, 9, 9, 9, 9, 10]\n",
      "[0, 1, 1, 2, 2, 2, 2, 3, 3, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 9, 9, 10, 10]\n",
      "[0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 8, 9, 9, 10, 10, 10]\n"
     ]
    }
   ],
   "source": [
    "for i in range(10):\n",
    "    head = random_linked_list(size=3 * i, r=10)\n",
    "    head = mergesort_recursive(head)\n",
    "    print_list(head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[]\n",
      "[4, 4, 5]\n",
      "[1, 2, 4, 5, 6, 6]\n",
      "[3, 4, 5, 5, 6, 9, 10, 10, 10]\n",
      "[0, 2, 3, 3, 5, 6, 7, 8, 8, 8, 10, 10]\n",
      "[0, 0, 1, 1, 2, 3, 3, 4, 4, 5, 7, 8, 9, 9, 10]\n",
      "[1, 1, 2, 2, 2, 3, 4, 5, 5, 5, 7, 7, 7, 7, 9, 9, 10, 10]\n",
      "[0, 1, 1, 2, 2, 3, 3, 3, 3, 3, 3, 3, 5, 5, 5, 6, 6, 7, 9, 10, 10]\n",
      "[0, 0, 0, 1, 1, 2, 2, 2, 3, 4, 4, 5, 5, 5, 5, 5, 5, 6, 7, 7, 7, 7, 10, 10]\n",
      "[0, 0, 1, 1, 1, 1, 2, 2, 2, 4, 6, 6, 6, 6, 7, 7, 8, 8, 8, 8, 8, 9, 9, 9, 10, 10, 10]\n"
     ]
    }
   ],
   "source": [
    "for i in range(10):\n",
    "    head = random_linked_list(size=3 * i, r=10)\n",
    "    head = mergesort_iterative(head)\n",
    "    print_list(head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "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
}