(5) Develop programs for data structure algorithms using python
1) Searching Algorithms, A) Linear Search, B) Binary Search
2) Sorting Algorithms, A)Selection Sort, B)Bubble Sort,
C)Insertion Sort, D)Merge Sort, E)Quick Sort,
3) Hash Tables A)Accessing Values B) Updating Values C)Delete Dictionary Elements
Program Code -1A: Linear Search Algorithm program
# linear_search program
def linear_search(alist, key):
"""Return index of key in alist. Return -1 if key not present."""
for i in range(len(alist)):
if alist[i] == key:
return i
return -1
alist = input('Enter the list of numbers: ')
alist = alist.split()
alist = [int(x) for x in alist]
key = int(input('The number to search for: '))
index = linear_search(alist, key)
if index < 0:
print('{} was not found.'.format(key))
else:
print('{} was found at index {}.'.format(key, index))
Output-1A:Linear Search Algorithm program
Program Code-1B:binary Search Algorithm program
#Python program to implement binary search without using recursion.#The program output is shown below.
def binary_search(alist, key):
"""Search key in alist[start... end - 1]."""
start = 0
end = len(alist)
while start < end:
mid = (start + end)//2
if alist[mid] > key:
end = mid
elif alist[mid] < key:
start = mid + 1
else:
return mid
return -1
alist = input('Enter the sorted list of numbers: ')
alist = alist.split()
alist = [int(x) for x in alist]
key = int(input('The number to search for: '))
index = binary_search(alist, key)
if index < 0:
print('{} was not found.'.format(key))
else:
print('{} was found at index {}.'.format(key, index))
Output-1B:binary Search Algorithm program
Program Code-2A: Bubble Sort
#Lab-5-Python program to implement bubble_sort
#bubble_sort program
def bubble_sort(alist):
for i in range(len(alist) - 1, 0, -1):
no_swap = True
for j in range(0, i):
if alist[j + 1] < alist[j]:
alist[j], alist[j + 1] = alist[j + 1], alist[j]
no_swap = False
if no_swap:
return
alist = input('Enter the list of numbers: ').split()
alist = [int(x) for x in alist]
bubble_sort(alist)
print('Sorted list: ', end='')
print(alist)
Output-2A: Bubble Sort
Program Code-2B: Quick Sort
#Lab-5-Python program to implement quicksort.
#quick sort program
def quicksort(alist, start, end):
'''Sorts the list from indexes start to end - 1 inclusive.'''
if end - start > 1:
p = partition(alist, start, end)
quicksort(alist, start, p)
quicksort(alist, p + 1, end)
def partition(alist, start, end):
pivot = alist[start]
i = start + 1
j = end - 1
while True:
while (i <= j and alist[i] <= pivot):
i = i + 1
while (i <= j and alist[j] >= pivot):
j = j - 1
if i <= j:
alist[i], alist[j] = alist[j], alist[i]
else:
alist[start], alist[j] = alist[j], alist[start]
return j
alist = input('Enter the list of numbers: ').split()
alist = [int(x) for x in alist]
quicksort(alist, 0, len(alist))
print('Sorted list: ', end='')
print(alist)
Output-2B: Quick Sort
Program Code-2C: Merge Sort
#Lab-5-Python program to implement mergesort.
#Merge sort program
def merge_sort(alist, start, end):
'''Sorts the list from indexes start to end - 1 inclusive.'''
if end - start > 1:
mid = (start + end)//2
merge_sort(alist, start, mid)
merge_sort(alist, mid, end)
merge_list(alist, start, mid, end)
def merge_list(alist, start, mid, end):
left = alist[start:mid]
right = alist[mid:end]
k = start
i = 0
j = 0
while (start + i < mid and mid + j < end):
if (left[i] <= right[j]):
alist[k] = left[i]
i = i + 1
else:
alist[k] = right[j]
j = j + 1
k = k + 1
if start + i < mid:
while k < end:
alist[k] = left[i]
i = i + 1
k = k + 1
else:
while k < end:
alist[k] = right[j]
j = j + 1
k = k + 1
alist = input('Enter the list of numbers: ').split()
alist = [int(x) for x in alist]
merge_sort(alist, 0, len(alist))
print('Sorted list: ', end='')
print(alist)
Output-2C: Merge Sort
Program Code-2D: insertion Sort
#Lab-5-Python program to implement insertion_sort.
#insertion_sort program
def insertion_sort(alist):
for i in range(1, len(alist)):
temp = alist[i]
j = i - 1
while (j >= 0 and temp < alist[j]):
alist[j + 1] = alist[j]
j = j - 1
alist[j + 1] = temp
alist = input('Enter the list of numbers: ').split()
alist = [int(x) for x in alist]
insertion_sort(alist)
print('Sorted list: ', end='')
print(alist)
Output-2D: insertion Sort
Program Code-2E: Selection Sort
#Lab-5-Python program to implement selection_sort.
#selection_sort program
def selection_sort(alist):
for i in range(0, len(alist) - 1):
smallest = i
for j in range(i + 1, len(alist)):
if alist[j] < alist[smallest]:
smallest = j
alist[i], alist[smallest] = alist[smallest], alist[i]
alist = input('Enter the list of numbers: ').split()
alist = [int(x) for x in alist]
selection_sort(alist)
print('Sorted list: ', end='')
print(alist)
Output-2E: Selection Sort
Program Code -3A: Hash Table(Accessing Values)
dict =
{'Name': 'Zara', 'Age': 7,
'Class': 'First'}
# Accessing the dictionary with its key
print
("dict['Name']:
", dict['Name'])
print ("dict['Age']: ",
dict['Age'])
Output-3A: Hash Table(Accessing Values)
Program Code -3B: Hash Table(Updating)
dict = {'Name': 'Zara', 'Age': 7, 'Class': 'First'} dict['Age'] = 8;
# update existing entry
dict['School'] = "DPS School"; # Add new entry
print "dict['Age']: ", dict['Age']
print "dict['School']: ", dict['School']
# update existing entry
dict['School'] = "DPS School"; # Add new entry
print "dict['Age']: ", dict['Age']
print "dict['School']: ", dict['School']
Output-3B: Hash Table(Updating)
Program Code -3C: Hash TableLinear(Delete Dictionary Elements)
del dict['Name']; # remove entry with key 'Name'
dict.clear(); # remove all entries in dict
del dict ; # delete entire dictionary
print ("dict['Age']: ", dict['Age'])
print ("dict['School']: ", dict['School'])
Output-3C: Hash TableLinear(Delete Dictionary Elements)
No comments:
Post a Comment