Q13. WRITE A PROGRAM IN PYTHON TO IMPLEMENT BUBBLE SORT.
def bubblesort(elements):
swapped = False
for n in range(len(elements)-1, 0, -1):
for i in range(n):
if elements[i] > elements[i + 1]:
swapped = True
elements[i], elements[i + 1] = elements[i + 1], elements[i]
if not swapped:
return
elements = [39, 12, 18, 85, 72, 10, 2, 18]
print("Unsorted list is,")
print(elements)
bubblesort(elements)
print("Sorted Array is, ")
print(elements)
Q14. WRITE A PROGRAM IN PYTHON TO IMPLEMENT SELECTION SORT.
def selectionSort(array, size):
for ind in range(size):
min_index = ind
for j in range(ind + 1, size):
if array[j] < array[min_index]:
min_index = j
(array[ind], array[min_index]) = (array[min_index], array[ind])
arr = [-2, 45, 0, 11, -9,88,-97,-202,747]
size = len(arr)
selectionSort(arr, size)
print('The array after sorting in Ascending Order by selection sort is:')
print(arr)
Q15. WRITE A PROGRAM IN PYTHON TO IMPLEMENT INSERTION SORT.
def insertionSort(arr):
n = len(arr)
if n <= 1:
return
for i in range(1, n):
key = arr[i]
j = i-1
while j >= 0 and key < arr[j]:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key # Insert the key in the correct position
arr = [12, 11, 13, 5, 6]
insertionSort(arr)
print(arr)
Q16. WRITE A PYTHON PROGRAM TO CHECK WHETHER THE GIVEN STRING IS PALINDROME OR NOT, USING
DEQUE.
string = input("Enter a string :- ")
deque = [ ]
for i in string :
deque.append(i)
length = len ( deque ) // 2
x=1
for i in range (length) :
front_element = deque.pop(0)
rear_element = deque.pop()
if front_element != rear_element :
x=0
break
if x == 0 :
print("Not palindrome")
else :
print("Palindrome")
Q17. WRITE A PROGRAM USING USER DEFINED FUNCTIONS THAT ACCEPTS A LIST OF NUMBERS AS AN ARGUMENT
AND FINDS ITS MEDIAN.
def bubblesort(numlist):
length = len(numlist)
for i in range( length - 1):
for j in range(0, length-1-i):
if numlist[j] > numlist[j+1]:
numlist[j], numlist[j+1] = numlist[j+1], numlist[j]
numbers = eval(input("Enter list using bracket : "))
bubblesort(numbers)
size = len(numbers)
if size % 2 == 0:
median = (numbers[size//2-1] + numbers[(size//2)]) / 2
else:
median = numbers[size//2]
print("Given list in sorted orders : ")
print(numbers)
print("Median : ", median)
Q.18. WRITE A PROGRAM IN PYTHON TO SHOW THE USE OF LINEAR SEARCH IN PYTHON.
PROGRAM 6.1 PAGE 84
Q.19. WRITE A PROGRAM IN PYTHON TO SHOW THE USE OF BINARY SEARCH IN PYTHON.
PROGRAM 6.2 PAGE 89
Q.20. WRITE A PROGRAM TO SHOW THE USE OF HASHING TO FIND A KEY IN THE GIVEN LIST L IN PYTHON
PRGORAM 6.3 PAGE 91
Q.21. WRITE A PROGRAM THAT TAKES AS INPUT A LIST HAVING A MIX OF 10 NEGATIVE AND POSITIVE NUMBERS
AND A KEY VALUE. APPLY LINEAR SEARCH TO FIND WHETHER THE KEY IS PRESENT IN THE LIST OR NOT. IF THE KEY
IS PRESENT, IT SHOULD DISPLAY THE POSITION OF THE KEY IN THE LIST OTHERWISE IT SHOULD PRINT AN
APPROPRIATE MESSAGE. RUN THE PROGRAM FOR AT LEAST 3 DIFFERENT KEYS AND NOTE THE RESULT.
def linearSearch(list, key):
for index in range(0,len(list)):
if list[index] == key:
return index+1
return None
list1 = []
maximum = int(input("How many elements in your list? "))
print("Enter each element and press enter: ")
for i in range(0,maximum):
n = int(input())
list1.append(n)
print("the list contents are:", list1)
key = int(input("Enter the number to be searched:"))
position = linearSearch(list1, key)
if position is None:
print("Number",key,"is not present in the list")
else:
print("Number",key,"is present at position",position)
Q.22. WRITE A PROGRAM THAT TAKES AS INPUT A LIST OF 10 INTEGERS AND A KEY VALUE AND APPLIES BINARY
SEARCH TO FIND WHETHER THE KEY IS PRESENT IN THE LIST OR NOT. IF THE KEY IS PRESENT, IT SHOULD DISPLAY
THE POSITION OF THE KEY IN THE LIST OTHERWISE IT SHOULD PRINT AN APPROPRIATE MESSAGE. RUN THE
PROGRAM FOR AT LEAST 3 DIFFERENT KEY VALUES AND NOTE THE RESULTS.
def bisearch (ar, key):
low = 0
high = len(ar)-1
while low <= high :
mid = int ((low+high)/2)
if key == ar[mid]:
return mid
elif key < ar [mid]:
high = mid - 1
else :
low = mid +1
else :
return -999
lst = eval(input ("Enter a List :-"))
key = int (input("Enter search key : " ))
res = bisearch(lst , key)
if res >= 0:
print (key , "FOUND at index ", res+1)
else :
print ("Sorry ! ",key ,"Not FOUND in list")
