EXPERIMENT -1
Object:- Write a Python Program to perform Linear Search.
Code:-
def linearSearch(array, n, x)
for i in range(0, n):
if (array[i] = = x):
return i
return -1
array = [2, 4, 0, 1, 9]
x=1
n = len(array)
result = linearSearch(array, n, x)
if(result = = -1):
print("Element not found")
else:
print("Element found at index: ", result)
Output:-
Element found at index: 3
Time Complexity : O(n)
Space Complexity : O(1)
EXPERIMENT -2
Object:- Write a Python Program to perform Binary Search.
Code:-
def binarySearch(array, x, low, high):
while low <= high:
mid = low + (high - low)//2
if array[mid] = = x:
return mid
elif array[mid] < x:
low = mid + 1
else:
high = mid - 1
return -1
array = [3, 4, 5, 6, 7, 8, 9]
x=4
result = binarySearch(array, x, 0, len(array)-1)
if result != -1:
print("Element is present at index " + str(result))
else:
print("Not found")
Output:-
Element is present at index 1
Time Complexity :
Best case - O(1)
Average case- O(log n)
Worst case- O(log n)
Space Complexity : O(1)
EXPERIMENT -3
Object:- Write a Python Program to perform selection sort.
Code:-
def selectionSort(array, size):
for step in range(size):
min_idx = step
for i in range(step + 1, size):
if array[i] < array[min_idx]:
min_idx = i
# put min at the correct position
(array[step], array[min_idx]) = (array[min_idx], array[step])
data = [-2, 45, 0, 11, -9]
size = len(data)
selectionSort(data, size)
print('Sorted Array in Ascending Order:')
print(data)
Output:-
Sorted Array in Ascending Order:
[-9, -2, 0, 11, 45]
Time Complexity :
Best case - O(n2)
Average case- O(n2)
Worst case- O(n2)
Space Complexity : O(1)
EXPERRIMENT -4
Object:- Write a Python Program to perform insertion sort.
Code:-
def insertionSort(array):
for step in range(1, len(array)):
key = array[step]
j = step - 1
while j >= 0 and key < array[j]:
array[j + 1] = array[j]
j=j-1
# Place key at after the element just smaller than it.
array[j + 1] = key
data = [9, 5, 1, 4, 3]
insertionSort(data)
print('Sorted Array in Ascending Order:')
print(data)
Output:-
Sorted Array in Ascending Order:
[1, 3, 4, 5, 9]
Time Complexity :
Best case - O(n)
Average case- O(n2)
Worst case- O(n2)
Space Complexity : O(1)
EXPERIMENT -5
Object:- Write a Python Program to perform Merge sort.
Code:-
def mergeSort(array):
if len(array) > 1:
r = len(array)//2
L = array[:r]
M = array[r:]
mergeSort(L)
mergeSort(M)
i=j=k=0
while i < len(L) and j < len(M):
if L[i] < M[j]:
array[k] = L[i]
i += 1
else:
array[k] = M[j]
j += 1
k += 1
while i < len(L):
array[k] = L[i]
i += 1
k += 1
while j < len(M):
array[k] = M[j]
j += 1
k += 1
def printList(array):
for i in range(len(array)):
print(array[i], end=" ")
print()
# Driver program
if __name__ = = '__main__':
array = [6, 5, 12, 10, 9, 1]
mergeSort(array)
print("Sorted array is: ")
printList(array)
Output:-
Sorted array is:
1 5 6 9 10 12
Time Complexity :
Best case - O(n*log n)
Average case- O(n*log n)
Worst case- O(n*log n)
Space Complexity : O(n)