sec15-17-merge-quick-radix-sort.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Section 15: Merge Sort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "## Create a function that receives two parameters and merge them in ascending order\n",
    "# merge([1, 10, 50], [2, 14, 99, 100]) // [1, 2, 10, 14, 50, 99, 100]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## `merge`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def merge(arr1, arr2):\n",
    "    # Create empty arr to store result\n",
    "    res = []\n",
    "\n",
    "    # initialize the index of arr1 and arr2\n",
    "    i = 0\n",
    "    j = 0\n",
    "\n",
    "    while (i < len(arr1)) and (j < len(arr2)):\n",
    "        # When arr[i] <= arr2[j]\n",
    "        if arr1[i] <= arr2[j]:\n",
    "            res.append(arr1[i])\n",
    "            i += 1\n",
    "        \n",
    "        # When arr[i] > arr2[j]\n",
    "        else:\n",
    "            res.append(arr2[j])\n",
    "            j += 1\n",
    "    \n",
    "    # When either one is exhausted\n",
    "    if i < len(arr1): # This means arr2 is exhausted\n",
    "        res += arr1[i:]\n",
    "\n",
    "    if j < len(arr2): # This means arr1 is exhausted\n",
    "        res += arr2[j:]\n",
    "\n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "arr1 = [1, 10, 2550]\n",
    "arr2 = [2, 14, 99, 100]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 10, 14, 99, 100, 2550]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "merge(arr1, arr2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## `mergeSort`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# ===================================================================== #\n",
    "# Create mergeSort using recursion\n",
    "# ===================================================================== #"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def mergeSort(arr):\n",
    "    half = len(arr)//2\n",
    "    if len(arr) <= 1:\n",
    "        return arr\n",
    "    \n",
    "    left = mergeSort(arr[:half])\n",
    "    right = mergeSort(arr[half:]) \n",
    "    return merge(left, right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "arr = [1, 20, 3, 5, 17]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 3, 5, 17, 20]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mergeSort(arr)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Section 16: Quick Sort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Create a pivot function that receives arr, start idx, and end idx)\n",
    "# pivot([4, 8, 2, 1, 5, 7, 6, 3]) // 3\n",
    "# because there are three elements less than 4, so 4 should be in index 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Create swap that receives array and two indices to be swapped\n",
    "def swap(arr, idx1, idx2):\n",
    "    temp      = arr[idx1]\n",
    "    arr[idx1] = arr[idx2]\n",
    "    arr[idx2] = temp"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## `pivot`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The explanation on udemy course is quite complicated, still failed to implement is, but will be fixed later.\n",
    "Instead I found more understanable implementation with python on Youtube, see below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def pivot(arr, start=0, end=len(arr)):\n",
    "    # Define start idx, st = 0 \n",
    "    stix = 0\n",
    "\n",
    "    # Define the current pivot index\n",
    "    pvix = 0\n",
    "\n",
    "    # Set the first element to be pivot\n",
    "    pivot = arr[0]\n",
    "    #print(f\"Initial: {arr}\")\n",
    "    \n",
    "    # Iterate from pvix + 1 to length of array\n",
    "    for i in range(stix+1, len(arr)):\n",
    "        if pivot >= arr[i]:\n",
    "            pvix += 1\n",
    "            swap(arr, i, pvix)\n",
    "            # print(f\"Swapping!: {arr}\")\n",
    "        \n",
    "    # Lastly swap pivot to pvi index\n",
    "    swap(arr, stix, pvix)\n",
    "    # print(f'Last step!: {arr}')  \n",
    "    \n",
    "    return pvix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr = [4, 8, 3, 1, 5]\n",
    "pivot(arr)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## `quickSort`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Note: this was following JS logic, might not applicable to python\n",
    "def quickSort(arr, left=0, right=len(arr)):\n",
    "    print(f'left {left}')\n",
    "    print(f'right {right}')\n",
    "    \n",
    "    i = 0\n",
    "    if left < right-1 and i < 15:    \n",
    "        print('Entering if')\n",
    "        pvix = pivot(arr, left, right)\n",
    "        print(f\"pivot index: {pvix}\")\n",
    "        \n",
    "        # recursion\n",
    "        print('First Left')\n",
    "        quickSort(arr, left, pvix)\n",
    "        \n",
    "        print('Now right')\n",
    "        quickSort(arr, pvix+1, right)\n",
    "        i += 1\n",
    "    \n",
    "    print('======return arr=====')\n",
    "    print(f'{arr}')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Unlimited loop find out why later\n",
    "# quickSort(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "arr = [4, 8, 3, 1, 5]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Using another source\n",
    "https://www.youtube.com/watch?v=kFeXwkgnQ9U&ab_channel=DerrickSherrill"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "def quickSort(arr):\n",
    "    \n",
    "    # Base case\n",
    "    if len(arr) <= 1:\n",
    "        #print('Already length of one')\n",
    "        return arr\n",
    "\n",
    "    # Length of arr\n",
    "    N = len(arr)\n",
    "\n",
    "    piv = arr.pop(N//2)\n",
    "\n",
    "    # Less than \n",
    "    less_than = []\n",
    "    for val in arr:\n",
    "        if val < piv:\n",
    "            less_than.append(val)\n",
    "\n",
    "    # Greater than\n",
    "    great_than = []\n",
    "    for val in arr:\n",
    "        if val > piv:\n",
    "            great_than.append(val)\n",
    "            \n",
    "    lt_sort = quickSort(less_than)\n",
    "    gt_sort = quickSort(great_than)\n",
    "    \n",
    "    return lt_sort + [piv] + gt_sort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "arr = [4, 8, 2, 1, 5, 7, 6, 3, 100, -3, 60]\n",
    "\n",
    "fin = quickSort(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[-3, 1, 2, 3, 4, 5, 6, 7, 8, 60, 100]"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fin"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Section 17: Radix Sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Helper function `getDigit`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Example\n",
    "# getDigit(12345, 0) // 5\n",
    "# getDigit(12345, 1) // 4\n",
    "# getDigit(12345, 2) // 3\n",
    "# getDigit(12345, 3) // 2\n",
    "# getDigit(12345, 4) // 1\n",
    "# getDigit(12345, 5) // 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Return the digit in num at the given place value\n",
    "def getDigit(num, place):\n",
    "    return (num//(10**place))%10    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## `digitCount(num)`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Returns the number of digits in num\n",
    "# digitCOunt(1)   / 1\n",
    "# digitCOunt(15)  / 2\n",
    "# digitCOunt(312) / 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "def digitCount(num):\n",
    "    return len(str(num))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "digitCount(234)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## `mostDigits(nums)`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Given an array of numbers returns number of digits in largest numbers in the list\n",
    "# mostDigits(nums)\n",
    "# mostDigits([1234, 56, 7]); //4\n",
    "# mostDigits([1, 1, 11111, 1]); //5\n",
    "# mostDigits([12, 34, 56, 78]); //2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "def mostDigits(nums):\n",
    "    most = 0    \n",
    "    for n in nums:\n",
    "        most = max(digitCount(n), most)\n",
    "    \n",
    "    return most "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mostDigits([1234, 334564, 56, 78])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## `radixSort`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "def radixSort(arr):\n",
    "    # Figure out the largest number\n",
    "    n_iter = mostDigits(arr)\n",
    "\n",
    "    for k in range(n_iter):\n",
    "        # print(f'Right now k is {k}')\n",
    "\n",
    "        # Create bucket for each digit\n",
    "        bucket = []\n",
    "\n",
    "        # Iterate over arr, getDigit equal to k\n",
    "        for i in range(10):\n",
    "            bucket += [val for val in arr if getDigit(val, k) == i]\n",
    "\n",
    "        # Assign newly sorted newarr as arr\n",
    "        arr = bucket\n",
    "\n",
    "    return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "arr = [1, 300, 10, 62, 453, 67, 11, 1238, 18, 100, 20, 200, 5]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 5, 10, 11, 18, 20, 62, 67, 100, 200, 300, 453, 1238]"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "radixSort(arr)"
   ]
  }
 ],
 "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.7.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}