Sorting Algorithms (insertion Sort, Merge Sort, Min Heap, Bucket Sort, Fractional Knapsack) using Python code.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# insertionSort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " 2\n",
      " 5\n",
      " 6\n",
      " 11\n",
      " 12\n",
      " 13\n"
     ]
    }
   ],
   "source": [
    "#insertionSort using function\n",
    "\n",
    "def insertionSort(arr):\n",
    " \n",
    "    # Traverse through 1 to len(arr)\n",
    "    for i in range(1, len(arr)):\n",
    " \n",
    "        key = arr[i]\n",
    " \n",
    "        # Move elements of arr[0..i-1], that are\n",
    "        # greater than key, to one position ahead\n",
    "        # of their current position\n",
    "        j = i-1\n",
    "        while j >= 0 and key < arr[j] :\n",
    "                arr[j + 1] = arr[j]\n",
    "                j -= 1\n",
    "        arr[j + 1] = key\n",
    " \n",
    " \n",
    "# Driver code to test above\n",
    "arr = [2,12, 11, 13, 5, 6]\n",
    "insertionSort(arr)\n",
    "for i in range(len(arr)):\n",
    "    print (\"% d\" % arr[i])\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 5, 6, 11, 12, 13]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Original Data:\n",
      "[64, 99, 64, 25, 12, 10, 22, 11]\n",
      "\n",
      "Sorted Data:\n",
      "[10, 11, 12, 22, 25, 64, 64, 99]\n"
     ]
    }
   ],
   "source": [
    "#insertionSort\n",
    "\n",
    "A = [64,99,64,25,12,10,22,11]\n",
    "print (\"Original Data:\")\n",
    "print(A)\n",
    "for i in range(1, len(A)):\n",
    "    key = A[i]\n",
    "    j = i-1\n",
    "    while j >= 0 and key < A[j] :\n",
    "        A[j + 1] = A[j]\n",
    "        j -= 1\n",
    "    A[j + 1] = key\n",
    "\n",
    "print (\"\\nSorted Data:\")    \n",
    "print(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Enter size of the list:\t3\n",
      "Enter the data: \t2\n",
      "Enter the data: \t1\n",
      "Enter the data: \t9\n",
      "Original Data:\n",
      "[2, 1, 9]\n",
      "\n",
      "Sorted Data:\n",
      "[1, 2, 9]\n"
     ]
    }
   ],
   "source": [
    "#insertionSort using user input\n",
    "\n",
    "A = []\n",
    "size = int(input(\"\\nEnter size of the list:\\t\"))\n",
    "for i in range(size):\n",
    "    data = int(input(\"Enter the data: \\t\"))\n",
    "    A.append(data)\n",
    "    \n",
    "print (\"Original Data:\")\n",
    "print(A)\n",
    "    \n",
    "for i in range(1, len(A)):\n",
    "    key = A[i]\n",
    "    j = i-1\n",
    "    while j >= 0 and key < A[j] :\n",
    "        A[j + 1] = A[j]\n",
    "        j -= 1\n",
    "    A[j + 1] = key\n",
    "\n",
    "print (\"\\nSorted Data:\")    \n",
    "print(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Merge Sort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Given array is: \n",
      "9 5 2 7 6 1 8 4 \n",
      "[9]\n",
      "[5]\n",
      "[2]\n",
      "[7]\n",
      "[5, 9]\n",
      "[2, 7]\n",
      "[6]\n",
      "[1]\n",
      "[8]\n",
      "[4]\n",
      "[1, 6]\n",
      "[4, 8]\n",
      "[2, 5, 7, 9]\n",
      "[1, 4, 6, 8]\n",
      "Sorted array is: \n",
      "1 2 4 5 6 7 8 9 \n"
     ]
    }
   ],
   "source": [
    "def merge(arr):\n",
    "    if len(arr) > 1:\n",
    "        mid = len(arr)//2\n",
    "        L = arr[:mid]\n",
    "        R = arr[mid:]\n",
    "        merge(L)\n",
    "        merge(R)\n",
    "        i = j = k = 0\n",
    "        while i < len(L) and j < len(R):\n",
    "            if L[i] < R[j]:\n",
    "                arr[k] = L[i]\n",
    "                i += 1\n",
    "            else:\n",
    "                arr[k] = R[j]\n",
    "                j += 1\n",
    "            k += 1\n",
    "        while i < len(L):\n",
    "            arr[k] = L[i]\n",
    "            i += 1\n",
    "            k += 1\n",
    "        while j < len(R):\n",
    "            arr[k] = R[j]\n",
    "            j += 1\n",
    "            k += 1\n",
    "        print(L)\n",
    "        print(R)\n",
    "def printList(arr):\n",
    "    for i in range(len(arr)):\n",
    "        print(arr[i], end=\" \")\n",
    "    print()\n",
    "if __name__ == '__main__':\n",
    "    arr = [9,5,2,7,6,1,8,4]\n",
    "    print(\"Given array is: \")\n",
    "    printList(arr)\n",
    "    merge(arr)\n",
    "    print(\"Sorted array is: \")\n",
    "    printList(arr)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Min Heap"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Given array is \n",
      "[10, 4, 6, 3, 2, 9, 1, 5]\n",
      "Sorted array is \n",
      "10 9 6 5 4 3 2 1 \n"
     ]
    }
   ],
   "source": [
    "def heapify(arr, n, i):\n",
    "    smallest = i \n",
    "    l = 2 * i + 1\n",
    "    r = 2 * i + 2 \n",
    "    if l < n and arr[l] < arr[smallest]: \n",
    "        smallest = l \n",
    "\n",
    "    if r < n and arr[r] < arr[smallest]: \n",
    "        smallest = r \n",
    "\n",
    "    if smallest != i: \n",
    "        (arr[i],arr[smallest]) = (arr[smallest],arr[i])\n",
    "\n",
    "        heapify(arr, n, smallest)\n",
    "\n",
    "def heapSort(arr, n):\n",
    "\n",
    "    for i in range(int(n / 2) - 1,-1,-1):\n",
    "        heapify(arr, n, i) \n",
    "\n",
    "    for i in range(n-1, -1, -1):\n",
    "\n",
    "        arr[0], arr[i] = arr[i], arr[0]\n",
    "\n",
    "        heapify(arr, i, 0)\n",
    "\n",
    "def printArray(arr, n):\n",
    "      \n",
    "    for i in range(n):\n",
    "        print(arr[i], end = \" \") \n",
    "    print()\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    arr = [10,4, 6, 3, 2, 9,1 ,5] \n",
    "    n = len(arr) \n",
    "    print(\"Given array is \")\n",
    "    print(arr)\n",
    "    heapSort(arr, n) \n",
    "  \n",
    "    print(\"Sorted array is \") \n",
    "    printArray(arr, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Bucket Sort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Sorted data is\n",
      "[0.21, 0.27, 0.3, 0.47, 0.51, 0.54, 0.6, 0.88, 0.91, 0.99]\n"
     ]
    }
   ],
   "source": [
    "def bucketSort(data):\n",
    "    bucket = []\n",
    "    for i in range(len(data)):\n",
    "        bucket.append([])\n",
    "\n",
    "    for j in data:\n",
    "        index_b = int(10 * j)\n",
    "        bucket[index_b].append(j)\n",
    "\n",
    "    for i in range(len(data)):\n",
    "        bucket[i] = sorted(bucket[i])\n",
    "    k = 0\n",
    "    for i in range(len(data)):\n",
    "        for j in range(len(bucket[i])):\n",
    "            data[k] = bucket[i][j]\n",
    "            k += 1\n",
    "    return data\n",
    "\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    \n",
    "    data = [.91, .21, .30, .54, .60,.88, .99, .27, .47, .51]\n",
    "    print(\"Sorted data is\")\n",
    "    BKsort=bucketSort(data)\n",
    "    print(BKsort)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Fractional Knapsack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Maximum value in Knapsack = 65.0\n"
     ]
    }
   ],
   "source": [
    " class ItemValue:\n",
    " \n",
    "    def __init__(self, wt, val, ind):\n",
    "        self.wt = wt\n",
    "        self.val = val\n",
    "        self.ind = ind\n",
    "        self.cost = val // wt\n",
    " \n",
    "    def __lt__(self, other):\n",
    "        return self.cost < other.cost\n",
    "    \n",
    "class FractionalKnapSack:\n",
    "\n",
    "    def getMaxValue(wt, val, capacity):\n",
    "\n",
    "        iVal = []\n",
    "        for i in range(len(wt)):\n",
    "            iVal.append(ItemValue(wt[i], val[i], i))\n",
    "        iVal.sort(reverse=True)\n",
    "        totalValue = 0\n",
    "        for i in iVal:\n",
    "            curWt = int(i.wt)\n",
    "            curVal = int(i.val)\n",
    "            if capacity - curWt >= 0:\n",
    "                capacity -= curWt\n",
    "                totalValue += curVal\n",
    "            else:\n",
    "                fraction = capacity / curWt\n",
    "                totalValue += curVal * fraction\n",
    "                capacity = int(capacity - (curWt * fraction))\n",
    "                break\n",
    "        return totalValue\n",
    " \n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    wt = [3,2,1,4,5]\n",
    "    val = [25,20,15,40,50]\n",
    "    capacity = 6\n",
    " \n",
    "\n",
    "    maxValue = FractionalKnapSack.getMaxValue(wt, val, capacity)\n",
    "    print(\"Maximum value in Knapsack =\", maxValue)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Item_weight 1 Item_value 15 capacity 6 Value 15\n",
      "Item_weight 2 Item_value 20 capacity 4 Value 35\n",
      "Item_weight 4 Item_value 40 capacity 0 Value 75\n",
      "Maximum value in Knapsack = 75.0\n"
     ]
    }
   ],
   "source": [
    "\n",
    "class ItemValue:\n",
    " \n",
    "    def __init__(self, wt, val, ind):\n",
    "        self.wt = wt\n",
    "        self.val = val\n",
    "        self.ind = ind\n",
    "        self.cost = val // wt\n",
    " \n",
    "    def __lt__(self, other):\n",
    "        return self.cost < other.cost\n",
    "    \n",
    "class FractionalKnapSack:\n",
    "\n",
    "    def getMaxValue(wt, val, capacity):\n",
    "\n",
    "        iVal = []\n",
    "        for i in range(len(wt)):\n",
    "            iVal.append(ItemValue(wt[i], val[i], i))\n",
    "            \n",
    "        iVal.sort(reverse=True)\n",
    "        totalValue = 0\n",
    "        for i in iVal:\n",
    "            curWt = int(i.wt)\n",
    "            curVal = int(i.val)\n",
    "            if capacity - curWt >= 0:\n",
    "                capacity -= curWt\n",
    "                totalValue += curVal\n",
    "                print('Item_weight', curWt,'Item_value',curVal,'capacity', capacity,'Value',totalValue)\n",
    "\n",
    "            else:\n",
    "                fraction = capacity / curWt\n",
    "                totalValue += curVal * fraction\n",
    "                capacity = int(capacity - (curWt * fraction))\n",
    "               # print('Item_weight', curWt,'Item_value',curVal,'capacity', capacity,'Value',totalValue)\n",
    "                break\n",
    "\n",
    "                    \n",
    "        return totalValue\n",
    " \n",
    "if __name__ == \"__main__\":\n",
    "    wt = [3,2,1,4,5]\n",
    "    val = [25,20,15,40,50]\n",
    "    capacity = 7\n",
    "    maxValue = FractionalKnapSack.getMaxValue(wt, val, capacity)\n",
    "    #print(\"Weight: \", wt,\"\\nvalue: \",val)\n",
    "    print(\"Maximum value in Knapsack =\", maxValue)\n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}