Searching and Sorting.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# The Binary Search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=http://interactivepython.org/runestone/static/pythonds/_images/binsearch.png \\>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## loop"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def BinarySearch(orderedList,target):\n",
    "    # initialize\n",
    "    first=0\n",
    "    last=len(orderedList)-1\n",
    "    found=False\n",
    "    \n",
    "    while(first<=last and not found):\n",
    "        midpoint=(first+last)/2\n",
    "        if(target==orderedList[midpoint]):\n",
    "            found=True\n",
    "        elif(target>orderedList[midpoint]):\n",
    "            first=midpoint+1\n",
    "        else:\n",
    "            last=midpoint-1\n",
    "            \n",
    "    return (found,midpoint)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a=[17,22]\n",
    "a[2:1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(False, 0)"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "BinarySearch(a,55)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## recursion"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def BinarySearch(orderedList,target):\n",
    "    midpoint=(len(orderedList)-1)/2\n",
    "    if(orderedList==[]):\n",
    "        return False\n",
    "    if(target==orderedList[midpoint]):\n",
    "        return True\n",
    "    elif(target>orderedList[midpoint]):\n",
    "        return BinarySearch(orderedList[midpoint+1:],target)\n",
    "    else:\n",
    "        return BinarySearch(orderedList[:midpoint],target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[17]"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a=[17,20,26,31,44,54,55,65,77,93]\n",
    "a[0:1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "BinarySearch(a,21)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Hashing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A hash table is a collection of items which are stored in such a way as to make it easy to find them later. Each position of the hash table, often called a slot, can hold an item and is named by an integer value starting at 0. For example, we will have a slot named 0, a slot named 1, a slot named 2, and so on. Initially, the hash table contains no items so every slot is empty. We can implement a hash table by using a list with each element initialized to the special Python value None. \n",
    "\n",
    "<img src=http://interactivepython.org/runestone/static/pythonds/_images/hashtable.png \\>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The mapping between an item and the slot where that item belongs in the hash table is called the hash function. The hash function will take any item in the collection and return an integer in the range of slot names, between 0 and m-1. Assume that we have the set of integer items 54, 26, 93, 17, 77, and 31. Our first hash function, sometimes referred to as the “remainder method,” simply takes an item and divides it by the table size, returning the remainder as its hash value ($ h(item)=item\\%11 $). Table 4 gives all of the hash values for our example items. Note that this remainder method (modulo arithmetic) will typically be present in some form in all hash functions, since the result must be in the range of slot names."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "we use two lists to create a HashTable class that implements the Map abstract data type. One list, called slots, will hold the key items and a parallel list, called data, will hold the data values. When we look up a key, the corresponding position in the data list will hold the associated data value. We will treat the key list as a hash table using the ideas presented earlier. Note that the initial size for the hash table has been chosen to be 11. Although this is arbitrary, it is important that the size be a prime number so that the collision resolution algorithm can be as efficient as possible."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The collision resolution technique is linear probing with a \"plus 1\" rehash function. The put function (see Listing 3) assumes that there will eventually be an empty slot unless the key is already present in the self.slots. It computes the original hash value and if that slot is not empty, iterates the rehash function until an empty slot occurs. If a nonempty slot already contains the key, the old data value is replaced with the new data value. Dealing with the situation where there are no empty slots left is an exercise."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Likewise, the get function (see Listing 4) begins by computing the initial hash value. If the value is not in the initial slot, rehash is used to locate the next possible position. Notice that line 15 guarantees that the search will terminate by checking to make sure that we have not returned to the initial slot. If that happens, we have exhausted all possible slots and the item must not be present."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class HashTable:\n",
    "    def __init__(self):\n",
    "        self.size=11\n",
    "        self.slots=[None]*self.size\n",
    "        self.data=[None]*self.size\n",
    "        \n",
    "    def put(self,key,data):\n",
    "        hashvalue=self.hashfunction(key,len(self.slots))\n",
    "        \n",
    "        if self.slots[hashvalue]==None:\n",
    "            self.slots[hashvalue]=key\n",
    "            self.data[hashvalue]=data\n",
    "        else:\n",
    "            if self.slots[hashvalue]==key:\n",
    "                self.data[hashvalue]=data #replace\n",
    "            else:\n",
    "                nextslot=self.rehash(hashvalue,len(self.slots))\n",
    "                while(self.slots[nextslot]!=None and self.slots[nextslot]!=key):\n",
    "                    nextslot=self.rehash(nextslot,len(self.slots))\n",
    "                \n",
    "                if(self.slots[nextslot]==None):\n",
    "                    self.slots[nextslot]=key\n",
    "                    self.data[nextslot]=data\n",
    "                else:\n",
    "                    self.data[nextslot]=data #replace\n",
    "                    \n",
    "    def get(self,key):\n",
    "        hashvalue=self.hashfunction(key,len(self.slots))\n",
    "        \n",
    "        if self.slots[hashvalue]==key:\n",
    "            return self.data[hashvalue]\n",
    "        elif self.slots[hashvalue]==None:\n",
    "            return None\n",
    "        else:\n",
    "            nextslot=self.rehash(hashvalue,len(self.slots))\n",
    "            while(self.slots[nextslot]!=None and self.slots[nextslot]!=key and nextslot!=hashvalue):\n",
    "                nextslot=self.rehash(nextslot,len(self.slots))\n",
    "                \n",
    "            if self.slots[nextslot]==key:\n",
    "                return self.data[nextslot]\n",
    "            elif nextslot==hashvalue:\n",
    "                return None\n",
    "            else:\n",
    "                return None\n",
    "        \n",
    "    def hashfunction(self,key,size):\n",
    "        return key%size\n",
    "        \n",
    "    def rehash(self,oldhash,size):\n",
    "        return (oldhash+1)%size\n",
    "    \n",
    "    def __setitem__(self,key,data):\n",
    "        self.put(key,data)\n",
    "        \n",
    "    def __getitem__(self,key):\n",
    "        return self.get(key)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[77, 44, 55, 20, 26, 93, 17, None, None, 31, 54]"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "H=HashTable()\n",
    "H[54]=\"cat\"\n",
    "H[26]=\"dog\"\n",
    "H[93]=\"lion\"\n",
    "H[17]=\"tiger\"\n",
    "H[77]=\"bird\"\n",
    "H[31]=\"cow\"\n",
    "H[44]=\"goat\"\n",
    "H[55]=\"pig\"\n",
    "H[20]=\"chicken\"\n",
    "H.slots"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['bird',\n",
       " 'goat',\n",
       " 'pig',\n",
       " 'chicken',\n",
       " 'dog',\n",
       " 'lion',\n",
       " 'tiger',\n",
       " None,\n",
       " None,\n",
       " 'cow',\n",
       " 'cat']"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "H.data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'chicken'"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "H[20]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'tiger'"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "H[17]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "None\n"
     ]
    }
   ],
   "source": [
    "H[29]='me'\n",
    "H[30]='you'\n",
    "print H[99]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Analysis of Hashing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The best case hashing would provide a $O(1)$. However, due to collisions, the number of comparisons is typically not so simple. The most important piece of information we need to analyze the use of a hash table is the load factor, λ\n",
    ". Conceptually, if λ\n",
    " is small, then there is a lower chance of collisions, meaning that items are more likely to be in the slots where they belong. If λ\n",
    " is large, meaning that the table is filling up, then there are more and more collisions. This means that collision resolution is more difficult, requiring more comparisons to find an empty slot. With chaining, increased collisions means an increased number of items on each chain."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As before, we will have a result for both a successful and an unsuccessful search. For a successful search using open addressing with linear probing, the average number of comparisons is approximately $\\frac{1}{2}(1+\\frac{1}{1−λ})$\n",
    " and an unsuccessful search gives $\\frac{1}{2}(1+(\\frac{1}{1−λ})^2)$\n",
    " If we are using chaining, the average number of comparisons is $1+\\frac{λ}{2}$\n",
    " for the successful case, and simply λ\n",
    " comparisons if the search is unsuccessful."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Bubble Sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=http://interactivepython.org/runestone/static/pythonds/_images/bubblepass.png \\>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def BubbleSort(list):\n",
    "    size=len(list)\n",
    "    while(size>=2):\n",
    "        for i in range(size-1):\n",
    "            if(list[i]>list[i+1]):\n",
    "                temp=list[i]\n",
    "                list[i]=list[i+1]\n",
    "                list[i+1]=temp\n",
    "        size-=1\n",
    "    return list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[17, 17, 20, 26, 31, 44, 54, 55, 77]"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a=[26,54,17,17,77,31,44,55,20]\n",
    "BubbleSort(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1]"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "b=[1]\n",
    "BubbleSort(b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Selection Sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=http://interactivepython.org/runestone/static/pythonds/_images/selectionsortnew.png \\>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def SelectionSort(list):\n",
    "    size=len(list)\n",
    "    while(size>=2):\n",
    "        max=list[size-1]\n",
    "        for i in range(size-1):\n",
    "            if(list[i]>max):\n",
    "                max=list[i]\n",
    "                list[i]=list[size-1]\n",
    "                list[size-1]=max\n",
    "        size-=1\n",
    "    \n",
    "    return list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[17, 17, 20, 26, 31, 44, 54, 55, 77]"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a=[26,54,17,17,77,31,44,55,20]\n",
    "SelectionSort(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[20, 21]"
      ]
     },
     "execution_count": 63,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "b=[21,20]\n",
    "SelectionSort(b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "c=[]\n",
    "SelectionSort(c)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Insertion Sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=http://interactivepython.org/runestone/static/pythonds/_images/insertionsort.png \\>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def InsertionSort(list):\n",
    "    size=1\n",
    "    while(size < len(list)):\n",
    "        for i in range(size):\n",
    "            insert=list[size]\n",
    "            if(list[i]>insert):\n",
    "                temp=list[i:size]\n",
    "                list[i+1:size+1]=temp\n",
    "                list[i]=insert\n",
    "        size+=1\n",
    "    \n",
    "    return list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[17, 20, 26, 31, 44, 54, 55, 77, 93]"
      ]
     },
     "execution_count": 66,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a=[26,54,17,93,77,31,44,55,20]\n",
    "InsertionSort(a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Shell Sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=http://interactivepython.org/runestone/static/pythonds/_images/shellsortA.png \\>\n",
    "<img src=http://interactivepython.org/runestone/static/pythonds/_images/shellsortB.png \\>\n",
    "<img src=http://interactivepython.org/runestone/static/pythonds/_images/shellsortC.png \\>\n",
    "<img src=http://interactivepython.org/runestone/static/pythonds/_images/shellsortD.png \\>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def ShellSort(list):\n",
    "    \n",
    "    return list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Merge Sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=http://interactivepython.org/runestone/static/pythonds/_images/mergesortA.png \\>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=http://interactivepython.org/runestone/static/pythonds/_images/mergesortB.png \\>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=https://upload.wikimedia.org/wikipedia/commons/c/cc/Merge-sort-example-300px.gif \\>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given alist:\n",
    "* split into list with single element\n",
    "* merge sublists back into the whole"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def MergeSort(list):\n",
    "    if(len(list)>1):\n",
    "        # split until there is only single element in the sublist\n",
    "        midpoint=len(list)/2\n",
    "        left=MergeSort(list[:midpoint])\n",
    "        right=MergeSort(list[midpoint:])\n",
    "        \n",
    "        # merge left and right sublist\n",
    "        i=0\n",
    "        j=0\n",
    "        sorted_list=[]\n",
    "        while(i<len(left) or j<len(right)):\n",
    "            if(j>=len(right)):\n",
    "                sorted_list.append(left[i])\n",
    "                i+=1\n",
    "            elif(i>=len(left)):\n",
    "                sorted_list.append(right[j])\n",
    "                j+=1\n",
    "            elif(left[i]<right[j]):\n",
    "                sorted_list.append(left[i])\n",
    "                i+=1\n",
    "            else:\n",
    "                sorted_list.append(right[j])\n",
    "                j+=1\n",
    "            \n",
    "        return sorted_list\n",
    "    \n",
    "    #return the full list or list with single element\n",
    "    return list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[17, 20, 26, 31, 44, 54, 55, 93, 93]"
      ]
     },
     "execution_count": 89,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a=[26,54,17,93,93,31,44,55,20]\n",
    "MergeSort(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 91,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "b=[]\n",
    "MergeSort(b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Quick Sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=http://interactivepython.org/runestone/static/pythonds/_images/firstsplit.png \\>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=http://interactivepython.org/runestone/static/pythonds/_images/partitionA.png \\>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=http://interactivepython.org/runestone/static/pythonds/_images/partitionB.png \\>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def QuickSort(list):\n",
    "    if(len(list)>1):\n",
    "        #initialize\n",
    "        pivot=0\n",
    "        leftmarker=0\n",
    "        rightmarker=len(list)-1\n",
    "        #exchange process\n",
    "        while(leftmarker<=rightmarker):\n",
    "            if(list[leftmarker]<=list[pivot]):\n",
    "                leftmarker+=1\n",
    "            elif(list[rightmarker]>=list[pivot]):\n",
    "                rightmarker-=1\n",
    "            else:\n",
    "                temp=list[leftmarker]\n",
    "                list[leftmarker]=list[rightmarker]\n",
    "                list[rightmarker]=temp\n",
    "                \n",
    "        #split point found\n",
    "        temp=list[rightmarker]\n",
    "        list[rightmarker]=list[pivot]\n",
    "        list[pivot]=temp\n",
    "        pivot=rightmarker\n",
    "        #sublist quicksort\n",
    "        leftsublist=list[:pivot]\n",
    "        rightsublist=list[pivot+1:]\n",
    "        return QuickSort(leftsublist)+[list[pivot]]+QuickSort(rightsublist)\n",
    "        \n",
    "    return list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 107,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[17, 20, 26, 31, 44, 54, 55, 77, 93]"
      ]
     },
     "execution_count": 107,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a=[54,26,93,17,77,31,44,55,20]\n",
    "QuickSort(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[17, 54]"
      ]
     },
     "execution_count": 110,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "b=[54,17]\n",
    "QuickSort(b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# Crack coding interview: Searching and Sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**1**. You are given two sorted arrays, A and B, and A has a large enough buffer at the end to hold B. Write a method to merge B into A in sorted order.\n",
    "pg"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: This should be part of Merge sort algorithm.\n",
    "<img src=https://upload.wikimedia.org/wikipedia/commons/c/cc/Merge-sort-example-300px.gif \\>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def merge(L1,L2):\n",
    "    result=[]\n",
    "    k=0\n",
    "    j=0\n",
    "    while(k<len(L1) and j<len(L2)):\n",
    "        if(L1[k]<=L2[j]):\n",
    "            result.append(L1[k])\n",
    "            k+=1\n",
    "        else:\n",
    "            result.append(L2[j])\n",
    "            j+=1\n",
    "    if(k==len(L1)):\n",
    "        result+=L2[j:]\n",
    "    else:\n",
    "        result+=L1[k:]\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a=[]\n",
    "b=[]\n",
    "merge(a,b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**2**. Write a method to sort an array of strings so that all the anagrams are next to each other."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: We seek a comparator that sort the string in the list before sorting the list of the string."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def anagrams_comparator(a,b):\n",
    "    a=list(a)\n",
    "    b=list(b)\n",
    "    a.sort()\n",
    "    b.sort()\n",
    "    if a>b:\n",
    "        return 1\n",
    "    elif a==b:\n",
    "        return 0\n",
    "    else:\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "a=[\"dcba\",\"abc\",\"cba\",\"bcad\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['abc', 'bcad', 'cba', 'dcba']"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sorted(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['abc', 'cba', 'dcba', 'bcad']"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sorted(a,cmp=anagrams_comparator)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**3**. Given a sorted array of n integers that has been rotated an unknown number of times, give an O(log n) algorithm that finds an element in the array. You may assume that the array was originally sorted in increasing order.\n",
    "EXAMPLE: Input: find 5 in array (15 16 19 20 25 1 3 4 5 7 10 14) Output: 8 (the index of 5 in the array)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: If the whole list is sorted, then the binary sort is O(log n). The problem becomes how to locate the truncation point in an O(log n) algorithm. We could divide the list by half and compare the middle point element with the first element. If it is less than the first element, we discard the right half, else we discard the left half. We will carry out the division on the index list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def binarySearch(alist, item):\n",
    "    first = 0\n",
    "    last = len(alist)-1\n",
    "    found = False\n",
    "    \n",
    "    while first<=last and not found:\n",
    "        midpoint = (first + last)//2\n",
    "        if alist[midpoint] == item:\n",
    "            found = True\n",
    "        else:\n",
    "            if item < alist[midpoint]:\n",
    "                last = midpoint-1\n",
    "            else:\n",
    "                first = midpoint+1\n",
    "    \n",
    "    return found"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def rot_index(alist):\n",
    "    start=0\n",
    "    end=len(alist)-1\n",
    "    while start<end:\n",
    "        mid=(start+end)//2+1\n",
    "        if(alist[mid]>=alist[start]):\n",
    "            start=mid\n",
    "        else:\n",
    "            end=mid-1\n",
    "    return end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 63,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a=[6,7,8,9,10,11,12,13,14,15,16, 25, 1, 2,3,4,5]\n",
    "a_sorted=a[rot_index(a)+1:]+a[:rot_index(a)+1]\n",
    "a_sorted\n",
    "binarySearch(a_sorted,25)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**4**. If you have a 2 GB file with one string per line, which sorting algorithm would you use to sort the file and why?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: Obviously, we could not bring all the file into memory.\n",
    "\n",
    "How much memory do we have available? Let’s assume we have X MB of memory available.\n",
    "\n",
    "1. Divide the file into K chunks, where X * K = 2 GB. Bring each chunk into memory and sort the lines as usual using any O(n log n) algorithm. Save the lines back to the file.\n",
    "2. Now bring the next chunk into memory and sort. \n",
    "3. Once we’re done, merge them one by one. The above algorithm is also known as external sort. \n",
    "\n",
    "Step 3 is known as N-way merge\n",
    "The rationale behind using external sort is the size of data."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**5**. Given a sorted array of strings which is interspersed with empty strings, write a method to find the location of a given string.\n",
    "\n",
    "Example: find “ball” in [“at”, “”, “”, “”, “ball”, “”, “”, “car”, “”, “”, “dad”, “”, “”] will return 4 \n",
    "\n",
    "Example: find “ballcar” in [“at”, “”, “”, “”, “”, “ball”, “car”, “”, “”, “dad”, “”, “”] will return -1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: First I noticed that the array is sorted, which suggests a binary search. But the mid-point element could be an empty string. If this is the case, we could either move left or move right to find a non-empty string to compare with. If there is no non-empty string in the left/right half, we could simply discard that half."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def emptybinarySearch(alist,item):\n",
    "    first = 0\n",
    "    last = len(alist)-1\n",
    "    found = -1\n",
    "    \n",
    "    while first<=last and found==-1:\n",
    "        midpoint = (first + last)//2\n",
    "        #move left to find a non-empty element\n",
    "        while alist[midpoint]==\"\" and midpoint>=first:\n",
    "            midpoint-=1\n",
    "        #if non-empty string not found, discard left sublist\n",
    "        if(midpoint<first):\n",
    "            first=(first + last)//2+1\n",
    "        else:        \n",
    "            if alist[midpoint] == item:\n",
    "                found = midpoint\n",
    "            else:\n",
    "                if item < alist[midpoint]:\n",
    "                    last = midpoint-1\n",
    "                else:\n",
    "                    first = midpoint+1\n",
    "    \n",
    "    return found"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n",
      "-1\n",
      "-1\n",
      "-1\n"
     ]
    }
   ],
   "source": [
    "alist=[\"at\", \"\", \"\", \"\", \"ball\", \"\", \"\", \"car\", \"\", \"\", \"dad\", \"\", \"\"]\n",
    "print emptybinarySearch(alist,\"ball\")\n",
    "blist=[]\n",
    "print emptybinarySearch(blist,\"ball\")\n",
    "clist=[\"at\", \"\", \"\", \"\", \"\", \"ball\", \"car\", \"\", \"\", \"dad\", \"\", \"\"]\n",
    "print emptybinarySearch(clist,\"ballcar\")\n",
    "dlist=[\"\", \"\", \"\", \"\", \"\", \"\", \"\", \"\", \"\"]\n",
    "print emptybinarySearch(dlist,\"\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**6**. Given a matrix in which each row and each column is sorted, write a method to find an element in it."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: The key word is \"sorted\", which suggests binary search. If binary search is applied to each row, the algorithm will be O(n log n). But there should be a better way utilizing sorted nature in each column.\n",
    "\n",
    "Assumptions:\n",
    "\n",
    "1. Every row is sorted in ascending order from left to right; Every column is sorted in ascending order from up to down.\n",
    "2. The matrix is N$\\times$N.\n",
    "\n",
    "The algorithm is elimination. Each left move will rule out the elements below the current entry in that column; Each down move will rule out the elements to the left of the current entry in that row."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 137,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def matrixSort(matrix,item):\n",
    "    found=(-1,-1)\n",
    "    (m,n)=np.shape(matrix)\n",
    "    i=0\n",
    "    j=n-1\n",
    "    \n",
    "    while(i<m and j>=0):\n",
    "        if(matrix[i,j]==item):\n",
    "            found=(i,j)\n",
    "            return found\n",
    "        elif(matrix[i,j]<item):\n",
    "            matrix=np.delete(matrix,i,0)\n",
    "            i+=1\n",
    "        else:\n",
    "            matrix=np.delete(matrix,j,1)\n",
    "            j-=1\n",
    "            \n",
    "    return found"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 139,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(0, 1)"
      ]
     },
     "execution_count": 139,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import numpy as np\n",
    "a=np.array([[1,2]])\n",
    "matrixSort(a,2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**7**. <font color='red'>A circus is designing a tower routine consisting of people standing atop one another’s shoulders. For practical and aesthetic reasons, each person must be both shorter and lighter than the person below him or her. Given the heights and weights of each person in the circus, write a method to compute the largest possible number of people in such a tower.\n",
    "\n",
    "EXAMPLE: Input (ht, wt): (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110)\n",
    "Output: The longest tower is length 6 and includes from top to bottom: (56, 90) (60,95) (65,100) (68,110) (70,150) (75,190)</font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: Since the input are tuples, if we sort ht first, then the wt might be unsorted."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "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.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}