C1W3_5_QUICKSORT.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# V. Quick Sort\n",
    "In this notebook we will be looking at quick sort in details and will be doing the worst and average running time analysis.\n",
    "\n",
    "In this notebook I will not explaining how quicksort works with examples rather go ahead and implement the bits of quick sort which by itself is self explanatory. The interesting part of the notebook is the proof for correctness and the running time analysis of the quicksort\n",
    "\n",
    "***\n",
    "\n",
    "Following code gives us the an implementation of in place partitioning of input array. The assumption is that the first element of the list will act as the pivot, before we implement the partition, let us implement a swap function that will swap values of two given index of an array. The partition sub routine apart from partitioning the"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {},
   "outputs": [],
   "source": [
    "def swap(element1, element2):\n",
    "    temp = element1\n",
    "    element1 = element2\n",
    "    element2 = temp\n",
    "    return element1, element2\n",
    "\n",
    "def partition(array, l, r):\n",
    "    #Partitions the input array in place and returns the index of the pivot element\n",
    "    #in the partitioned array and the number of comparisons performed which is required for the analysis\n",
    "    #of the number of comparisons performed.\n",
    "    i = l + 1\n",
    "    for j in range(1, r):\n",
    "        if array[0] > array[j]:\n",
    "            if j != i:\n",
    "                array[i], array[j] = swap(array[i], array[j])   \n",
    "            i += 1\n",
    "    array[0], array[i-1] = swap(array[0], array[i-1]) \n",
    "    return array, i-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "('When Pivot is an Intermediate number', ([0, 2, 1, 3, 5, 7, 8], 3))\n",
      "('When Pivot is the Maximum number', ([3, 2, 1, 5, 0, 7, 8], 6))\n",
      "('When Pivot is the Minimum number', ([0, 2, 1, 5, 8, 7, 3], 0))\n",
      "('Input array is same as the example in book', ([1, 2, 3, 5, 8, 4, 7, 6], 2))\n"
     ]
    }
   ],
   "source": [
    "print('When Pivot is an Intermediate number', partition([3, 2, 1, 5, 0, 7, 8], 0, 7))\n",
    "print('When Pivot is the Maximum number', partition([8, 2, 1, 5, 0, 7, 3], 0, 7))\n",
    "print('When Pivot is the Minimum number', partition([0, 2, 1, 5, 8, 7, 3], 0, 7))\n",
    "print('Input array is same as the example in book', partition([3, 8, 2, 5, 1, 4, 7, 6], 0, 8))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With a working partition function, let us put in place a quick sort function. The impementation is pretty simple and as against merge sort, where we have the merge function after the recursive calls, in quicksort, we perform a linear scan for partition first, followed by the recursive calls on smaller arrays."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {},
   "outputs": [],
   "source": [
    "def quicksort_naivepivot(array , init_ncomparisons = 0):\n",
    "    global ncomparisons\n",
    "    if init_ncomparisons == 0:\n",
    "        ncomparisons = 0\n",
    "    n = len(array)\n",
    "    if n == 1:\n",
    "        print(array)\n",
    "        return array, ncomparisons\n",
    "    if n > 1:\n",
    "        print(array)\n",
    "        pivot = array[0]   # 1st element is pivot\n",
    "        array, pvtidx = partition(array, 0, n)\n",
    "        ncomparisons += n-1\n",
    "        print(\"partitioned : {}\".format(array))\n",
    "        if pvtidx != 0:\n",
    "            array[:pvtidx], _ = quicksort_naivepivot(array[:pvtidx], init_ncomparisons = 1)\n",
    "        if pvtidx != n-1:\n",
    "            array[pvtidx+1:], _ = quicksort_naivepivot(array[pvtidx+1:], init_ncomparisons = 1)\n",
    "            \n",
    "    return array, ncomparisons"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[3, 8, 2, 5, 1, 4, 7, 6]\n",
      "partitioned : [1, 2, 3, 5, 8, 4, 7, 6]\n",
      "[1, 2]\n",
      "partitioned : [1, 2]\n",
      "[2]\n",
      "[5, 8, 4, 7, 6]\n",
      "partitioned : [4, 5, 8, 7, 6]\n",
      "[4]\n",
      "[8, 7, 6]\n",
      "partitioned : [6, 7, 8]\n",
      "[6, 7]\n",
      "partitioned : [6, 7]\n",
      "[7]\n",
      "([1, 2, 3, 4, 5, 6, 7, 8], 15)\n"
     ]
    }
   ],
   "source": [
    "#print(quicksort_naivepivot([3, 2, 1, 5, 0, 7, 8]))\n",
    "print(quicksort_naivepivot([3, 8, 2, 5, 1, 4, 7, 6]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "def choose_pivot(array):\n",
    "    randomidx = random.randint(0,len(array)-1)\n",
    "    array[0], array[randomidx] = swap(array[0], array[randomidx])\n",
    "    return array\n",
    "\n",
    "def quicksort_randomizedpivot(array , init_ncomparisons = 0):\n",
    "    global ncomparisons\n",
    "    if init_ncomparisons == 0:\n",
    "        ncomparisons = 0\n",
    "    n = len(array)\n",
    "    if n == 1:\n",
    "        return array, ncomparisons\n",
    "    if n > 1:\n",
    "        array = choose_pivot(array)   # Randomized algorithm: choosing pivot\n",
    "        array, pvtidx = partition(array, 0, n)\n",
    "        ncomparisons += n-1\n",
    "        if pvtidx != 0:\n",
    "            array[:pvtidx], _ = quicksort_randomizedpivot(array[:pvtidx], init_ncomparisons = 1)\n",
    "        if pvtidx != n-1:\n",
    "            array[pvtidx+1:], _ = quicksort_randomizedpivot(array[pvtidx+1:], init_ncomparisons = 1)\n",
    "    return array, ncomparisons"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "QuickSorted array & Number of comparisons made using randomized algorithm:\n",
      "([0, 1, 2, 3, 5, 7, 8], 11)\n",
      "([1, 2, 3, 4, 5, 6, 7, 8], 22)\n"
     ]
    }
   ],
   "source": [
    "print(\"QuickSorted array & Number of comparisons made using randomized algorithm:\")\n",
    "print(quicksort_randomizedpivot([3, 2, 1, 5, 0, 7, 8]))\n",
    "print(quicksort_randomizedpivot([3, 8, 2, 5, 1, 4, 7, 6]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***\n",
    "\n",
    "\n",
    "We see above that the sorting function works well. However the efficiency of Quick sort vastly depends on how even the chosen pivot splits in input array into. Thus the choice of Pivot function is extremely crucial for the running time of the Quick sort algorithm. We know Merge sort runs in $O(nlog n)$ time and thats what we aim for. The benefit of quick sort over Merge sort is that it requires no extra memory apart from the constant memory required to store the variables. The simplest way to choose a pivot, is to always choose the first element of the input array.\n",
    "\n",
    "Suppose with this approach, we end up attempting to sort an already sorted array, then by picking up the first element in the list, we do not get a left and a right split but all elements in the right (or left, depending on sorted and sorting order) split except the pivot. This will continue to happen till the entire array is sorted. This is most possible uneven split we can get in Quick sort and we will end up comparing the pivot with all remaining numbers to be sorted, this giving us a worst case time complexity of $O(n^2)$\n",
    "\n",
    "Another extreme scenario is to implement a choose pivot function that select the median of available values in the left or right side of the array. Assuming that the operation to choose the pivot is a linear time operation (which we will see in next chapter) we can then perform the operation to find the pivot (which is a perfect median of the values we are partioning) and the partition collectively is done in linear time(with high constants, but these are suppressed in Big Oh notations). Thus\n",
    "\n",
    "$T(n) \\leq 2\\cdot T(\\frac{n}{2}) + O(n)$\n",
    "\n",
    "By master method this a divide and conquer algorithm that runs in $O(n log n)$ time. Note that for any other implementation of choose pivot function, we cannot use master method as the input is not necessarily evenly split. However, when the pivot chosen is guaranteed to be a median of the array being partioned, we are guaranteed an even split.\n",
    "\n",
    "Thus we have seen how a good choose pivot functionality decides the runing time of the quick sort algorithm\n",
    "\n",
    "***\n",
    "\n",
    "Before we continue with the the analysis of the running time of Quick Sort algorithm, let us, prove the correctness of the algorithm\n",
    "\n",
    "The correctness is proven by proving the following 2\n",
    "\n",
    "Prove the correctness of the partioning routine\n",
    "Given the previous, use induction to prove the correctness of the quick sort algorithm\n",
    "First for the correctness of Quick Sort, the partition subroutine partitions the input array in a way where the pivot ends up in right place for the entire array where all elements on the left of the pivot are less than or equal to the pivot element and the elements on the right are greater than the pivot. With this in mind lets prove the correctness of Quicksort by induction.\n",
    "\n",
    "For base case, n = 1, Quicksort correctly sorts the input array\n",
    "\n",
    "The inductive hypothesis is that for k < n, quicksort function p(k) correctly sorts the input. Consider that an input array of size n is given to the quicksort function. The partition function correctly places the pivot in the rightful place and strictly gives us two smaller array of length < n with elements of the left smaller or equal to pivot and on the right, greater than pivot. Since we know by inductive hypothesis, p(k) holds with k < n, quick sort will correctly sort the left and right sub arrays correctly. Since the pivot is already in righ position, the entire array will be sorted.\n",
    "\n",
    "***\n",
    "\n",
    "TODO: Give proof for correctness of partition\n",
    "\n",
    "***\n",
    "\n",
    "Coming back to the running time of the Quicksort algorithm, we saw that always chosing the first element of the array as pivot will give bad running time of $O(n^2)$ and chosing the pivot by finding the perfect median element in $O(n)$ time will give us a guaranteed $O(nlog n)$ time. However this approach is an overkill and will see if there is an alternate approach which will be fast pivot selection technique (near $O(1)$ time) but gives better running time guarantees than always chosing the first element as pivot.\n",
    "\n",
    "***\n",
    "\n",
    "**Performance of Randomized pivot selection**<br>\n",
    "**Intuition** <br>\n",
    "Let us assume that the size of the input becomes $\\alpha\\cdot n$ on each iteration where $\\alpha < 0$. To lets assume we hot the base case in k iterations. Thus $\\alpha ^ k n = 1$. Taking log on both sizes gives us\n",
    "\n",
    "$log\\alpha^k + logn = 0$\n",
    "\n",
    "$k\\cdot log \\alpha = -logn$\n",
    "\n",
    "Let $\\beta = \\frac{1}{\\alpha}$ this $log\\alpha = -log\\beta$\n",
    "\n",
    "From above we can say that $k = \\frac{logn}{log\\beta} = log_{\\beta}\\alpha$\n",
    "\n",
    "This makes sense as in case of merge sort where $\\alpha = 0.5$, that is when the input array is halved on each recursive call we hit the base case in $log_2n$ iterations. With $\\alpha = 0.5$ the value $\\beta = 2$\n",
    "\n",
    "With the above in mind, we know that in case of quick sort taking an exact median is guaranteed to split the array in two exact parts and the running time can be derived using Master method. However, if we are ok with an approximate median, meaning, the split after partition gives us a sub array of size maximum 75% of input array (or a minimum 25% of the input array), then we can say that we would need a maximum of $log_{4/3}n$ levels till we reach the base case. In case of quick sort, the arrays are not overlapping at each level and thus the work done at each level is no more than n. Thus intuitively we have $n\\cdot log_{4/3}n$ or $O(nlogn)$ running time\n",
    "\n",
    "**Mathematical proof** <br>\n",
    "Let $\\Omega$ be a sample space of all possible outcomes of random choices of pivot in Quicksort. This is a well defined random variable because whenever all the pivot element choices are predetermined ($\\omega \\in \\Omega$), QuickSort has a fixed running time RT($\\omega$) ranging between $O(nlogn)$ to $O(n^2)$\n",
    "\n",
    "We then have another random variavble C which is for counting the number of comparisons between two different elements of the array.\n",
    "\n",
    "One Lemma we we will use is, for a give array A of length $\\geq$ 2 and every pivot sequence $\\omega$, there is a constant a > 0 such that $RT(\\omega)\\: \\leq a\\cdot C(\\omega)$\n",
    "\n",
    "***\n",
    "\n",
    "Before we proceed, let us see how to decompose a bigger problem and use linearity of expectation to come up with an expected value for a complex variable\n",
    "\n",
    "Let Y be the complex random variable expressed a sum of simple random variable X as $Y = \\sum_{l = 1}^{m}X_l$\n",
    "\n",
    "Thus $E[Y] = E[\\sum_{l = 1}^{m}X_l] = \\sum_{l = 1}^{m}E[X_l]$\n",
    "\n",
    "If X is an indicator random variable with value 1 and 0 with some probability, the expected value of X is $E[X_l] = 0\\cdot P_r[X_l =0] + 1\\cdot P_r[X_l = 1] = P_r[X_l = 1]$\n",
    "\n",
    "Thus $E[Y] = \\sum_{l = 1}^{m}P_r[X_l = 1]$\n",
    "\n",
    "***\n",
    "\n",
    "We need to decompose this random variable C into a smaller random variable in a similar way. We need to decompose the random variable C to an indicator random variable. Let is assume $z_i$ denotes the $i{th}$ smallest number in the array. Note that this value is the position of $i{th}$ element in the sorted array and not the input array. For example if 6, 8, 9, 2 are the input values, then $z_1, z_2, z_3\\: and\\: z_4$ are 2, 6, 8, and 9 respectively\n",
    "\n",
    "for every $i, j \\in 1, 2, 3 \\dots n$ where i < j, we define an indicator random variable $X_{ij}$ which denotes whether or not the the $z_i$ and $z_j$ variables are compared or not\n",
    "\n",
    "$C(\\omega)\\: = \\: \\sum_{i = 1}^{n - 1} \\sum_{j = i + 1}^{n} X_{ij}$ $E[C(\\omega)]\\: = \\: \\sum_{i = 1}^{n - 1} \\sum_{j = i + 1}^{n} E[X_{ij}] \\: = \\sum_{i = 1}^{n - 1}\\:  \\sum_{j = i + 1}^{n} P_r[X_{ij} = 1]$\n",
    "\n",
    "One fact to be aware of is that two given values in an array are either compared once or never compared. We will see this why using the following four scenarios.\n",
    "\n",
    "With two numbers $z_i$ and $z_j$, following things can happen\n",
    "\n",
    "- If the chosen pivot is less than $z_i$ the number $z_i$ and $z_j$ (and all numbers between them), both will appear together in the next recursive call\n",
    "- Similarly, If the chosen pivot is greater than $z_j$ the number $z_i$ and $z_j$ (and all numbers between them), both will appear together in the next recursive call.\n",
    "- If one number between $z_i$ and $z_j$ are chosen, then $z_i$ and $z_j$ both will appear on different sub arrays on which the quicksort routine is called. Not only would these two number wont be compared now, they would never be compared in any future recursive call.\n",
    "- One of $z_i$ and $z_j$ is chose, as pivot. In this case they would be compared.\n",
    "\n",
    "Thus we can see that whether the number $z_i$ and $z_j$ are compared with each other or not is dependent on whether these two numbers and any of the numbers between them is chosen as pivot. From $z_i$ to $z_j$, we have j - i + 1 possible numbers. The probability of $z_i$ or $z_j$ being picked as a pivot between these numbers is therefore $\\frac{2}{j - i + 1}$\n",
    "\n",
    "Coming back to expected value of C we have\n",
    "\n",
    "$E[C] = \\sum_{i = 1}^{n - 1}\\sum_{j = i + 1}^{n}\\frac{2}{j - i + 1}$\n",
    "\n",
    "$\\sum_{j = i + 1}^{n}\\frac{2}{j - i + 1} = 2\\cdot (\\frac{1}{2} + \\frac{1}{3} \\dots \\frac{1}{n - i + 1})$\n",
    "\n",
    "Therefore, $E[C] = \\sum_{i = 1}^{n - 1}\\sum_{j = i + 1}^{n}\\frac{2}{j - i + 1} \\leq \\sum_{i = 1}^{n - 1}\\sum_{j = 2}^{n}\\frac{2}{j}\\: =\\: 2(n - 1)\\sum_{j = 2}^{n}\\frac{1}{j}$\n",
    "\n",
    "What is the value of $\\sum_{j = 2}^{n}\\frac{1}{j}$\n",
    "\n",
    "The value $\\sum_{j = 2}^{n}\\frac{1}{j}\\: \\leq \\:\\int_1^n \\frac{1}{x}\\cdot dx \\: = \\: ln\\:\\vert_1^n  = ln(n) - ln0 = ln(n)$\n",
    "\n",
    "Therefore\n",
    "\n",
    "$E[C] = 2(n - 1)\\sum_{j = 2}^{n}\\frac{1}{j} \\: \\leq\\: 2(n - 1)\\cdot ln(n)$. Therefore running time of Quicksort is $O(nlogn)$\n",
    "\n",
    "***\n",
    "\n",
    "TODO: Work on the optional sectctional to prove that no comparison based sorting algorithm do better than $O(nlogn)$. I am yet to convince myself with the proof and not everything is intuitive as of yet to me.\n",
    "\n",
    "***\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Programming Assignment #3 \n",
    "**GENERAL DIRECTIONS:**\n",
    "\n",
    "Download the following text file: QuickSort.txt\n",
    "\n",
    "The file contains all of the integers between 1 and 10,000 (inclusive, with no repeats) in unsorted order. The integer in the $i^{th}$ row of the file gives you the $i^{th}$ entry of an input array.\n",
    "\n",
    "Your task is to compute the total number of comparisons used to sort the given input file by QuickSort. As you know, the number of comparisons depends on which elements are chosen as pivots, so we'll ask you to explore three different pivoting rules.\n",
    "\n",
    "You should not count comparisons one-by-one. Rather, when there is a recursive call on a subarray of length m, you should simply add m-1 to your running total of comparisons. (This is because the pivot element is compared to each of the other m-1 elements in the subarray in this recursive call.)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 129,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "def choose_pivot_last(array):\n",
    "    array[0], array[-1] = swap(array[0], array[-1])\n",
    "    return array\n",
    "\n",
    "def choose_pivot_median_of_3_index(array):\n",
    "    mid = len(array) // 2\n",
    "    if len(array) % 2 == 0:\n",
    "        mid -= 1\n",
    "    median = mid if array[0] < array[mid] and  array[mid] < array[-1] or array[0] > array[mid] and  array[mid] > array[-1] else  (-1 if array[0] < array[-1] and  array[-1] < array[mid] or array[0] > array[-1] and  array[-1] > array[mid] else 0 )\n",
    "    if median == -1 or median == mid: \n",
    "        array[0], array[median] = swap(array[0], array[median])\n",
    "    return array\n",
    "\n",
    "def quicksort_choosepivot(array , init_ncomparisons = 0, choose_pivot = lambda x : x):\n",
    "    global ncomparisons\n",
    "    if init_ncomparisons == 0:\n",
    "        ncomparisons = 0\n",
    "    n = len(array)\n",
    "    if n == 1:\n",
    "        return array, ncomparisons\n",
    "    if n > 1:\n",
    "        array = choose_pivot(array)   # Randomized algorithm: choosing pivot\n",
    "        array, pvtidx = partition(array, 0, n)\n",
    "        ncomparisons += n-1\n",
    "        if pvtidx != 0:\n",
    "            array[:pvtidx], _ = quicksort_choosepivot(array[:pvtidx], init_ncomparisons = 1, choose_pivot = choose_pivot)\n",
    "        if pvtidx != n-1:\n",
    "            array[pvtidx+1:], _ = quicksort_choosepivot(array[pvtidx+1:], init_ncomparisons = 1, choose_pivot = choose_pivot)\n",
    "    return array, ncomparisons"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Problem 1** <br>\n",
    "For the first part of the programming assignment, you should always use the first element of the array as the pivot element."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 107,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/Users/aishwaya/anaconda2/lib/python2.7/site-packages/urllib3/connectionpool.py:858: InsecureRequestWarning: Unverified HTTPS request is being made. Adding certificate verification is strongly advised. See: https://urllib3.readthedocs.io/en/latest/advanced-usage.html#ssl-warnings\n",
      "  InsecureRequestWarning)\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of comparisons when FIRST element of the array is the pivot element: 162085\n"
     ]
    }
   ],
   "source": [
    "import urllib3\n",
    "http = urllib3.PoolManager()\n",
    "\n",
    "def test_case():\n",
    "    # Test case\n",
    "    r1 = http.request('GET', \"https://d18ky98rnyall9.cloudfront.net/_32387ba40b36359a38625cbb397eee65_QuickSort.txt?Expires=1559779200&Signature=NfhNRh0cyqaK~TTY9v6Y2EXzOqs7vgi-FOcNfJQDqMUdFZ0W8qvj6uvI2StpmnCUsW0V2nRUmjpv0PzHdKy0nY7fcEoYmFlZynrqYW8bgjpINSSspXUySxj9LYxgt4JI63kX9FwWLuT~kJZr7LuJfGmmtTpdwKSbeSEXdWLBOgo_&Key-Pair-Id=APKAJLTNE6QMUY6HBC5A\")\n",
    "    IntegerArrayString = r1.data.split('\\r\\n')\n",
    "    del IntegerArrayString[-1]\n",
    "    IntegerArray = [int(i) for i in IntegerArrayString]\n",
    "    return IntegerArray\n",
    "\n",
    "print(\"Number of comparisons when FIRST element of the array is the pivot element: {}\".format(quicksort_choosepivot(test_case())[1]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Problem 2** <br>\n",
    "Compute the number of comparisons (as in Problem 1), always using the final element of the given array as the pivot element. Again, be sure to implement the Partition subroutine exactly as it is described in the video lectures.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 108,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/Users/aishwaya/anaconda2/lib/python2.7/site-packages/urllib3/connectionpool.py:858: InsecureRequestWarning: Unverified HTTPS request is being made. Adding certificate verification is strongly advised. See: https://urllib3.readthedocs.io/en/latest/advanced-usage.html#ssl-warnings\n",
      "  InsecureRequestWarning)\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of comparisons when LAST element of the array is the pivot element: 164123\n"
     ]
    }
   ],
   "source": [
    "print(\"Number of comparisons when LAST element of the array is the pivot element: {}\".format(quicksort_choosepivot(test_case(), choose_pivot = lambda x : choose_pivot_last(x))[1]))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Problem 3** <br>\n",
    "Compute the number of comparisons (as in Problem 1), using the \"median-of-three\" pivot rule. [The primary motivation behind this rule is to do a little bit of extra work to get much better performance on input arrays that are nearly sorted or reverse sorted.] In more detail, you should choose the pivot as follows. Consider the first, middle, and final elements of the given array. (If the array has odd length it should be clear what the \"middle\" element is; for an array with even length 2k, use the $k^{th}$\n",
    "th\n",
    "  element as the \"middle\" element. So for the array 4 5 6 7, the \"middle\" element is the second one ---- 5 and not 6!) Identify which of these three elements is the median (i.e., the one whose value is in between the other two), and use this as your pivot. As discussed in the first and second parts of this programming assignment, be sure to implement Partition exactly as described in the video lectures (including exchanging the pivot element with the first element just before the main Partition subroutine)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 131,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/Users/aishwaya/anaconda2/lib/python2.7/site-packages/urllib3/connectionpool.py:858: InsecureRequestWarning: Unverified HTTPS request is being made. Adding certificate verification is strongly advised. See: https://urllib3.readthedocs.io/en/latest/advanced-usage.html#ssl-warnings\n",
      "  InsecureRequestWarning)\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of comparisons when MEDIAN element of the array is the pivot element: 138382\n"
     ]
    }
   ],
   "source": [
    "print(\"Number of comparisons when MEDIAN element of the array is the pivot element: {}\".format(quicksort_choosepivot(test_case(), choose_pivot = lambda x : choose_pivot_median_of_3_index(x))[1]))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Test Your Understanding\n",
    "\n",
    "**Problem 5.1** <br>\n",
    "\n",
    "Q. Let 0 < $\\alpha$ < .5 be some constant (independent of the input array length n). Recall the Partition subroutine employed by the QuickSort algorithm, as explained in lecture. What is the probability that, with a randomly chosen pivot element, the Partition subroutine produces a split in which the size of the smaller of the two subarrays is ≥ $\\alpha$ times the size of the original array?\n",
    "\n",
    "A. Suppose $\\alpha$ is a number between 0 and 0.5, then what is the probability that for a randomly chosen pivot, the size of each sub problem is at least $\\alpha$ times n.\n",
    "\n",
    "To get an two arrays of size minimum $\\alpha$ times n, the number chosen as pivot has to be greater than the $\\alpha^{th}$ order statistic, but no greater than $(1 - \\alpha)n^{th}$ order statistic. We have total of $2\\alpha n$ numbers ($\\alpha n + (n - n(1 - \\alpha)) = 2\\alpha n$) whose value is less than $\\alpha^{th}$ and greater than $n(1 - \\alpha)^{th}$ statistic. Thus the probability that the array size is less than $\\alpha n$ is $2\\alpha$ and thus the probability that the size of atleast $\\alpha n$ is $1 - 2\\alpha$\n",
    "\n",
    " <br>\n",
    "**Problem 5.2** <br>\n",
    "\n",
    "Q.  Now assume that you achieve the approximately balanced splits above in every recursive call --- that is, assume that whenever a recursive call is given an array of length k, then each of its two recursive calls is passed a subarray with length between $\\alpha k$ and $(1 - \\alpha)k$ (where $\\alpha$ is a fixed constant strictly between 0 and .5.5). How many recursive calls can occur before you hit the base case? Equivalently, which levels of the recursion tree can contain leaves? Express your answer as a range of possible numbers dd, from the minimum to the maximum number of recursive calls that might be needed.\n",
    "\n",
    "A. Let $\\alpha$ be some constant independent of n and between 0 and 0.5. Whenever we make a recursive call on an array of length k, we get sub array with length between $\\alpha k$ and $(1 - \\alpha)k$.\n",
    "\n",
    "How many recursive calls are needed before we hit the base case.\n",
    "\n",
    "For an array of size k that is shrinking at a rate of $\\alpha$, we will need $-log_{\\alpha}k$ iteration. This is something we have seen previously. The sign negative is needed as log to the base of a number less than 1 is negative and the number of iterations have to be positive. Now $-log_{\\alpha}k = -\\frac{ln\\:k}{\\ln \\alpha}$, thus we will require between $-\\frac{ln\\:k}{\\ln \\alpha}$ and $-\\frac{ln\\:k}{\\ln (1 - \\alpha)}$ iterations\n",
    "\n",
    " <br>\n",
    "**Problem 5.3** <br>\n",
    "\n",
    "Define the recursion depth of QuickSort to be the maximum number of successive recursive calls before it hits the base case --- equivalently, the number of the last level of the corresponding recursion tree. Note that the recursion depth is a random variable, which depends on which pivots get chosen. What is the minimum-possible and maximum-possible recursion depth of QuickSort, respectively?\n",
    "\n",
    "A. Minimum: Θ(log(n)) ; Maximum: Θ(n)\n",
    "The best case is when each pivot is the true median of the input array, in which case on each iteration we split the array in exact halves and thus the best possible tree depth we can expect is $O(\\log n)$, on other hand the pivot chosen splits the array in the work possible way with all elements ending up on one side, in which case the maximum possible length of the tree is $O(n)$\n",
    "\n",
    "\n",
    " <br>\n",
    "**Problem 5.4** <br>\n",
    "\n",
    "Q.  Consider a group of k people. Assume that each person's birthday is drawn uniformly at random from the 365 possibilities. (And ignore leap years.) What is the smallest value of k such that the expected number of pairs of distinct people with the same birthday is at least one?\n",
    "\n",
    "[Hint: define an indicator random variable for each ordered pair of people. Use linearity of expectation.]\n",
    "\n",
    "Options: 366, 27, 23, 20, 28\n",
    "\n",
    "Ans1.  With 𝑑=365 days, the probability a particular pair share a birthday is 1 / 𝑑 <br>\n",
    "With 𝑛 people, there are ${n \\choose 2}$ = $\\frac{𝑛(𝑛−1)}{2}$ pairs of people so the expected number of pairs sharing a birthday is $\\frac{𝑛^{2}−n}{2𝑑}$ <br>\n",
    "∴ This is greater than 1 when n > $\\frac{1+ \\sqrt{1+8𝑑}}{2}$ or n < $\\frac{1− \\sqrt{1+8d}}{2}$, though for this question the answer should be positive so 𝑘>27.523… and an integer\n",
    "\n",
    "Ans2.  Approach using indicator random variable:\n",
    "\n",
    "$$ 𝑋_{𝐢,𝐣,𝐢≠𝐣} = \\begin{cases}\n",
    "1 \\text{ if ith and jth person having same birthday} \\\\\n",
    "0 \\text{ if ith and jth person NOT having same birthday}  \n",
    "\\end{cases}\n",
    "$$\n",
    "\n",
    "$$𝐸(𝑋_{𝑖,𝑗}) = 1∗𝑃(𝑋_{𝑖,𝑗})+0∗(1−𝑃(𝑋_{𝑖,𝑗}))$$\n",
    "$$⇒𝐸(𝑋_{𝑖,𝑗})=𝑃(𝑋_{𝑖,𝑗})$$\n",
    "$$⇒Overall  E=\\sum_{}{} 𝐸_{𝑖,𝑗}$$\n",
    "\n",
    "We need $𝐸≥1$\n",
    "$$⇒[\\sum_{𝑖=1}^{𝑘}\\sum_{𝑗=𝑖+1}^{𝑘} 𝐸_{𝑖,𝑗}] ≥ 1$$\n",
    "$$⇒[\\sum_{𝑖=1}^{𝑘}\\sum_{𝑗=𝑖+1}^{𝑘} P_{𝑖,𝑗}] ≥ 1$$\n",
    "$$⇒[\\sum_{𝑖=1}^{𝑘}\\sum_{𝑗=𝑖+1}^{𝑘} \\frac{1}{365}] ≥ 1$$\n",
    "$$⇒(\\frac{1}{365})[\\sum_{𝑖=1}^{𝑘}\\sum_{𝑗=𝑖+1}^{𝑘} 1 ] ≥ 1$$\n",
    "$$⇒(\\frac{1}{365})[\\sum_{𝑖=1}^{𝑘-1} 1 ] ≥ 1$$\n",
    "$$⇒(\\frac{1}{365})[\\frac{k. (k - 1)}{2} ] ≥ 1$$ <br><br>\n",
    "$$⇒𝑘^{2}−𝑘−730≥0$$<br><br>\n",
    "$$⇒𝑘=⌈1+\\frac{\\sqrt{1+4∗730}{2}}{2}⌉  =  ⌈27.52⌉  =28$$\n",
    "\n",
    "\n",
    " <br> <br>\n",
    "**Problem 5.5** <br>\n",
    "Q.  Let $X_1,X_2,X_3$\t  denote the outcomes of three rolls of a six-sided die. (I.e., each $X_i$\t  is uniformly distributed among ${1,2,3,4,5,6}$ and by assumption they are independent.) Let $Y$ denote the product of $X_1$ and $X_2$  and $Z$ the product of $X_2$ and $X_3$. Which of the following statements is correct?\n",
    "\n",
    "option 1. $Y$ and $Z$ are not independent, but $E[Y*Z]=E[Y]*E[Z]$. <br>\n",
    "option 2. $Y$ and $Z$ are independent, and $E[Y*Z]=E[Y]*E[Z]$.<br>\n",
    "option 3. $Y$ and $Z$  are independent, but $E[Y*Z] \\neq E[Y]*E[Z]$.<br>\n",
    "option 4. $Y$ and $Z$  are not independent, and $E[Y*Z] \\neq E[Y]*E[Z]$.<br>\n",
    "\n",
    "Ans.  $X_1,X_2,X_3$ are variables each taking values   ${1,2,3,4,5,6}$ and each value has a probability $\\frac{1}{6}$. <br>\n",
    "Now,  <br>\n",
    "$Y = X_1 * X_2$ \n",
    "\n",
    "$Z = X_2 * X_3$\n",
    "\n",
    "To find: $E[Y*Z] = E[Y]*E[Z]$  OR $E[Y*Z] \\neq E[Y]*E[Z]$\n",
    "\n",
    "LHS: $E[Y*Z] \\\\\n",
    "= E[X_1 * X_2 * X_2 * X_3 ] \\\\\n",
    "= E[X_1 * X_2 * X_3 ]    \\text{(As in an event $X_2$ can have value  [1,6] only for both the $X_2$  variable above )} \\\\\n",
    "= E[X_1] * E[X_2] * E[X_3] \\text{(As $X_1$ , $X_2$ and $X_3$ are independent )} $\n",
    "\n",
    "RHS: $E[Y]*E[Z]  \\\\\n",
    "=  E[X_1 * X_2] * E[X_2 * X_3 ] \\\\\n",
    "=  E[X_1] * E[X_2] * E[X_2] * E[X_3]   \\text{(As $X_1$ and $X_2$ are independent and $X_2$ and $X_3$ are independent )}$  \n",
    "\n",
    "∴ $ LHS  \\neq RHS $\n",
    "\n",
    "option 4. $Y$ and $Z$  are not independent, and $E[Y*Z] \\neq E[Y]*E[Z]$.<br>\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "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.14"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}