{
"metadata": {
"name": "",
"signature": "sha256:fe52e80aefa7cef4c97d80a1d8ac06d5a056bd7deebddce40f058e873b9c3a02"
},
"nbformat": 3,
"nbformat_minor": 0,
"worksheets": [
{
"cells": [
{
"cell_type": "heading",
"level": 1,
"metadata": {},
"source": [
"9 Recurrence relations and recursive algorithms"
]
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Example 15:Page 421"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print \"MERGE SORT\"\n",
"alist=[65,43,22,54,87,11,76,48,30,60,19,75,94,27,58,80]#List to be sorted\n",
"def mergesort(alist):\n",
" print \"Splitting\",alist\n",
" if len(alist)>1:\n",
" \n",
" mid=len(alist)/2\n",
" left_half=alist[:mid]\n",
" right_half=alist[mid:]#Spltting into halves\n",
" mergesort(left_half)\n",
" mergesort(right_half)#Recirsive split to obtain values\n",
" i=0\n",
" j=0\n",
" k=0#Varaibles for indexing\n",
" while i<len(left_half) and j<len(right_half):\n",
" if left_half[i]<right_half[j]:\n",
" alist[k]=left_half[i]#Puts the minimum value in the beginning\n",
" i=i+1\n",
" else:\n",
" alist[k]=right_half[j]\n",
" j=j+1\n",
" k=k+1\n",
" while i<len(left_half):\n",
" alist[k]=left_half[i]#Combine left sorted elements to the whole list\n",
" i=i+1\n",
" k=k+1\n",
" while j<len(right_half):\n",
" alist[k]=right_half[j]#Combine right sorted elements to the wholw list\n",
" j=j+1\n",
" k=k+1\n",
" print \"Merging\",alist\n",
" \n",
"mergesort(alist)\n",
"print(alist)\n",
"\n",
"\n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"MERGE SORT\n",
"Splitting [65, 43, 22, 54, 87, 11, 76, 48, 30, 60, 19, 75, 94, 27, 58, 80]\n",
"Splitting [65, 43, 22, 54, 87, 11, 76, 48]\n",
"Splitting [65, 43, 22, 54]\n",
"Splitting [65, 43]\n",
"Splitting [65]\n",
"Merging [65]\n",
"Splitting [43]\n",
"Merging [43]\n",
"Merging [43, 65]\n",
"Splitting [22, 54]\n",
"Splitting [22]\n",
"Merging [22]\n",
"Splitting [54]\n",
"Merging [54]\n",
"Merging [22, 54]\n",
"Merging [22, 43, 54, 65]\n",
"Splitting [87, 11, 76, 48]\n",
"Splitting [87, 11]\n",
"Splitting [87]\n",
"Merging [87]\n",
"Splitting [11]\n",
"Merging [11]\n",
"Merging [11, 87]\n",
"Splitting [76, 48]\n",
"Splitting [76]\n",
"Merging [76]\n",
"Splitting [48]\n",
"Merging [48]\n",
"Merging [48, 76]\n",
"Merging [11, 48, 76, 87]\n",
"Merging [11, 22, 43, 48, 54, 65, 76, 87]\n",
"Splitting [30, 60, 19, 75, 94, 27, 58, 80]\n",
"Splitting [30, 60, 19, 75]\n",
"Splitting [30, 60]\n",
"Splitting [30]\n",
"Merging [30]\n",
"Splitting [60]\n",
"Merging [60]\n",
"Merging [30, 60]\n",
"Splitting [19, 75]\n",
"Splitting [19]\n",
"Merging [19]\n",
"Splitting [75]\n",
"Merging [75]\n",
"Merging [19, 75]\n",
"Merging [19, 30, 60, 75]\n",
"Splitting [94, 27, 58, 80]\n",
"Splitting [94, 27]\n",
"Splitting [94]\n",
"Merging [94]\n",
"Splitting [27]\n",
"Merging [27]\n",
"Merging [27, 94]\n",
"Splitting [58, 80]\n",
"Splitting [58]\n",
"Merging [58]\n",
"Splitting [80]\n",
"Merging [80]\n",
"Merging [58, 80]\n",
"Merging [27, 58, 80, 94]\n",
"Merging [19, 27, 30, 58, 60, 75, 80, 94]\n",
"Merging [11, 19, 22, 27, 30, 43, 48, 54, 58, 60, 65, 75, 76, 80, 87, 94]\n",
"[11, 19, 22, 27, 30, 43, 48, 54, 58, 60, 65, 75, 76, 80, 87, 94]\n"
]
}
],
"prompt_number": 2
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Example 17:Page 424"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print \"BINARY SEARCH\"\n",
"array=[\"\" for i in range(100)]\n",
"temp=0#Variable checks if the element has been found. Initialised to zero, if it retains the same value till the end, then the element is not in the given list\n",
"n=input(\"Enter the number of elements\")\n",
"print \"Enter the elememts in sorted order\"\n",
"for i in range(0,n):\n",
" array[i]=input()#Input the numbers in ascending order\n",
"item=input(\"Enter the item to be searched\")\n",
"first=0#\n",
"last=n-1\n",
"while first<=last:\n",
" mid=(first+last)/2#Finds the middle element\n",
" if item==array[mid]:\n",
" print \"Search is successfully completed\"\n",
" temp=mid\n",
" print \"The item is in position\",temp+1\n",
" \n",
" if item<array[mid]:#Divides the array into half depending on the value to be searched\n",
" last=mid-1\n",
" else:\n",
" first=mid+1\n",
"if temp==0:\n",
" print \"Search is not successfully completed\"\n",
" \n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"BINARY SEARCH\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the number of elements7\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the elememts in sorted order\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"9\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"16\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"25\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"49\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"50\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"67\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"84\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the item to be searched67\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Search is successfully completed\n",
"The item is in position 6\n"
]
}
],
"prompt_number": 3
}
],
"metadata": {}
}
]
}