Colab_Codes/chapter_sorting_and_selection_algorithms.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "chapter_sorting_and_selection_algorithms.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "toc_visible": true,
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/liyin2015/Algorithms-and-Coding-Interviews/blob/master/chapter_sorting_and_selection_algorithms.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "IQcElo1mM_Sf",
        "colab_type": "text"
      },
      "source": [
        "## Naive Sort in O(n^2)\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "zqAHZFGyelhI",
        "colab_type": "text"
      },
      "source": [
        "### Insertion Sort in O(n^2)"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "q2pruFdZjpm2",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Not in-place\n",
        "def insertionSort(a):\n",
        "  if not a or len(a) == 1:\n",
        "    return a\n",
        "  n = len(a)\n",
        "  sl = [a[0]] # sorted list\n",
        "  for i in range(1, n):\n",
        "    for j in range(i):\n",
        "      if sl[j] > a[i]:\n",
        "        sl.insert(j, a[i])\n",
        "        break\n",
        "    if len(sl) != i + 1: # not inserted yet\n",
        "      sl.insert(i, a[i])\n",
        "  return sl"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "z09E9HTdlMSE",
        "colab_type": "code",
        "outputId": "9ce33518-bc5f-4286-8f0e-37ef296c8c2d",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "a = [9, 10, 2, 8, 9, 3, 7]\n",
        "sa = insertionSort(a)\n",
        "sa"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[2, 3, 7, 8, 9, 9, 10]"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 9
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "yJL27nHcNEJl",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Backward and in-place\n",
        "def insertionSort(a):\n",
        "  if not a or len(a) == 1:\n",
        "    return a\n",
        "  n = len(a)\n",
        "  for i in range(1, n):\n",
        "    t = a[i]\n",
        "    j = i - 1\n",
        "    while j >= 0 and t < a[j]: \n",
        "      a[j+1] = a[j] # Move item backward\n",
        "      j -= 1\n",
        "    a[j+1] = t      \n",
        "  return"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Zb5jMt-iScSz",
        "colab_type": "code",
        "outputId": "bb15e619-06fe-4c65-d989-bf2bf16d6c2e",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "a = [9, 10, 2, 8, 9, 3, 7]\n",
        "insertionSort(a)\n",
        "print(a)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[2, 3, 7, 8, 9, 9, 10]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "lHFCwzZNGrMu",
        "colab_type": "text"
      },
      "source": [
        "### Bubble Sort in O(n^2)"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "uqzSlyDXGzhO",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def bubbleSort(a):\n",
        "  if not a or len(a) == 1:\n",
        "    return \n",
        "  n = len(a)\n",
        "  for i in range(n - 1): #n-1 passes \n",
        "    for j in range(n - i -1): \n",
        "      # Swap\n",
        "      if a[j] > a[j + 1]:\n",
        "        a[j], a[j + 1] = a[j + 1], a[j] \n",
        "  return"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "dkpw1G1Xb9Gp",
        "colab_type": "code",
        "outputId": "69676f57-56a6-40db-f162-2c6f50234b8d",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "a = [9, 10, 2, 8, 9, 3]\n",
        "bubbleSort(a)\n",
        "a"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[2, 3, 8, 9, 9, 10]"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 21
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "B-WK_VNi_unM",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def bubbleSortOptimized(a):\n",
        "    if not a or len(a) == 1:\n",
        "        return\n",
        "    n = len(a)\n",
        "    for i in range(n - 1): #n-1 passes, \n",
        "      bSwap = False\n",
        "      for j in range(n - i -1): #each pass will have valid window [0, n-i], and j is the starting index of each pair\n",
        "        if a[j] > a[j + 1]:\n",
        "          a[j], a[j + 1] = a[j + 1], a[j] #swap\n",
        "          bSwap = True\n",
        "      if not bSwap:\n",
        "        break\n",
        "    return"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "npb5NRJdI4sV",
        "colab_type": "code",
        "outputId": "a91cc02d-78be-4623-f9be-417aa09a2772",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "a = [9, 10, 2, 8, 9, 3]\n",
        "bubbleSortOptimized(a)\n",
        "a"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[2, 3, 8, 9, 9, 10]"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 24
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RZwzr_7xBjae",
        "colab_type": "text"
      },
      "source": [
        "### Selection Sort in O(n^2)\n",
        "In selection sort, each time it selects the current largest item and swap it with the last item in the unrestricted region.\n",
        "Given the input size to be `n`, we have index `[0, n-1]`. \n",
        "\n",
        "* At the first pass, we choose the largest item from `A[0,n-1]` and swap it with `A[n-1]`. \n",
        "\n",
        "* At the second pass, we choose the largest item from `A[0,n-2]` and swap it with `A[n-2]`. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ud6JuKtBhZ5N",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def selectSort(a):\n",
        "  n = len(a)\n",
        "  for i in range(n - 1): #n-1 passes \n",
        "    ti = n - 1 - i\n",
        "    li = 0 # The index of the largest item\n",
        "    for j in range(n - i):\n",
        "      if a[j] >= a[li]:\n",
        "        li = j\n",
        "    # swap li and ti\n",
        "    a[ti], a[li] = a[li], a[ti]\n",
        "  return "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "e0U-HGHcBpL4",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def selectSort(a):\n",
        "  n = len(a)\n",
        "  for i in range(n - 1): #n-1 passes \n",
        "    ti = n - 1 - i\n",
        "    li = 0 # The index of the largest item\n",
        "    for j in range(n - i):\n",
        "      if a[j] >= a[li]:\n",
        "        li = j\n",
        "    # swap li and ti\n",
        "    print('swap', a[li], a[ti], li)\n",
        "    a[ti], a[li] = a[li], a[ti]\n",
        "    print(a)\n",
        "  return a"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "r3v62LNjEZVY",
        "colab_type": "code",
        "outputId": "ab2a8871-62d7-4190-dced-149fba761a64",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 219
        }
      },
      "source": [
        "a = [9, 10, 2, 8, 9, 3]\n",
        "selectSort(a)\n",
        "a"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "swap 10 3 1\n",
            "[9, 3, 2, 8, 9, 10]\n",
            "swap 9 9 4\n",
            "[9, 3, 2, 8, 9, 10]\n",
            "swap 9 8 0\n",
            "[8, 3, 2, 9, 9, 10]\n",
            "swap 8 2 0\n",
            "[2, 3, 8, 9, 9, 10]\n",
            "swap 3 3 1\n",
            "[2, 3, 8, 9, 9, 10]\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[2, 3, 8, 9, 9, 10]"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 31
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "g1CFDBHpGaOG",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def insertionSort(a):\n",
        "  '''implement insertion sort'''\n",
        "  if not a or len(a) == 1:\n",
        "    return a\n",
        "  n = len(a)\n",
        "  sl = [a[0]] + [None] *(n-1) # sorted list\n",
        "  for i in range(1, n): # items to be inserted into the sorted\n",
        "    key = a[i]\n",
        "    j = i-1 \n",
        "\n",
        "    while j >= 0 and sl[j] > key: # compare key from the last sorted element\n",
        "      sl[j+1] = sl[j] # shift a[j] backward\n",
        "      j -= 1\n",
        "    sl[j+1] = key\n",
        "    print(sl)\n",
        "  return sl\n",
        "      "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "EI1bDD3106fV",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def shift(a, start, end):\n",
        "  for i in range(end, start, -1): # [i, j)\n",
        "    a[i] = a[i-1]\n",
        "    \n",
        "def insertionSortForward(a):\n",
        "  if not a or len(a) == 1:\n",
        "    return a\n",
        "  n = len(a)\n",
        "  sl = [a[0]] # sorted list\n",
        "  for i in range(1, n): # items to be inserted into the sorted\n",
        "    for j in range(i):\n",
        "      if a[i] < a[j]:\n",
        "        # shift all other elements [j, i-1]\n",
        "        tmp = a[i]\n",
        "        shift(a, j, i)\n",
        "        a[j] = tmp   \n",
        "  return a\n",
        "\n",
        "def insertionSortInPlace(a):\n",
        "  if not a or len(a) == 1:\n",
        "    return a\n",
        "  n = len(a)\n",
        "  for i in range(1, n): # items to be inserted into the sorted\n",
        "    t = a[i]\n",
        "    j = i - 1\n",
        "    while j >= 0 and t < a[j]: # keep comparing if target is still smaller\n",
        "      a[j+1] = a[j] # shift current item backward\n",
        "      j -= 1\n",
        "    a[j+1] = t # a[j] <= t , insert t at the location j+1     \n",
        "  return a"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "NgeLGKn51mxY",
        "colab_type": "code",
        "outputId": "6051e043-4c10-48c3-d477-10bb3b13a05b",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "a = [9, 10, 2, 8, 9, 3, 7]\n",
        "print(insertionSortInPlace(a))"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[2, 3, 7, 8, 9, 9, 10]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GN1yseSKImNy",
        "colab_type": "text"
      },
      "source": [
        "## Merge Sort O(nlgn)"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "rILA4lBhdPxD",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def merge(l, r): \n",
        "  ans = []\n",
        "  # Two pointers each points at l and r\n",
        "  i = j = 0 \n",
        "  n, m = len(l), len(r)\n",
        "\n",
        "  while i < n and j < m: \n",
        "    if l[i] <= r[j]:\n",
        "      ans.append(l[i])\n",
        "      i += 1\n",
        "    else:\n",
        "      ans.append(r[j])\n",
        "      j += 1\n",
        "      \n",
        "  ans += l[i:]\n",
        "  ans += r[j:]\n",
        "  return ans\n",
        "  "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DK003Ic1Isb3",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def mergeSort(a, s, e):\n",
        "  if s == e:\n",
        "    return [a[s]]\n",
        "\n",
        "  m = (s + e) // 2 \n",
        "\n",
        "  l = mergeSort(a, s , m)\n",
        "  r = mergeSort(a, m+1, e)\n",
        "  return merge(l, r)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ys6tUAd8i7ao",
        "colab_type": "code",
        "outputId": "afc20a0d-012e-413f-baf1-f098bb8e23ce",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "a = [9, 10, 2, 8, 9, 3, 7, 9]\n",
        "mergeSort(a, 0, len(a)-1)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[2, 3, 7, 8, 9, 9, 9, 10]"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 34
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "IL6hPk6IjGSf",
        "colab_type": "text"
      },
      "source": [
        "### prove merge sort is stable by sorting tuple and printing id"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "UwgdFdaRipEN",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def mergeTuple(l, r): \n",
        "  '''combine the left and right sorted list'''\n",
        "  ans = []\n",
        "  i = j = 0 # two pointers each points at l and r\n",
        "  n, m = len(l), len(r)\n",
        "  \n",
        "  # first while loop to merge\n",
        "  while i < n and j < m: \n",
        "    if l[i][0] <= r[j][0]: # chaning it to l[i][0] < r[j][0] will not be stable anymore. \n",
        "      ans.append(l[i])\n",
        "      i += 1\n",
        "    else:\n",
        "      ans.append(r[j])\n",
        "      j += 1\n",
        "      \n",
        "  # now one list of l and r might have items left\n",
        "  ans += l[i:]\n",
        "  ans += r[j:]\n",
        "  return ans\n",
        "\n",
        "def mergeSortTuple(a, s, e):\n",
        "  # base case , can not be divided further\n",
        "  if s == e:\n",
        "    return [a[s]]\n",
        "  # divide into two halves from the middle point\n",
        "  m = (s + e) // 2\n",
        "  \n",
        "  # conquer\n",
        "  l = mergeSort(a, s , m)\n",
        "  r = mergeSort(a, m+1, e)\n",
        "  \n",
        "  # combine\n",
        "  return mergeTuple(l, r)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "mm07Ac0-dO3A",
        "colab_type": "code",
        "outputId": "dd9eca57-98b7-4e04-acc2-7a31e7efd61d",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 312
        }
      },
      "source": [
        "a = [(9, 1), (10, 1), (2, 1), (8, 1), (9, 2), (3, 1), (7, 1), (9, 3)] # the second item represents the index of duplcates\n",
        "ids = [id(x) if x[0] == 9 else None for x in a]\n",
        "sorted_a = mergeSortTuple(a, 0, len(a)-1)\n",
        "ids2 = [id(x) if x[0] == 9 else None for x in sorted_a]\n",
        "print(sorted_a)\n",
        "ids, ids2"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[(2, 1), (3, 1), (7, 1), (8, 1), (9, 2), (9, 3), (9, 1), (10, 1)]\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "([140381548618120,\n",
              "  None,\n",
              "  None,\n",
              "  None,\n",
              "  140381548653128,\n",
              "  None,\n",
              "  None,\n",
              "  140381548653320],\n",
              " [None,\n",
              "  None,\n",
              "  None,\n",
              "  None,\n",
              "  140381548653128,\n",
              "  140381548653320,\n",
              "  140381548618120,\n",
              "  None])"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 47
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "h0QYWQaDxt9D",
        "colab_type": "text"
      },
      "source": [
        "## QuickSort in O(nlogn)"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "j4mW9xNrO6hm",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def partition(a, s, e):\n",
        "  p = a[e]\n",
        "  i = s - 1\n",
        "  # Scan unresticted area\n",
        "  for j in range(s, e): \n",
        "    # Swap \n",
        "    if a[j] <= p:\n",
        "      i += 1\n",
        "      a[i], a[j] = a[j], a[i] \n",
        "  a[i+1], a[e] = a[e], a[i+1]\n",
        "  return i+1"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "oTmEOjk2QQZV",
        "colab_type": "code",
        "outputId": "d8fe6f91-cfc0-42e9-c5af-f87ee5d7357b",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 54
        }
      },
      "source": [
        "# Experiment the correctness of lumutos partition\n",
        "lst = [9, 10, 2, 8, 9, 3, 7]\n",
        "print(partition(lst, 0, len(lst)-1))\n",
        "print(lst)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "2\n",
            "[2, 3, 7, 8, 9, 10, 9]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "v2_nP14pObAn",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# main algorithm of quick sort\n",
        "def quickSort(a, s, e, partition=partition):\n",
        "  # base case , can not be divided further\n",
        "  if s >= e:\n",
        "    return \n",
        "  p = partition(a, s, e)\n",
        "  \n",
        "  # conquer smaller problem\n",
        "  quickSort(a, s , p-1, partition)\n",
        "  quickSort(a, p+1, e, partition)\n",
        "  return"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ep4sVlJI7gNs",
        "colab_type": "code",
        "outputId": "ec1ca64d-ea4d-4c48-b2cc-cd57534b4228",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "quickSort(lst, 0, len(lst) - 1)\n",
        "lst"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[2, 3, 7, 8, 9, 9, 10]"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 4
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "UjMN8PWW7AVD",
        "colab_type": "text"
      },
      "source": [
        "### Quick Select"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "AUs3mt3o7DaF",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def quickSelect(a, s, e, k, partition=partition):\n",
        "  if s >= e:\n",
        "    return a[s]\n",
        "\n",
        "  p = partition(a, s, e) \n",
        "  if p == k:\n",
        "    return a[p]\n",
        "  if k > p:\n",
        "    return quickSelect(a, p+1, e, k, partition)\n",
        "  else:\n",
        "    return quickSelect(a, s, p-1,  k, partition)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "22m8CitD8747",
        "colab_type": "code",
        "outputId": "d697de6c-cff1-435a-e2cc-291f1f7305ea",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "lst = [9, 10, 2, 8, 9, 3, 7]\n",
        "quickSelect(lst, 0, len(lst) - 1, 2)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "7"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 7
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "8N4QPVcqouFf",
        "colab_type": "text"
      },
      "source": [
        "### experiment to see the stability of quick sort"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "oOHBweKDgiMw",
        "colab_type": "code",
        "outputId": "948493b2-40d4-4573-dffd-4dbfbba6f870",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "#a = [(5, 1), (7, 1),(3, 1), (2, 1), (5, 2), (6,1), (7, 2), (8, 1), (9, 1), (5, 3), (5, 4)] # the second item represents the index of duplcates\n",
        "a = [(2, 1), (2, 2), (1, 1)]\n",
        "def partition_tuple(a, s, e):\n",
        "  '''Lumutos partition'''\n",
        "  p = a[e][0]\n",
        "  i = s - 1\n",
        "  for j in range(s, e): #a[s, e-1]\n",
        "    \n",
        "    if a[j][0] <= p:\n",
        "      i += 1\n",
        "      a[i], a[j] = a[j], a[i] # swap a[i] and a[j]\n",
        "  a[i+1], a[e] = a[e], a[i+1]\n",
        "  return i+1\n",
        "quickSort(a, 0, len(a) - 1, partition_tuple)\n",
        "print(a)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[(1, 1), (2, 2), (2, 1)]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "QqcdUXaepGSa",
        "colab_type": "text"
      },
      "source": [
        "### experiment to see the performance of worst time"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "5n7nsw13pLWr",
        "colab_type": "code",
        "outputId": "736cf200-711d-4f42-b2b1-f5c369f70ce8",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 54
        }
      },
      "source": [
        "import random, time\n",
        "lst1 = [random.randint(1, 25) for i in range(400)]\n",
        "lst2 = [i for i in range(400)[::-1]]\n",
        "t1 = time.time()\n",
        "quickSort(lst1, 0, len(lst1)-1, partition)\n",
        "print('time for random values:', time.time()-t1)\n",
        "\n",
        "t1 = time.time()\n",
        "quickSort(lst2, 0, len(lst2)-1, partition)\n",
        "print('time for sorted values:', time.time()-t1)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "time for random values: 0.0017516613006591797\n",
            "time for sorted values: 0.0171658992767334\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "0y5x07wwo4Um",
        "colab_type": "text"
      },
      "source": [
        "### Hoare Partition"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "3vNUigFmo7ei",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# def partition_hoare(a, s, e):\n",
        "#   '''Hoare Parition'''\n",
        "#   p = a[e]\n",
        "#   i = s\n",
        "#   j = e-1\n",
        "#   while True:\n",
        "#     while a[i] <= p and i < j:\n",
        "#       i += 1\n",
        "#     while a[j] > p and i < j:\n",
        "#       j -= 1\n",
        "#     if i < j:\n",
        "#       a[i], a[j] = a[j], a[i]\n",
        "#     else:\n",
        "#       return j\n",
        "#   return j"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "GKbXRk4Czwjt",
        "colab_type": "code",
        "outputId": "be048173-9125-4716-89f0-17ad7fb0b345",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 54
        }
      },
      "source": [
        "# lst = [9, 10, 2, 8, 9, 3, 7]\n",
        "# print(partition_hoare(lst, 0, len(lst)-1))\n",
        "# print(lst)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "2\n",
            "[3, 2, 10, 8, 9, 9, 7]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "4EDqug7Yg2yl",
        "colab_type": "text"
      },
      "source": [
        "## HeapSort in O(nlogn)"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "0PE9BxQBg7lu",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "from heapq import heapify, heappop\n",
        "def heapsort(a):\n",
        "  heapify(a)\n",
        "  return [heappop(a) for i in range(len(a))]"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "PcUurYvkg_Px",
        "colab_type": "code",
        "outputId": "a96f214c-6fdb-4ed5-9c94-7e8772e65fb5",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "lst = [21, 1, 45, 78, 3, 5]\n",
        "heapsort(lst)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[1, 3, 5, 21, 45, 78]"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 2
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "XOkspIkgKots",
        "colab_type": "text"
      },
      "source": [
        "## Linear Sort"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "K1EUj-De16tk",
        "colab_type": "text"
      },
      "source": [
        "### Bucket Sort"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KR6BfJia-Nza",
        "colab_type": "code",
        "outputId": "6f52adca-30ab-4b13-e2db-f1231d6de755",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "# Prepare input data\n",
        "import numpy as np\n",
        "np.random.seed(1)\n",
        "a = np.random.uniform(0,  1, 10)\n",
        "a = np.round(a, decimals=2)\n",
        "a"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([0.42, 0.72, 0.  , 0.3 , 0.15, 0.09, 0.19, 0.35, 0.4 , 0.54])"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 9
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "3tI_x9WqBI0m",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "from functools import reduce\n",
        "def bucketSort(a):\n",
        "  n = len(a)\n",
        "  buckets = [[] for _ in range(n)]\n",
        "  # Divide numbers into buckets\n",
        "  for v in a:\n",
        "    buckets[int(v*n)].append(v)\n",
        "  print(buckets)\n",
        "  # Apply insertion sort within each bucket\n",
        "  for i in range(n):\n",
        "    insertionSort(buckets[i])\n",
        "  # Combine sorted buckets\n",
        "  return reduce(lambda a, b: a + b, buckets)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DZAfxnRNBVuG",
        "colab_type": "code",
        "outputId": "24aeffb1-1963-4848-c021-017fcdb800a7",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 54
        }
      },
      "source": [
        "bucketSort(a)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[[0.0, 0.09], [0.15, 0.19], [], [0.3, 0.35], [0.42, 0.4], [0.54], [], [0.72], [], []]\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[0.0, 0.09, 0.15, 0.19, 0.3, 0.35, 0.4, 0.42, 0.54, 0.72]"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 16
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "W-4vTjaf9cKN",
        "colab_type": "text"
      },
      "source": [
        "### Counting Sort"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "LrGlbYH59nZT",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "a1 = [1, 4, 0, 2, 7, 5, 9]\n",
        "a2 = [1, 4, 1, 2, 7, 5, 2]"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ptAUeFu8Kvrs",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def countSort(a):\n",
        "  minK, maxK = min(a), max(a)\n",
        "  k = maxK - minK + 1\n",
        "  count = [0] * (maxK - minK + 1)\n",
        "  n = len(a)\n",
        "  order = [0] * n\n",
        "  # Get occurrence\n",
        "  for key in a:\n",
        "    count[key - minK] += 1\n",
        "  \n",
        "  # Get prefix sum\n",
        "  for i in range(1, k):\n",
        "    count[i] += count[i-1]\n",
        "    \n",
        "  # Put key in position\n",
        "  for i in range(n-1, -1, -1):\n",
        "    key = a[i] - minK\n",
        "    count[key] -= 1 # to get the index as position\n",
        "    order[count[key]] = a[i] \n",
        "  return order"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "cvrX-2Co_AgO",
        "colab_type": "code",
        "outputId": "49b5ea36-34c9-481b-a539-7d7327878cfa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "countSort(a1)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[0, 1, 2, 4, 5, 7, 9]"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 3
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "sk5qIeoo_D6G",
        "colab_type": "code",
        "outputId": "e0b9bf82-685b-4087-b8a5-a9e7f8aa0388",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 90
        }
      },
      "source": [
        "countSort(a2)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[2, 2, 0, 1, 1, 0, 1]\n",
            "[2, 4, 4, 5, 6, 6, 7]\n",
            "[1, 1, 2, 2, 4, 5, 7]\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[1, 1, 2, 2, 4, 5, 7]"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 6
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "R85He0D050tZ",
        "colab_type": "text"
      },
      "source": [
        "### Radix Sort"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Ma4Sqj-KViqD",
        "colab_type": "code",
        "outputId": "87e16a22-de0c-407f-a30e-2b7181649892",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "# Get digits\n",
        "a = 178\n",
        "digits = []\n",
        "while a > 0:\n",
        "    digits.append(a%10)\n",
        "    a = a // 10\n",
        "digits"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[8, 7, 1]"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 46
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Jh65UuU4IeMj",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def count_sort(a, exp):\n",
        "  count = [0] * 10 # [0, 9]\n",
        "  n = len(a)\n",
        "  order = [0] * n\n",
        "  # Get occurrence\n",
        "  for key in a:\n",
        "    key = (key // exp) % 10\n",
        "    count[key] += 1\n",
        "  \n",
        "  # Get prefix sum\n",
        "  for i in range(1, 10):\n",
        "    count[i] += count[i-1]\n",
        "    \n",
        "  # Put key in position\n",
        "  for i in range(n-1, -1, -1):\n",
        "    key = (a[i] // exp) % 10\n",
        "    count[key] -= 1 # to get the index as position\n",
        "    order[count[key]] = a[i] \n",
        "  return order"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Mq1PxuWQ50HD",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "a = [170, 45, 75, 90, 802, 24]\n",
        "\n",
        "# LSD radix sortin\n",
        "def radixSort(a):\n",
        "  maxInt = max(a)\n",
        "  exp = 1\n",
        "  while maxInt // exp > 0:\n",
        "    a = count_sort(a, exp)\n",
        "    exp *= 10\n",
        "  return a"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "6mNsMh4rNXA8",
        "colab_type": "code",
        "outputId": "c14cefac-5007-49cc-9b98-1fba67be05f1",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "a = radixSort(a)\n",
        "a"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[24, 45, 75, 90, 170, 802]"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 45
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Rq82GJm5lHaH",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# MSD radix soring of strings with bucket sort\n",
        "def MSD_radix_string_sort(a, i):\n",
        "  '''\n",
        "  s : strings\n",
        "  i: starting radix for sorting\n",
        "  '''\n",
        "  # End condition: bucket has only one item\n",
        "  if len(a) <= 1:\n",
        "    return a\n",
        "\n",
        "  # Divide\n",
        "  buckets = [[] for _ in range(26)]\n",
        "  done_bucket = []\n",
        "  for s in a:\n",
        "    if i >= len(s):\n",
        "      done_bucket.append(s)\n",
        "    else:\n",
        "      buckets[ord(s[i]) - ord('a')].append(s)\n",
        "  # Conquer and chain all buckets\n",
        "  ans = []\n",
        "  for b in buckets:\n",
        "    ans += MSD_radix_string_sort(b, i + 1)\n",
        "  return done_bucket + ans"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tnHSSy6WzXPG",
        "colab_type": "code",
        "outputId": "a11f8ba2-c679-4169-827d-944d61002fe6",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "s = ['apple', 'pear', 'berry', 'peach', 'apricot', 'ap', 'pear']\n",
        "MSD_radix_string_sort(s, 0)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "['ap', 'apple', 'apricot', 'berry', 'peach', 'pear', 'pear']"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 53
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Q92n6NwiMInZ",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Experiment with Python sort"
      ],
      "execution_count": 0,
      "outputs": []
    }
  ]
}