Scribd
Upload
36 views9 pages

DSA Programs

Uploaded by

saitejakasani091
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
36 views9 pages

DSA Programs

Uploaded by

saitejakasani091
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

5/3/23, 1:05 PM python - Jupyter Notebook

LINEAR SEARCH
In [2]:

def search(lis,key):
for i in range(len(lis)-1):
if lis[i]==key:
return i
return -1

num_list = [98,34,3,12,84,45]
key = int(input('Enter the number to find: '))
index = search(num_list,key)
if index == -1:
print('Element is not found.')
else:
print('Element is found at: ',index)

Enter the number to find: 12


Element is found at: 3

BINARY SEARCH
In [3]:

def binary_search(lis,key):
start = 0
end = len(lis)-1
mid = 0
while start<=end:
mid = (start+end)//2
if lis[mid]>key:
end = mid-1
elif lis[mid]<key:
start = mid+1
else:
return mid
return -1

num_list = [98,34,3,12,84,45]
key = int(input('Enter the number to find: '))
num_list.sort()
index = binary_search(num_list,key)
if index == -1:
print('Element is not found.')
else:
print('Element is found at: ',index)

Enter the number to find: 25


Element is not found.

BUBBLE SORT

localhost:8888/notebooks/sri/[Link] 1/9
5/3/23, 1:05 PM python - Jupyter Notebook

In [9]:

def bubble_sort(lis):
size = len(lis)
for i in range(size):
swap = False
for j in range(0,size-i-1):
if lis[j]>lis[j+1]:
lis[j],lis[j+1]=lis[j+1],lis[j]
swap = True
if not swap:
break
return lis

lis = [98,34,3,12,84,45]
print('unsorted list: ',lis)
sort = bubble_sort(lis)
print('sorted list: ',sort)

unsorted list: [98, 34, 3, 12, 84, 45]


sorted list: [3, 12, 34, 45, 84, 98]

SELECTION SORT
In [10]:

def selection_sort(lis):
for i in range(len(lis)):
min_index = i
for j in range(i+1,len(lis)):
if lis[j]<lis[min_index]:
min_index=j
lis[min_index],lis[i]=lis[i],lis[min_index]
return lis

lis = [98,34,3,12,84,45]
print('unsorted list: ',lis)
selection_sort(lis)
print('sorted list: ',lis)

unsorted list: [98, 34, 3, 12, 84, 45]


sorted list: [3, 12, 34, 45, 84, 98]

MERGE SORT

localhost:8888/notebooks/sri/[Link] 2/9
5/3/23, 1:05 PM python - Jupyter Notebook

In [11]:

def merge_sort(l):
if len(l)<=1:
return l
else:
mid = len(l)//2
left_list=l[:mid]
right_list = l[mid:]
left_sort = merge_sort(left_list)
right_sort = merge_sort(right_list)
result = []
i = j = 0
while i <len(left_sort) and j<len(right_sort):
if left_sort[i]<right_sort[j]:
[Link](left_sort[i])
i+=1
else:
[Link](right_sort[j])
j+=1

[Link](left_sort[i:])
[Link](right_sort[j:])
return result

lis = [98,34,3,12,84,45]
print('unsorted list: ',lis)
sort = merge_sort(lis)
print('sorted list: ',sort)

unsorted list: [98, 34, 3, 12, 84, 45]


sorted list: [3, 12, 34, 45, 84, 98]

QUICK SORT

localhost:8888/notebooks/sri/[Link] 3/9
5/3/23, 1:05 PM python - Jupyter Notebook

In [18]:

def quick_sort(l,start,end):
if start<end:
pi = partition(l,start,end)
quick_sort(l,start,pi-1)
quick_sort(l,pi+1,end)
return l
def partition(l,start,end):
pivot_index = start
pivot = l[pivot_index]
while start<end:
while start<len(l) and l[start]<= pivot:
start +=1
while l[end] > pivot :
end -= 1
if start<=end:
l[start],l[end]=l[end],l[start]
if end!=pivot_index:
l[pivot_index],l[end]=l[end],l[pivot_index]
return end

lis = [98,34,3,12,84,45]
print('unsorted list: ',lis)
sort = quick_sort(lis,0,len(lis)-1)
print('sorted list: ',sort)

unsorted list: [98, 34, 3, 12, 84, 45]


sorted list: [3, 12, 34, 45, 84, 98]

STACK IMPLEMENTATION

localhost:8888/notebooks/sri/[Link] 4/9
5/3/23, 1:05 PM python - Jupyter Notebook

In [14]:

class stack:
def __init__(self):
[Link] = []

def display(self):
print([Link])

def is_empty(self):
return [Link]==[]

def push(self,data):
[Link](data)
return

def pop(self):
if self.is_empty():
print("stack is empty....")
else:
ele = [Link]()
print(ele)

def peek(self):
top = [Link][-1]
print(top)

s = stack()
[Link](3)
[Link](4)
[Link](5)
[Link](6)
[Link]()
[Link]()
[Link]()
[Link]()
[Link]()

6
6
5
[3, 4, 5]
5

QUEUE IMPLEMENTATION

localhost:8888/notebooks/sri/[Link] 5/9
5/3/23, 1:05 PM python - Jupyter Notebook

In [15]:

class queue:
def __init__(self):
[Link] = []

def display(self):
print([Link])

def is_empty(self):
return [Link]==[]

def enqueue(self,data):
[Link](data)
return

def dequeue(self):
if self.is_empty():
print("Queue is empty.....")
else:
ele = [Link](0)
print(ele)

def size(self):
size = len([Link])
print(size)

q = queue()
[Link](1)
[Link](2)
[Link](3)
[Link](4)
[Link](5)
[Link]()
[Link]()
[Link]()

[1, 2, 3, 4, 5]
1
2

LINKED LIST

localhost:8888/notebooks/sri/[Link] 6/9
5/3/23, 1:05 PM python - Jupyter Notebook

localhost:8888/notebooks/sri/[Link] 7/9
5/3/23, 1:05 PM python - Jupyter Notebook

In [16]:

class node:
def __init__(self,data=None):
[Link] = data
[Link] = None

class linked_list:
def __init__(self):
[Link] = None

def list_print(self):
print_val = [Link]
while print_val is not None:
print(print_val.data)
print_val = print_val.next

def add_begin(self,add):
new_node = node(add)
new_node.next = [Link]
[Link] = new_node

def add_end(self,add):
new_node = node(add)
if [Link] == None:
[Link] = new_node
return
last = [Link]
while [Link]:
last = [Link]
[Link] = new_node

def add_bw(self,prev,new):
if prev is None:
return
new_node = node(new)
new_node.next = [Link]
[Link] = new_node

def delete(self,pos):
if [Link] == None:
return

temp = [Link]
if pos == 0:
[Link] = [Link]
temp = None
return

for i in range(pos-1):
temp = [Link]
if temp is None:
break

if temp is None:
return

if [Link] is None:
return

nex = [Link]
localhost:8888/notebooks/sri/[Link] 8/9
5/3/23, 1:05 PM python - Jupyter Notebook

[Link] = None
[Link] = nex

ele1 = linked_list()
[Link] = node(111)
ele2 = node(112)
[Link] = ele2
ele3 = node(113)
[Link] = ele3
ele1.add_begin(114)
ele1.add_bw(ele2,115)
ele1.list_print()
114
111
112
115
113

localhost:8888/notebooks/sri/[Link] 9/9

You might also like