searching_sorting.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": []
    },
    "kernelspec": {
      "display_name": "Python 3",
      "name": "python3"
    }
  },
  "cells": [
    {
      "cell_type": "code",
      "metadata": {
        "id": "jqVB3ib40scd"
      },
      "source": [
        "# Linear Searching\n",
        "# Binary\n",
        "\n",
        "# Sleep Sort\n",
        "# Monkey Sort\n",
        "# Bubble Sort\n",
        "# Selection\n",
        "# Merge Sort\n",
        "# Quick Sort\n",
        "# Insertion Sort"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Vcoqh6ob1dwG"
      },
      "source": [
        "# Linear Search\n",
        "\n",
        "# Brute Force\n",
        "\n",
        "def linear_search(arr,item):\n",
        "\n",
        "  for i in range(len(arr)):\n",
        "\n",
        "    if arr[i] == item:\n",
        "      return i\n",
        "\n",
        "  return -1"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "0gIHvKcb151X",
        "outputId": "791af712-4de4-492c-f43c-037292fcae74"
      },
      "source": [
        "arr = [12,34,56,1,67,100,47,99]\n",
        "\n",
        "linear_search(arr,121)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "-1"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 6
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8aFnf5s42GKE"
      },
      "source": [
        "# Time Complexity is O(N)\n",
        "# No sorting required"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "m1_ZWchm2dRL"
      },
      "source": [
        "# Binary Search\n",
        "\n",
        "# Sorted Array \n",
        "\n",
        "def binary_search(arr, low, high, item):\n",
        "\n",
        "  #print(\"low = \",low,\"high = \",high,end=' ')\n",
        "\n",
        "  if low <= high:\n",
        "    # search\n",
        "\n",
        "    mid = (low + high)//2\n",
        "\n",
        "    #print(\"mid value is\",arr[mid])\n",
        "\n",
        "    if arr[mid] == item:\n",
        "      return mid\n",
        "    elif arr[mid] > item:\n",
        "      return binary_search(arr, low, mid-1,item)\n",
        "    else:\n",
        "      return binary_search(arr,mid+1,high,item)\n",
        "  else:\n",
        "    return -1"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "TIHQdlLE4HOJ",
        "outputId": "29799497-bc89-4e41-a43d-f3b8754eef91"
      },
      "source": [
        "arr = [12,24,35,46,57,68,80,99,100]\n",
        "print(binary_search(arr,0,len(arr)-1,-5))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "-1\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "y2akKfUq4YQR"
      },
      "source": [
        "# Sorting\n",
        "\n",
        "def is_sorted(arr):\n",
        "\n",
        "  sorted = True\n",
        "\n",
        "  for i in range(len(arr) - 1):\n",
        "    if arr[i]>arr[i+1]:\n",
        "      sorted = False\n",
        "  \n",
        "  return sorted"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Q7ZlBwxY6lnF",
        "outputId": "9dddc45f-9416-4415-c8b5-fa2f6d911af6"
      },
      "source": [
        "arr = [1,2,3,4,8,6]\n",
        "is_sorted(arr)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "False"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 21
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "OQBwGjVO6r4I",
        "outputId": "d4b88293-8270-4134-ac03-5218c969f72e"
      },
      "source": [
        "# Monkey sort\n",
        "\n",
        "import random\n",
        "a=[1,2,3,4]\n",
        "random.shuffle(a)\n",
        "a"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[2, 1, 3, 4]"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 25
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "1w7aQ4DO7C6U"
      },
      "source": [
        "import time\n",
        "def monkey_sort(arr):\n",
        "\n",
        "  while not is_sorted(arr):\n",
        "    time.sleep(1)\n",
        "    random.shuffle(arr)\n",
        "    print(arr)\n",
        "  print(arr)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Br5OepXe7aXN",
        "outputId": "8a692cf7-d03e-49d8-c406-eb90a27e0c38"
      },
      "source": [
        "a = [12,24,11,56,34,20]\n",
        "monkey_sort(a)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[24, 20, 11, 56, 12, 34]\n",
            "[11, 34, 12, 56, 20, 24]\n",
            "[20, 11, 24, 12, 34, 56]\n",
            "[24, 20, 34, 56, 11, 12]\n",
            "[56, 34, 12, 20, 11, 24]\n",
            "[34, 12, 11, 20, 56, 24]\n",
            "[56, 34, 20, 12, 11, 24]\n",
            "[11, 20, 34, 56, 24, 12]\n",
            "[24, 12, 11, 34, 56, 20]\n",
            "[20, 56, 11, 24, 34, 12]\n",
            "[56, 12, 24, 20, 11, 34]\n",
            "[56, 20, 24, 34, 11, 12]\n",
            "[56, 20, 24, 11, 34, 12]\n",
            "[56, 12, 24, 20, 34, 11]\n",
            "[11, 12, 20, 24, 34, 56]\n",
            "[11, 12, 20, 24, 34, 56]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lIqq4fMp7f75"
      },
      "source": [
        "12 24 45 5 16"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gsiRM1N_85ty"
      },
      "source": [
        "5 12 16 24 45"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "u_lW50sxGJiZ"
      },
      "source": [
        "def bubble_sort(arr):\n",
        "\n",
        "  for i in range(len(arr) - 1):\n",
        "    flag = 0\n",
        "    for j in range(len(arr) - 1 - i):\n",
        "      if arr[j] > arr[j+1]:\n",
        "        arr[j],arr[j+1] = arr[j+1],arr[j]\n",
        "        flag =1\n",
        "\n",
        "    if flag == 0:\n",
        "      break\n",
        "  \n",
        "  return arr"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "oj6D4lmLHCNV",
        "outputId": "08223624-9edb-48ef-e014-76add5913fd5"
      },
      "source": [
        "arr = [23,12,34,11,100,56,78]\n",
        "bubble_sort(arr)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[11, 12, 23, 34, 56, 78, 100]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "dVWdsgFfHFie"
      },
      "source": [
        "def selection_sort(arr):\n",
        "\n",
        "  for i in range(len(arr) - 1):\n",
        "\n",
        "    min = i\n",
        "\n",
        "    for j in range(i+1,len(arr)):\n",
        "      if arr[j] < arr[min]:\n",
        "        min = j\n",
        "    \n",
        "    arr[i],arr[min] = arr[min],arr[i]\n",
        "\n",
        "  return arr\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "JB_zTL3-isvI",
        "outputId": "666a6e7d-5782-48f4-ba0a-e81f09c766fb"
      },
      "source": [
        "arr = [23,12,34,11,100,56,78]\n",
        "selection_sort(arr)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "1 pass Current min is 23\n",
            "Current item under observation 12\n",
            "Current item is less than min\n",
            "Now the min has become 12\n",
            "Current item under observation 34\n",
            "Current item under observation 11\n",
            "Current item is less than min\n",
            "Now the min has become 11\n",
            "Current item under observation 100\n",
            "Current item under observation 56\n",
            "Current item under observation 78\n",
            "[11, 12, 34, 23, 100, 56, 78]\n",
            "**************************************************\n",
            "2 pass Current min is 12\n",
            "Current item under observation 34\n",
            "Current item under observation 23\n",
            "Current item under observation 100\n",
            "Current item under observation 56\n",
            "Current item under observation 78\n",
            "[11, 12, 34, 23, 100, 56, 78]\n",
            "**************************************************\n",
            "3 pass Current min is 34\n",
            "Current item under observation 23\n",
            "Current item is less than min\n",
            "Now the min has become 23\n",
            "Current item under observation 100\n",
            "Current item under observation 56\n",
            "Current item under observation 78\n",
            "[11, 12, 23, 34, 100, 56, 78]\n",
            "**************************************************\n",
            "4 pass Current min is 34\n",
            "Current item under observation 100\n",
            "Current item under observation 56\n",
            "Current item under observation 78\n",
            "[11, 12, 23, 34, 100, 56, 78]\n",
            "**************************************************\n",
            "5 pass Current min is 100\n",
            "Current item under observation 56\n",
            "Current item is less than min\n",
            "Now the min has become 56\n",
            "Current item under observation 78\n",
            "[11, 12, 23, 34, 56, 100, 78]\n",
            "**************************************************\n",
            "6 pass Current min is 100\n",
            "Current item under observation 78\n",
            "Current item is less than min\n",
            "Now the min has become 78\n",
            "[11, 12, 23, 34, 56, 78, 100]\n",
            "**************************************************\n",
            "[11, 12, 23, 34, 56, 78, 100]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "UQ0IoyZEi1wd"
      },
      "source": [
        "L = []\n",
        "\n",
        "import random\n",
        "\n",
        "for i in range(10000):\n",
        "  L.append(random.randint(1,10000))"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Q4gXj1bwk48c",
        "outputId": "149a726d-3bd1-40e1-a9b9-ed86862a97fa"
      },
      "source": [
        "len(L)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "10000"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 12
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "WbkyZJ1qk7Ds"
      },
      "source": [
        "L1 = L[:]\n",
        "# cloning"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "oatQ31jPk_m1",
        "outputId": "eb6d0c35-ff33-4f98-e571-c2115e4e019e"
      },
      "source": [
        "import time\n",
        "\n",
        "start = time.time()\n",
        "bubble_sort(L)\n",
        "print(\"Time taken\",time.time() - start,\"secs\")"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Time taken 0.0018186569213867188 secs\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "QzXY_fzLlQ9O",
        "outputId": "c0fca59b-d6f1-43f2-9060-d74d62979133"
      },
      "source": [
        "start = time.time()\n",
        "selection_sort(L1)\n",
        "print(\"Time taken\",time.time() - start,\"secs\")\n",
        "\n",
        "# Not Adaptive"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Time taken 3.4115519523620605 secs\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iJ2Xbh4llbJc"
      },
      "source": [
        "# Merge Sort"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "e5Skvkui0uVx"
      },
      "source": [
        "def merge_arrays(arr1,arr2):\n",
        "\n",
        "  i = 0\n",
        "  j = 0\n",
        "\n",
        "  new_arr = []\n",
        "\n",
        "  while i<len(arr1) and j<len(arr2):\n",
        "    if arr1[i] < arr2[j]:\n",
        "      new_arr.append(arr1[i])\n",
        "      i+=1\n",
        "    else:\n",
        "      new_arr.append(arr2[j])\n",
        "      j+=1\n",
        "\n",
        "  while i < len(arr1):\n",
        "    new_arr.append(arr1[i])\n",
        "    i+=1\n",
        "\n",
        "  while j < len(arr2):\n",
        "    new_arr.append(arr2[j])\n",
        "    j+=1\n",
        "\n",
        "  return new_arr\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vNVtnItS15Lx"
      },
      "source": [
        "arr1 = [1,2,6,7,8]\n",
        "arr2 = [2,3,5]"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "anf9XYwl1-Y7",
        "outputId": "b6d15ec9-7358-4a02-a703-46e1c25e3e15"
      },
      "source": [
        "merge_arrays(arr1,arr2)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[1, 2, 2, 3, 5, 6, 7, 8]"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 8
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "background_save": true
        },
        "id": "LVpNBTZM2BpS"
      },
      "source": [
        "def merge_sort(arr):\n",
        "\n",
        "  mid = len(arr)//2\n",
        "\n",
        "  left = arr[:mid]\n",
        "  right = arr[mid:]\n",
        "\n",
        "  if len(left) == 1 and len(right) == 1:\n",
        "    return merge_arrays(left,right)\n",
        "  else:\n",
        "    merge_sort(left)\n",
        "    merge_sort(right)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "hqp_mRbS3_Ei",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 132
        },
        "outputId": "6f0efb72-dbff-4b4b-fdd0-828f22168af6"
      },
      "source": [
        "[2,5,1,6,4,7,9,0]\n",
        "left = [2,5,1,6]\n",
        "right = [4,7,9,0]\n",
        "\n",
        "merge sort on left\n",
        "left1 = [2,5]\n",
        "right1 = [1,6]\n",
        "\n",
        "merge on left1\n",
        "left2 = [2]\n",
        "right2 = [5]\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "error",
          "ename": "SyntaxError",
          "evalue": "ignored",
          "traceback": [
            "\u001b[0;36m  File \u001b[0;32m\"<ipython-input-1-58c9a36702c2>\"\u001b[0;36m, line \u001b[0;32m5\u001b[0m\n\u001b[0;31m    merge sort on left\u001b[0m\n\u001b[0m             ^\u001b[0m\n\u001b[0;31mSyntaxError\u001b[0m\u001b[0;31m:\u001b[0m invalid syntax\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "4UzPu-WZxpTQ"
      },
      "source": [
        "def quick_sort(arr):\n",
        "\n",
        "  if len(arr) <= 1:\n",
        "    return arr\n",
        "\n",
        "  pivot = arr.pop()\n",
        "\n",
        "  items_left = []\n",
        "  items_right = []\n",
        "\n",
        "  for item in arr:\n",
        "    if item < pivot:\n",
        "      items_left.append(item)\n",
        "    else:\n",
        "      items_right.append(item)\n",
        "\n",
        "  return quick_sort(items_left) + [pivot] + quick_sort(items_right)\n",
        "\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "yBKRs3a_yUq2",
        "outputId": "f284aa5a-0e81-416a-ae65-c5b01ae5dacf"
      },
      "source": [
        "arr = [2,1,4,6,3,7,5]\n",
        "quick_sort(arr)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[1, 2, 3, 4, 5, 6, 7]"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 8
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "PNf7neZ1yZ1s"
      },
      "source": [
        "def quick_sort(arr,low,high):\n",
        "\n",
        "  if len(arr) == 1:\n",
        "    return arr\n",
        "\n",
        "  if low < high:\n",
        "\n",
        "    pi = partition(arr,low,high)\n",
        "\n",
        "    quick_sort(arr,low,pi-1)\n",
        "    quick_sort(arr,pi+1,high)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "RqlGnvbu4t2b"
      },
      "source": [
        "def partition(arr,low,high):\n",
        "\n",
        "  i = low - 1\n",
        "  pivot = arr[high]\n",
        "\n",
        "  for j in range(low,high):\n",
        "\n",
        "    if arr[j] <= pivot:\n",
        "      i+=1\n",
        "      arr[i],arr[j] = arr[j],arr[i]\n",
        "  arr[i+1],arr[high] = arr[high],arr[i+1]\n",
        "\n",
        "  return i+1"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "6k7ip8Fm5fx7",
        "outputId": "f29344d4-f23d-41fa-e6c9-44f895de6b55"
      },
      "source": [
        "arr = [10, 7, 8, 9, 1, 5] \n",
        "n = len(arr) \n",
        "quick_sort(arr, 0, n-1)\n",
        "print(arr)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[1, 5, 7, 8, 9, 10]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Lf1z0WWC56wz"
      },
      "source": [],
      "execution_count": null,
      "outputs": []
    }
  ]
}