advanced-sorting.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Advanced Sorting\n",
    "### Merge Sort\n",
    "Merge sort is **`O(NlogN)`** in all cases. `LogN` to split the problem to gradually smaller problems and `N` to go through all elements in the split problems.<br>\n",
    "<img src=\"Graphics/merge.png\" width=\"35%\" align=\"left\">"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "def merge_sort(alist):\n",
    "    size = len(alist)\n",
    "    if size==1: return alist\n",
    "    left=[]\n",
    "    right=[]\n",
    "    split = len(alist)/2\n",
    "    left=alist[:split]\n",
    "    right=alist[split:]\n",
    "    print \"Splitting\", alist, \"to\", left, right\n",
    "    \n",
    "    left=merge_sort(left)     # Each call stack frame keeps its own left and right lists (also see Recursion notebook)\n",
    "    right=merge_sort(right)   \n",
    "\n",
    "    return merge(left, right) # It then merges them to build the result which is passed to the next call stack frame"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 207,
   "metadata": {},
   "outputs": [],
   "source": [
    "def merge(alist, blist):\n",
    "    merged=[]\n",
    "    i=j=0\n",
    "    print \"Merging:\" , alist, blist\n",
    "    while i<len(alist) and j<len(blist):\n",
    "        if alist[i]<blist[j]:\n",
    "            merged.append(alist[i])\n",
    "            i+=1\n",
    "        else:\n",
    "            merged.append(blist[j])\n",
    "            j+=1\n",
    "    \n",
    "    while i<len(alist):\n",
    "            merged.append(alist[i])\n",
    "            i+=1\n",
    "            \n",
    "    while j<len(blist):\n",
    "            merged.append(blist[j])\n",
    "            j+=1    \n",
    "            \n",
    "    print \"Merged:\", merged\n",
    "    return merged"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Notes: \n",
    "- Each call stack frame keeps its own left and right lists (also see Recursion notebook).\n",
    "- It then merges them to build the result which is passed to the next call stack frame. \n",
    "- Also, note how `merge()` happens after the recursive calls, which makes `merge_sort()` a head recursion."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 209,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Merging: [2, 4, 5, 7] [1, 3, 8, 9, 12]\n",
      "Merged: [1, 2, 3, 4, 5, 7, 8, 9, 12]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5, 7, 8, 9, 12]"
      ]
     },
     "execution_count": 209,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# demo the merging function\n",
    "alist=[2,4,5,7]\n",
    "blist=[1,3,8,9, 12]\n",
    "merge(alist, blist)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 211,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Splitting [12, 35, 87, 26, 9, 28, 7] to [12, 35, 87] [26, 9, 28, 7]\n",
      "Splitting [12, 35, 87] to [12] [35, 87]\n",
      "Splitting [35, 87] to [35] [87]\n",
      "Merging: [35] [87]\n",
      "Merged: [35, 87]\n",
      "Merging: [12] [35, 87]\n",
      "Merged: [12, 35, 87]\n",
      "Splitting [26, 9, 28, 7] to [26, 9] [28, 7]\n",
      "Splitting [26, 9] to [26] [9]\n",
      "Merging: [26] [9]\n",
      "Merged: [9, 26]\n",
      "Splitting [28, 7] to [28] [7]\n",
      "Merging: [28] [7]\n",
      "Merged: [7, 28]\n",
      "Merging: [9, 26] [7, 28]\n",
      "Merged: [7, 9, 26, 28]\n",
      "Merging: [12, 35, 87] [7, 9, 26, 28]\n",
      "Merged: [7, 9, 12, 26, 28, 35, 87]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[7, 9, 12, 26, 28, 35, 87]"
      ]
     },
     "execution_count": 211,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# demo merge sort\n",
    "alist=[12,35,87,26,9,28,7]\n",
    "merge_sort(alist)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Quick Sort\n",
    "Quick sort is **`O(N^2)`** (worst case, i.e. when the list is in reverse order) but it is **`O(NlogN)`** on average (an improvement over selection and insertion sort's `O(N^2)` average)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The sorting principle of quick sort is as follows: Pick a partitioning (aka pivot) element. For example use the last element of the list, `list[-1]`, as the pivot. Then run through the list and every time you find an element smaller than the pivot, place it in the sublist that holds the smaller items. Every time you find an element larger than the pivot, place it at the sublist with the larger items. Now these two sublists can be sorted independently. Sort them recursively. The main difference between merge sort and quick sort is that merge sort runs independenetly of the input data, it just halves the list. Quick sort partitions it based on a selected element.\n",
    "\n",
    "There are two ways to execute this algorithm. The first and more intuitive version, creates two lists and then concatenates them. This version is more readable, but it is not as space efficient as it uses additional lists. Note that this implementation is consistent to recursive return pattern 1 with a tail recursion."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def quick_sort(alist):\n",
    "    less = []\n",
    "    equal = []\n",
    "    greater = []\n",
    "    size = len(alist)\n",
    "    \n",
    "    if size <= 1: return alist\n",
    "    pivot = alist[-1]\n",
    "    for x in alist:\n",
    "        if x < pivot:\n",
    "            less.append(x)\n",
    "        elif x == pivot:\n",
    "            equal.append(x)\n",
    "        else:\n",
    "            greater.append(x)\n",
    "    return quick_sort(less)+equal+quick_sort(greater)  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 5, 6, 7, 8, 9, 12]\n"
     ]
    }
   ],
   "source": [
    "alist = [2, 4, 5, 7, 1, 3, 8, 9, 12, 6]\n",
    "alist=quick_sort(alist)\n",
    "print alist"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### In place Quick Sort\n",
    "A more efficient implementation creates the two sublists in place (space complexity `O(logN)`). It uses a left index which starts from `list[0]` and a right index which starts from the element left left of the pivot, `list[-2]`. The left index runs the list to the right and every time it finds an element larger than the pivot it stops. The right index runs the list to the left and every time it finds an element smaller than the pivot is stops. The two elements are swapped and the process goes on until the two indices meet. The point at which they meet is the position where the pivot must be placed. The pivot is swapped with this element and now the list consists of two sublists: The one on the left of the pivot contains the smaller than the pivot elements and the one on the right of the pivot contains the larger than the pivot elements. Assorting the sublists is done here by the helper function `partition()`.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "def quick_sort_in_place(alist, start=0, end=len(alist)-1):\n",
    "    if start<0 or start>=end or end<1: return\n",
    "    alist, pivot_index = partition(alist, start, end)\n",
    "    quick_sort_in_place(alist, start, pivot_index-1)\n",
    "    quick_sort_in_place(alist, pivot_index+1, end)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "def partition(alist, start, end):\n",
    "    pivot = end\n",
    "    left_index = start\n",
    "    right_index = end-1\n",
    "    while left_index<right_index:\n",
    "        if alist[left_index]<=alist[pivot]:\n",
    "            left_index+=1\n",
    "            continue\n",
    "        if alist[right_index]>=alist[pivot]:\n",
    "            right_index-=1\n",
    "            continue\n",
    "        alist[left_index], alist[right_index] = alist[right_index], alist[left_index]\n",
    "    if alist[left_index] > alist[end]: alist[left_index], alist[end] = alist[end], alist[left_index]\n",
    "    return alist, left_index"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Note:\n",
    "In-place Quick Sort does not return a value. The reason is that the part that changes the list is extracted in this implementation to the helper function `partition()`, which returns the changed list to the caller `quick_sort_in_place()` function. `quick_sort_in_place()` then just manipulates the indices. Also see the Recursion notebook."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "alist=[2, 4, 5, 7, 1, 3, 8, 9, 12, 6]\n",
    "quick_sort(alist)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 5, 6, 7, 8, 9, 12]\n"
     ]
    }
   ],
   "source": [
    "print alist"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.15"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}