1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
|
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# 03:ALGORITHMS"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Example 03: Page 195"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Found number 19 at the position 12\n"
]
}
],
"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",
"\n",
"numlist=[1, 23, 5, 6, 7, 8, 10, 12, 13, 15, 16, 18, 19, 20, 22] #List of inputs\n",
"print \"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"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# 03:ALGORITHMS"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"##Example 05: Page 198"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[2, 3, 4, 1, 5]\n",
"[1, 2, 3, 4, 5]\n",
"[1, 2, 3, 4, 5]\n"
]
}
],
"source": [
"#To perform insertionsort\n",
"def 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\n",
"inputlist = [3,2,4,1,5]\n",
"print sort_insertion(inputlist)\n"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 2",
"language": "python",
"name": "python2"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 2
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython2",
"version": "2.7.9"
}
},
"nbformat": 4,
"nbformat_minor": 0
}
|
