Chapter03/Chapter_3_ALL_CODE.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Swap Function in Python"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "var1 = 1\n",
    "var2 = 2\n",
    "var1,var2 = var2,var1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(var1,var2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "list = [25,21,22,24,23,27,26]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# SORTING ALGORITHMS"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Pass 1 of Bubble Sort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 [2, 6, 11, 9, 7, 31, 45, 12]\n",
      "1 [2, 6, 11, 9, 7, 31, 45, 12]\n",
      "2 [2, 6, 11, 9, 7, 31, 45, 12]\n",
      "3 [2, 6, 9, 11, 7, 31, 45, 12]\n",
      "4 [2, 6, 9, 7, 11, 31, 45, 12]\n",
      "5 [2, 6, 9, 7, 11, 31, 45, 12]\n",
      "6 [2, 6, 9, 7, 11, 31, 45, 12]\n",
      "7 [2, 6, 9, 7, 11, 31, 12, 45]\n"
     ]
    }
   ],
   "source": [
    "lastElementIndex = len(list)-1\n",
    "print(0,list)\n",
    "for idx in range(lastElementIndex):\n",
    "                if list[idx]>list[idx+1]:\n",
    "                    list[idx],list[idx+1]=list[idx+1],list[idx]\n",
    "                print(idx+1,list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Bubble Sort Algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def BubbleSort(list):\n",
    "# Excahnge the elements to arrange in order\n",
    "    lastElementIndex = len(list)-1\n",
    "    for passNo in range(lastElementIndex,0,-1):\n",
    "        for idx in range(passNo):\n",
    "            if list[idx]>list[idx+1]:\n",
    "                list[idx],list[idx+1]=list[idx+1],list[idx]\n",
    "    return list\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "list = [25,21,22,24,23,27,26]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "BubbleSort(list)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Insertion Sort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def InsertionSort(list):\n",
    "    for i in range(1, len(list)):\n",
    "        j = i-1\n",
    "        next = list[i]\n",
    "# Compare the current element with next one\n",
    "    \n",
    "        while (list[j] > next) and (j >= 0):\n",
    "            list[j+1] = list[j]\n",
    "            j=j-1\n",
    "        list[j+1] = next\n",
    "    return list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "InsertionSort(list)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Shell Sort Algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def ShellSort(list):\n",
    "    distance = len(list) // 2\n",
    "    while distance > 0:\n",
    "        for i in range(distance, len(list)):\n",
    "            temp = list[i]\n",
    "            j = i\n",
    "# Sort the sub list for this distance\n",
    "            while j >= distance and list[j - distance] > temp:\n",
    "                list[j] = list[j - distance]\n",
    "                j = j-distance\n",
    "            list[j] = temp\n",
    "# Reduce the distance for the next element\n",
    "        distance = distance//2\n",
    "    return list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "list = [19,2,31,45,30,11,121,27]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ShellSort(list)\n",
    "print(list)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Merge Sort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def MergeSort(list):\n",
    "    if len(list)>1:\n",
    "        mid = len(list)//2 #splits list in half\n",
    "        left = list[:mid]\n",
    "        right = list[mid:]\n",
    "\n",
    "        MergeSort(left) #repeats until length of each list is 1\n",
    "        MergeSort(right)\n",
    "\n",
    "        a = 0\n",
    "        b = 0\n",
    "        c = 0\n",
    "        while a < len(left) and b < len(right):\n",
    "            if left[a] < right[b]:\n",
    "                list[c]=left[a]\n",
    "                a = a + 1\n",
    "            else:\n",
    "                list[c]=right[b]\n",
    "                b = b + 1\n",
    "            c = c + 1\n",
    "        while a < len(left):\n",
    "            list[c]=left[a]\n",
    "            a = a + 1\n",
    "            c = c + 1\n",
    "\n",
    "        while b < len(right):\n",
    "            list[c]=right[b]\n",
    "            b = b + 1\n",
    "            c = c + 1\n",
    "    return list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[7, 10, 16, 21, 34, 44, 45, 67, 83]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list = [44,16,83,7,67,21,34,45,10]\n",
    "MergeSort(list)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Selection Sort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def SelectionSort(list):\n",
    "    for fill_slot in range(len(list) - 1, 0, -1):\n",
    "        max_index = 0\n",
    "        for location in range(1, fill_slot + 1):\n",
    "            if list[location] > list[max_index]:\n",
    "                max_index = location\n",
    "        list[fill_slot],list[max_index] = list[max_index],list[fill_slot]\n",
    "    return list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "list = [70,15,25,19,34,44]\n",
    "SelectionSort(list)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# SEARCHING ALGORITHMS"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Linear Search"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def LinearSearch(list, item):\n",
    "    index = 0\n",
    "    found = False\n",
    "\n",
    "# Match the value with each data element       \n",
    "    while index < len(list) and found is False:\n",
    "        if list[index] == item:\n",
    "            found = True\n",
    "        else:\n",
    "            index = index + 1\n",
    "    return found"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "list = [12, 33, 11, 99, 22, 55, 90]\n",
    "print(LinearSearch(list, 12))\n",
    "print(LinearSearch(list, 91))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Binary Search"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def BinarySearch(list, item):\n",
    "    first = 0\n",
    "    last = len(list)-1\n",
    "    found = False\n",
    "\n",
    "    while first<=last and not found:\n",
    "        midpoint = (first + last)//2\n",
    "        if list[midpoint] == item:\n",
    "            found = True\n",
    "        else:\n",
    "            if item < list[midpoint]:\n",
    "                last = midpoint-1\n",
    "            else:\n",
    "                first = midpoint+1\n",
    "    return found"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "list = [12, 33, 11, 99, 22, 55, 90]\n",
    "sorted_list = BubbleSort(list)\n",
    "print(BinarySearch(list, 12))\n",
    "print(BinarySearch(list, 91))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Intpolation Search"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def IntPolsearch(list,x ):\n",
    "    idx0 = 0\n",
    "    idxn = (len(list) - 1)\n",
    "    found = False\n",
    "    while idx0 <= idxn and x >= list[idx0] and x <= list[idxn]:\n",
    "\n",
    "# Find the mid point\n",
    "        mid = idx0 +int(((float(idxn - idx0)/( list[idxn] - list[idx0])) * ( x - list[idx0])))\n",
    "\n",
    "# Compare the value at mid point with search value \n",
    "        if list[mid] == x:\n",
    "            found = True\n",
    "            return found\n",
    "\n",
    "        if list[mid] < x:\n",
    "            idx0 = mid + 1\n",
    "    return found"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "list = [12, 33, 11, 99, 22, 55, 90]\n",
    "sorted_list = BubbleSort(list)\n",
    "print(IntPolsearch(list, 12))\n",
    "print(IntPolsearch(list,91))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Depth First Search"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def dfs(aGraph, root): \n",
    "    stack = [root] \n",
    "    parents = {root: root} \n",
    "    path = list \n",
    "    while stack: \n",
    "        print ('Stack is: %s' % stack) \n",
    "        vertex = stack.pop(-1) \n",
    "        print ('Working on %s' % vertex) \n",
    "        for element in aGraph[vertex]: \n",
    "            if element not in parents: \n",
    "                parents[element] = vertex \n",
    "                stack.append(element)\n",
    "                print ('Now, adding %s to the stack' % element) \n",
    "                path.append(parents[vertex]+'>'+vertex) \n",
    "    return path[1:] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "g = dict() \n",
    "g['Amine'] = ['Wassim', 'Nick', 'Mike','Elena'] \n",
    "g['Wassim'] = ['Amine', 'Imran'] \n",
    "g['Nick'] = ['Amine'] \n",
    "g['Mike'] = ['Amine', 'Mary'] \n",
    "g['Elena'] = ['Amine'] \n",
    "g['Imran'] = ['Wassim', 'Steven'] \n",
    "g['Mary'] = ['Mike']\n",
    "g['Steven'] = ['Imran']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Stack is: ['Amine']\n",
      "Working on Amine\n",
      "Now, adding Wassim to the stack\n",
      "Now, adding Nick to the stack\n",
      "Now, adding Mike to the stack\n",
      "Now, adding Elena to the stack\n",
      "Stack is: ['Wassim', 'Nick', 'Mike', 'Elena']\n",
      "Working on Elena\n",
      "Stack is: ['Wassim', 'Nick', 'Mike']\n",
      "Working on Mike\n",
      "Now, adding Mary to the stack\n",
      "Stack is: ['Wassim', 'Nick', 'Mary']\n",
      "Working on Mary\n",
      "Stack is: ['Wassim', 'Nick']\n",
      "Working on Nick\n",
      "Stack is: ['Wassim']\n",
      "Working on Wassim\n",
      "Now, adding Imran to the stack\n",
      "Stack is: ['Imran']\n",
      "Working on Imran\n",
      "Now, adding Steven to the stack\n",
      "Stack is: ['Steven']\n",
      "Working on Steven\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "['Amine>Amine',\n",
       " 'Amine>Amine',\n",
       " 'Amine>Amine',\n",
       " 'Amine>Mike',\n",
       " 'Amine>Wassim',\n",
       " 'Wassim>Imran']"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dfs(g,\"Amine\")"
   ]
  },
  {
   "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}