{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Quick Sort Algorithm - Complexity Analysis"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import random as rdm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def generate_seq(n):\n",
    "    seq = []\n",
    "    for i in range(n):\n",
    "        seq.append(rdm.randint(1,100))\n",
    "    return seq\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[48, 16, 17, 52, 67, 99, 32, 22, 62, 79]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "generate_seq(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def swap(a,b):\n",
    "    temp = a\n",
    "    a = b\n",
    "    b = temp\n",
    "    return a,b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def swapint(x,y):\n",
    "    assert (isinstance(x,int) == isinstance(y,int)),\"Arguments types mismatch, they must be of type int\"\n",
    "    x +=y\n",
    "    y = x - y\n",
    "    x = x - y\n",
    "    return x,y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10 15\n"
     ]
    }
   ],
   "source": [
    "a = 15\n",
    "b = 10\n",
    "a,b = swapint(a,b)\n",
    "print(a,b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Lomuto Partition Scheme"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This scheme is attributed to Nico Lomuto and popularized by Bentley in his book Programming Pearls and Cormen et al. in their book Introduction to Algorithms. This scheme chooses a pivot that is typically the last element in the array. The algorithm maintains index i as it scans the array using another index j such that the elements lo through i (inclusive) are less than or equal to the pivot, and the elements i+1 through j-1 (inclusive) are greater than the pivot. As this scheme is more compact and easy to understand, it is frequently used in introductory material, although it is less efficient than Hoare's original scheme. This scheme degrades to O(n2) when the array is already in order. There have been various variants proposed to boost performance including various ways to select pivot, deal with equal elements, use other sorting algorithms such as Insertion sort for small arrays and so on. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def lomuto_partition(seq,low,high):\n",
    "    i = low\n",
    "    pivot = seq[high]\n",
    "    for j in range(high):\n",
    "        if seq[j] < pivot:\n",
    "            seq[i],seq[j] = swap(seq[i],seq[j])\n",
    "            i+=1\n",
    "    seq[i],seq[high] = swap(seq[i],pivot)\n",
    "    return i\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "seq = [40, 11, 71, 42, 15, 39, 92, 3, 84, 29, 16, 63, 46, 47, 55, 70, 94, 85, 42, 46]\n",
      "partitioned seq: [40, 11, 42, 15, 39, 3, 29, 16, 42, 46, 71, 63, 46, 47, 55, 70, 94, 85, 84, 92] , pivot=46\n"
     ]
    }
   ],
   "source": [
    "array = generate_seq(20)\n",
    "print(\"seq =\",array)\n",
    "p=lomuto_partition(array,0,len(array)-1)\n",
    "print(\"partitioned seq:\",array,\", pivot=%i\"%array[p])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Hoare partition scheme"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The original partition scheme described by C.A.R. Hoare uses two indices that start at the ends of the array being partitioned, then move toward each other, until they detect an inversion: a pair of elements, one greater than or equal to the pivot, one lesser or equal, that are in the wrong order relative to each other. The inverted elements are then swapped. When the indices meet, the algorithm stops and returns the final index. There are many variants of this algorithm, for example, selecting pivot from A[hi] instead of A[lo]. Hoare's scheme is more efficient than Lomuto's partition scheme because it does three times fewer swaps on average, and it creates efficient partitions even when all values are equal. Like Lomuto's partition scheme, Hoare's partitioning also would cause Quicksort to degrade to O(n2) for already sorted input, if the pivot was chosen as the first or the last element. With the middle element as the pivot, however, sorted data results with (almost) no swaps in equally sized partitions leading to best case behavior of Quicksort, i.e. O(n log(n)). Like others, Hoare's partitioning doesn't produce a stable sort. Note that in this scheme, the pivot's final location is not necessarily at the index that was returned, and the next two segments that the main algorithm recurs on are (lo..p) and (p+1..hi) as opposed to (lo..p-1) and (p+1..hi) as in Lomuto's scheme. However, the partitioning algorithm guarantees lo ≤ p < hi which implies both resulting partitions are non-empty, hence there's no risk of infinite recursion."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def hoare_partition(seq,low,high):\n",
    "    pass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Quick Sort Algorithm with Lomuto Partition Scheme"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def quicksort_l(seq,low,high):\n",
    "    if low < high:\n",
    "        pivot = lomuto_partition(seq,low,high)\n",
    "        quicksort_l(seq,low,pivot-1)\n",
    "        quicksort_l(seq,pivot+1,high)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 157,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "seq = [58, 27, 24, 90, 41, 78, 91]\n",
      "sorted seq: [24, 27, 41, 58, 78, 90, 91]\n"
     ]
    }
   ],
   "source": [
    "seq_1 = generate_seq(7)\n",
    "lo = 0 \n",
    "hi= len(seq_1)-1\n",
    "print(\"seq =\",seq_1)\n",
    "quicksort_l(seq_1,lo,hi)\n",
    "print(\"sorted seq:\",seq_1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Quick Sort Algorithm with Hoare Partition Scheme"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def quicksort_h(seq,low,high):\n",
    "    if low < high:\n",
    "        p = hoare_partition(seq,low,high)\n",
    "        quicksort_h(seq,low,pivot)\n",
    "        quicksort_h(seq,pivot+1,high)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "seq_2 = generate_seq(6)\n",
    "lo = 0 \n",
    "hi= len(seq_2)-1\n",
    "print(\"seq =\",seq_2)\n",
    "quicksort_l(seq_2,lo,hi)\n",
    "print(\"sorted seq:\",seq_2)"
   ]
  }
 ],
 "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.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}