{"nbformat_minor": 0, "cells": [{"source": "# 03 Algorithms", "cell_type": "markdown", "metadata": {}}, {"source": "## Example 03: Page 195", "cell_type": "markdown", "metadata": {}}, {"execution_count": 2, "cell_type": "code", "source": "def binarysearch(a,num): #function definition with its parameters 'a' is the inputlist\n                         #and 'num' number to be found\n\n    first=0 #initially the first position is zero\n    last=len(a)-1 #initially the last position is the total length of the inputlist-1\n    found=False #boolean value to indicate if the number to be searched is found or not.\n\n    while first<=last and not found:\n        midpoint=(first+last)//2 #dividing the inputlist into two halves and comparing the number to be found with the midpoint.\n\n        if a[midpoint]==num: #If the number to be found is equal to the midpoint returns the position.\n           found=True\n        else:\n            if num<a[midpoint]: #if the number to be found is less than the midpoint\n                                #then the first half of the divided input list is taken for further computation.\n\n                last=midpoint-1 #by assigning the last number of the first half(number before the midpoint) to the variable last.\n\n\n            else:\n                first=midpoint+1 #if the number to be found is greater than the midpoint\n                                 #then the second half of the divided input list is taken for further computation.\n                                #by assigning the first number of the second half(number following the midpoint) to the variable first.\n\n    return midpoint #returns the position of the number found in the list. \n\n\n\nnumlist=[1, 23, 5, 6, 7, 8, 10, 12, 13, 15, 16, 18, 19, 20, 22] #List of inputs\nprint \"Found number 19 at the position\",(binarysearch(numlist, 19)) #Printing the position of the number to be found by a function call.\n                                                                    #The function binarysearch is called along with its parameters, inputlist\n                                                                    #and the number to be found.\n\n\n", "outputs": [{"output_type": "stream", "name": "stdout", "text": "Found number 19 at the position 12\n"}], "metadata": {"collapsed": false, "trusted": true}}, {"source": "# 03 Algorithms", "cell_type": "markdown", "metadata": {}}, {"source": "##Example 04: Page 196", "cell_type": "markdown", "metadata": {}}, {"execution_count": null, "cell_type": "code", "source": "input_list1=[3,2,4,1,5] #List to be sorted\ndef bubblesort(input_list1): #Function definition\n    unsorted=True\n    n=-1\n    while unsorted:\n        for j in range(0,len(input_list1)-1): #based on the truth value proceedings are done\n            unsorted=False        \n            if (input_list1[j]>input_list1[j+1]): #algorithm is followed\n                temp=input_list1[j+1]\n                input_list1[j+1]=input_list1[j]\n                input_list1[j]=temp\n                n=n+1\n                print n,\"pass\",input_list1\n            else:\n                unsorted=True\nprint bubblesort(input_list1)\n", "outputs": [], "metadata": {"collapsed": false, "trusted": true}}, {"source": "# 03 Algorithms", "cell_type": "markdown", "metadata": {}}, {"source": "##Example 05: Page 198", "cell_type": "markdown", "metadata": {}}, {"execution_count": 2, "cell_type": "code", "source": "#To perform insertionsort\ndef sort_insertion(inputlist):\n\n    for i in range(1,len(inputlist)):\n\n        val_current = inputlist[i]\n        pos = i \n         \n        # check backwards through sorted list for proper pos of val_current\n        while((pos > 0) and (inputlist[pos-1] > val_current)):\n            inputlist[pos] = inputlist[pos-1]\n            pos = pos-1\n             \n        if pos != i:\n            inputlist[pos] = val_current \n            print(inputlist)\n    return inputlist\ninputlist = [3,2,4,1,5]\nprint sort_insertion(inputlist)\n", "outputs": [{"output_type": "stream", "name": "stdout", "text": "[2, 3, 4, 1, 5]\n[1, 2, 3, 4, 5]\n[1, 2, 3, 4, 5]\n"}], "metadata": {"collapsed": false, "trusted": true}}, {"source": "", "cell_type": "markdown", "metadata": {}}, {"source": "", "cell_type": "markdown", "metadata": {}}], "nbformat": 4, "metadata": {"kernelspec": {"display_name": "Python 2", "name": "python2", "language": "python"}, "language_info": {"mimetype": "text/x-python", "nbconvert_exporter": "python", "version": "2.7.9", "name": "python", "file_extension": ".py", "pygments_lexer": "ipython2", "codemirror_mode": {"version": 2, "name": "ipython"}}}}