Faculty of Engineering & Technology
Sankalchand Patel College of Engineering, Visnagar
Python Programming
(1ET1030702)
Unit-5
Algorithms and Data structures
Prepared By
Mr. Mehul S. Patel
Department of Computer Engineering & Information Technology
Content
• Search Algorithms
• Sorting Algorithms
• Stack
• Queue
Searching
• Searching is the process of finding particular information from a
collection of data based on specific criteria
• Search operations can be performed on every collection data
structure (string, array, list, stack, dictionary, set, …)
• Search operation accepts two inputs:
• Collection (or sequence) object
• Search key
• Search key can have several forms
• An item that we want to find in a list
• Part of an item to search
• Multiple parts for searching matching items (Google search)
Search Modes
• There are four different types of search operations
• In or out: Checking if the collection contains or does not contain the
item
Example: item in L
• First match: Finding the first occurrence of the key and reporting its
location in the collection
Example: [Link](item)
• All matches: Finding all the items in the collection that match the key
Example: [Link](Names, “Dan*”)
• Partial matches: Find the first n items that match the key
Linear Search (return first match)
def linear_search(List, item):
n = len(List)
for i in range(n):
if item == List[i]:
return i
return -1
• Linear search is already implemented by the list index method except
that when the item is not in the list you get an error
• The run time order of the linear search algorithm is O(n)
• Question: suppose that our sequence is sorted, could this help to
speed the search process?
Binary Search
L=[0, 1, 3, 4, 5, 7, 8, 9, 11, 14, 16, 18, 19]
# L is in sorted order!
binary_search(L, 7) -> low=0, high=len(L)-1 = 12
mid = (low+high)/2 = 6
Binary Search Algorithm (Iterative)
def binary_search(List, item, low=0, high=None):
if high is None:
high = len(List)
while low < high:
mid = (low + high) / 2
mid_value = List[mid]
if mid_value < item:
low = mid+1
elif mid_value > item:
high = mid
else:
return mid
return -1
Binary Search Algorithm (Recursive)
def binary_search_rec(List, item, low=0, high=None):
if high is None:
high = len(List)
if low >= high: # empty list
return -1
mid = (low + high) / 2
mid_value = List[mid]
if item < mid_value:
return binary_search_rec(List, item, low, mid)
elif item > mid_value:
return binary_search_rec(List, item, mid+1, high)
else:
return mid
Sorting
• Although binary search run time is fast O(log n), it depends on sorting
the sequence !!!
• Questions:
• What is the cost of sorting a sequence container?
• What sorting algorithms do we have?
• And which are the best sorting algorithms?
Bubble Sort
def bubble_sort(L):
N = len(L)
while True:
sorted = True
for i in range(0,N-1):
if L[i+1] < L[i]:
sorted = False
L[i], L[i+1] = L[i+1], L[i]
if sorted:
return
Selection Sort
def bubble_sort2(L):
N = len(L)
for i in range(0,N-1):
for j in range(i+1, N):
if L[j] < L[i]:
L[i], L[j] = L[j], L[i]
Stack
• Definition:
A stack is a linear data structure that follows the Last In, First Out
(LIFO) principle.
• LIFO – Last In First Out
• Use cases: Undo mechanisms, parsing expressions
• Real-life Example:
Think of a stack of plates; you can only take the top plate off first.
• Operations:
• Push: Add an element to the top of the stack.
• Pop: Remove the top element from the stack.
• Peek/Top: View the top element without removing it.
• IsEmpty: Check if the stack is empty.
Stack
class Stack:
def __init__(self):
[Link] = []
def push(self, item):
[Link](item)
def pop(self):
if not self.is_empty():
return [Link]()
def peek(self):
if not self.is_empty():
return [Link][-1]
def is_empty(self):
return len([Link]) == 0
Queue
• Definition:
A queue is a linear data structure that follows the First In, First Out
(FIFO) principle.
• FIFO – First In First Out
• Use cases: Task scheduling, handling requests in order
• Real-life Example:
Think of a queue at a ticket counter; the first person in line is the first
to be served
• Operations:
• Enqueue: Add an element to the end of the queue.
• Dequeue: Remove the front element from the queue.
• Front: View the front element without removing it.
• IsEmpty: Check if the queue is empty.
Queue
class Queue:
def __init__(self):
[Link] = []
def enqueue(self, item):
[Link](item)
def dequeue(self):
if not self.is_empty():
return [Link](0)
def front(self):
if not self.is_empty():
return [Link][0]
def is_empty(self):
return len([Link]) == 0
Questions?