All sorting techniques.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "iObvH3HyOcpU"
   },
   "source": [
    "# Bubble Sort "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "id": "QNnvPHkKOcpf",
    "outputId": "ac3126ce-1354-436d-e30c-015864414482"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 2, 2, 3, 4, 4, 4, 4, 4, 5, 5, 6, 6, 6, 6, 6, 7, 8, 8]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def bubble_sort(arr):\n",
    "    def swap(i, j):\n",
    "        arr[i], arr[j] = arr[j], arr[i]\n",
    "\n",
    "    n = len(arr)\n",
    "    swapped = True\n",
    "    \n",
    "    x = -1\n",
    "    while swapped:\n",
    "        swapped = False\n",
    "        x = x + 1\n",
    "        for i in range(1, n-x):\n",
    "            if arr[i - 1] > arr[i]:\n",
    "                swap(i - 1, i)\n",
    "                swapped = True\n",
    "                    \n",
    "    return arr\n",
    "ar=[6,8,4,6,2,4,7,6,8,5,2,4,6,2,5,4,6,3,4]\n",
    "z=bubble_sort(ar)\n",
    "z"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "eQmmIuluOcpi"
   },
   "source": [
    "# selection sort\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "Qr7oC7bWOcpi",
    "outputId": "4c2f5dad-d8bc-4ae6-d9f1-9ba84ea8ab87"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 2, 2, 4, 4, 4, 5, 5, 6, 6, 6, 6, 7, 8, 8]"
      ]
     },
     "execution_count": 25,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def selection_sort(arr):        \n",
    "    for i in range(len(arr)):\n",
    "        minimum = i\n",
    "        for j in range(i + 1, len(arr)):\n",
    "            if arr[j] < arr[minimum]:\n",
    "                minimum = j\n",
    "\n",
    "        arr[minimum], arr[i] = arr[i], arr[minimum]\n",
    "            \n",
    "    return arr\n",
    "ar=[6,8,4,6,2,4,7,6,8,5,2,4,6,2,5]\n",
    "z=selection_sort(ar)\n",
    "z"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "C8O4QWGrOcpj"
   },
   "source": [
    "# insertion sort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "XQ0Vp_i3Ocpk",
    "outputId": "54d84451-3dd8-48a7-e94a-9d65271e1f50"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 2, 2, 4, 4, 4, 5, 5, 6, 6, 6, 6, 7, 8, 8]"
      ]
     },
     "execution_count": 19,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def insersion_sort(arr, simulation=False):\n",
    "        \n",
    "    for i in range(len(arr)):\n",
    "        cursor = arr[i]\n",
    "        pos = i\n",
    "        \n",
    "        while pos > 0 and arr[pos - 1] > cursor:\n",
    "            # Swap the number down the list\n",
    "            arr[pos] = arr[pos - 1]\n",
    "            pos = pos - 1\n",
    "        # Break and do the final swap\n",
    "        arr[pos] = cursor\n",
    "\n",
    "    return arr\n",
    "ar=[6,8,4,6,2,4,7,6,8,5,2,4,6,2,5]\n",
    "z=insersion_sort(ar)\n",
    "z"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "1FenLqBgOcpk"
   },
   "source": [
    "# Merge sort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "AV_wieX4Ocpl",
    "outputId": "3bb99140-4717-4442-fcea-881436af4384"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 2, 2, 4, 4, 4, 5, 5, 6, 6, 6, 6, 7, 8, 8]"
      ]
     },
     "execution_count": 20,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def merge_sort(arr):\n",
    "    # The last array split\n",
    "    if len(arr) <= 1:\n",
    "        return arr\n",
    "    mid = len(arr) // 2\n",
    "    # Perform merge_sort recursively on both halves\n",
    "    left, right = merge_sort(arr[:mid]), merge_sort(arr[mid:])\n",
    "\n",
    "    # Merge each side together\n",
    "    return merge(left, right, arr.copy())\n",
    "\n",
    "\n",
    "def merge(left, right, merged):\n",
    "\n",
    "    left_cursor, right_cursor = 0, 0\n",
    "    while left_cursor < len(left) and right_cursor < len(right):\n",
    "      \n",
    "        # Sort each one and place into the result\n",
    "        if left[left_cursor] <= right[right_cursor]:\n",
    "            merged[left_cursor+right_cursor]=left[left_cursor]\n",
    "            left_cursor += 1\n",
    "        else:\n",
    "            merged[left_cursor + right_cursor] = right[right_cursor]\n",
    "            right_cursor += 1\n",
    "            \n",
    "    for left_cursor in range(left_cursor, len(left)):\n",
    "        merged[left_cursor + right_cursor] = left[left_cursor]\n",
    "        \n",
    "    for right_cursor in range(right_cursor, len(right)):\n",
    "        merged[left_cursor + right_cursor] = right[right_cursor]\n",
    "\n",
    "    return merged\n",
    "ar=[6,8,4,6,2,4,7,6,8,5,2,4,6,2,5]\n",
    "z=merge_sort(ar)\n",
    "z"
   ]
  }
 ],
 "metadata": {
  "colab": {
   "name": "All sorting techniques.ipynb",
   "provenance": []
  },
  "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": 1
}