In my last article on Introduction to data structures and algorithms I walked you through what algorithms and data structures are, types, classification, properties, characteristics, operations and merits. To get more insights read the articles . here and this here.
In today's topic we will look at:
1.we will learn data structures, abstract data types and their implementation
2.Implementation of binary tree traversal technique in python,
3.Graph traversals techniques i.e. Depth first search and Breadth-first-search in python
4.Implementation of sorting Algorithms in python.
5.Enhanced analytical skill and efficiently use searching and sorting algorithms in real applications.
6.Implementation of searching algorithms in python.
Implementation of ADT(Abstract data type)
Abstract Data type (ADT) is a type (or class) for objects whose behavior is defined by a set of values and a set of operations. The definition of ADT only mentions what operations are to be performed but not how these operations will be implemented. It does not specify how data will be organized in memory and what algorithms will be used for implementing the operations. It is called “abstract” because it gives an implementation-independent view. The process of providing only the essentials and hiding the details is known as abstraction.
user of data type does not need to know how that data type is implemented, for example, we have been using Primitive values like int, float, char data types only with the knowledge that these data type can operate and be performed on without any idea of how they are implemented. So a user only needs to know what a data type can do, but not how it will be implemented. Think of ADT as a black box which hides the inner structure and design of the data type. Now we’ll define three ADTs namely List ADT, Stack ADT, Queue ADT.
List ADT
The data is generally stored in key sequence in a list which has a head structure consisting of count, pointers and address of compare function needed to compare the data in the list.
The data node contains the pointer to a data structure and a self-referential pointer which points to the next node in the list.
The List ADT Functions is given below:
get() – Return an element from the list at any given position.
insert() – Insert an element at any position of the list.
remove() – Remove the first occurrence of any element from a non-empty list.
removeAt() – Remove the element at a specified location from a non-empty list.
replace() – Replace an element at any position by another element.
size() – Return the number of elements in the list.
isEmpty() – Return true if the list is empty, otherwise return false.
isFull() – Return true if the list is full, otherwise return false.
Stack ADT
In Stack ADT Implementation instead of data being stored in each node, the pointer to data is stored.
The program allocates memory for the data and address is passed to the stack ADT.
The head node and the data nodes are encapsulated in the ADT. The calling function can only see the pointer to the stack.
The stack head structure also contains a pointer to top and count of number of entries currently in stack.
push() – Insert an element at one end of the stack called top.
pop() – Remove and return the element at the top of the stack, if it is not empty.
peek() – Return the element at the top of the stack without removing it, if the stack is not empty.
size() – Return the number of elements in the stack.
isEmpty() – Return true if the stack is empty, otherwise return false.
isFull() – Return true if the stack is full, otherwise return false.
Queue ADT
The queue abstract data type (ADT) follows the basic design of the stack abstract data type.
Each node contains a void pointer to the data and the link pointer to the next element in the queue. The program’s responsibility is to allocate memory for storing the data.
enqueue() – Insert an element at the end of the queue.
dequeue() – Remove and return the first element of the queue, if the queue is not empty.
peek() – Return the element of the queue without removing it, if the queue is not empty.
size() – Return the number of elements in the queue.
isEmpty() – Return true if the queue is empty, otherwise return false.
isFull() – Return true if the queue is full, otherwise return false.
Features of ADT:
Abstraction: The user does not need to know the implementation of the data structure.
Better Conceptualization: ADT gives us a better conceptualization of the real world.
Robust: The program is robust and has the ability to catch errors.
implementation of searching Algorithms
Search algorithm is the set of procedures used to locate the specific data from the collection of data. The searching algorithm is always considered to be the fundamental procedure of computing. And hence it is always said that the difference between the fast application and slower application is often decided by the searching algorithm used by the application. We have various types of search algorithms like linear, Fibonacci, binary, exponential etc. But today we are going look at linear search algorithm and binary search algorithm in depth.
Linear search algorithm
Linear search is also known as a sequential searching algorithm to find the element within the collection of data. The algorithm begins from the first element of the list, starts checking every element until the expected element is found. If the element is not found in the list, the algorithm traverses the whole list and return “element not found”. Consider the python program below:
def LinearSearch(array, n, k):
for j in range(0, n):
if (array[j] == k):
return j
return -1
array = [1, 3, 5, 7, 9]
k = 7
n = len(array)
result = LinearSearch(array, n, k)
if(result == -1):
print("Element not found")
else:
print("Element found at index: ", result)
Output
Element found at index: 3
Time Complexity of Linear Search
The running time complexity of the linear search algorithm is O(n) for N number of elements in the list as the algorithm has to travel through each and every element to find the desired element.
Applications of Linear Search
Used to find the desired element from the collection of data when the dataset is small
The searching operations is less than 100 items
Binary search
Binary search is used with a similar concept, i.e to find the element from the list of elements. Binary search algorithms are fast and effective in comparison to linear search algorithms. The most important thing to note about binary search is that it works only on sorted lists of elements. If the list is not sorted, then the algorithm first sorts the elements using the sorting algorithm and then runs the binary search function to find the desired output. We have two binary search methods, recursive and iterative method
Below is an iterative method using python program
def binarySearch(arr, k, low, high):
while low <= high:
mid = low + (high - low)//2
if arr[mid] == k:
return mid
elif arr[mid] < k:
low = mid + 1
else:
high = mid - 1
return -1
arr = [1, 3, 5, 7, 9]
k = 5
result = binarySearch(arr, k, 0, len(arr)-1)
if result != -1:
print("Element is present at index " + str(result))
else:
print("Not found")
Output
Element is present at index 2
Below is recursive method using a python program
def BinarySearch(arr, k, low, high):
if high >= low:
mid = low + (high - low)//2
if arr[mid] == k:
return mid
elif arr[mid] > k:
return BinarySearch(arr, k, low, mid-1)
else:
return BinarySearch(arr, k, mid + 1, high)
else:
return -1
arr = [1, 3, 5, 7, 9]
k = 5
result = BinarySearch(arr, k, 0, len(arr)-1)
if result != -1:
print("Element is present at index " + str(result))
else:
print("Not found")
Output
Element is present at index 2
Time complexity of Binary Search
The running time complexity for binary search is different for each scenario. The best-case time complexity is O(1) which means the element is located at the mid-pointer. The Average and Worst-Case time complexity is O(log n) which means the element to be found is located either on the left side or on the right side of the mid pointer. Here, n indicates the number of elements in the list.
The space complexity of the binary search algorithm is O(1).
Applications of Binary Search
The binary search algorithm is used in the libraries of Java, C++, etc.
It is used in another additional program like finding the smallest element or largest element in the array
It is used to implement a dictionary
Implementation of binary traversal tree in python
Binary tree is special type of hierarchal data structures defined using nodes. Basically its extended version of linked list. Its a tree data structure where each node is allowed to have maximum two children node, generally referred as Left Child and Right Child. Hashing, routing data for network traffic, data compression, and binary search trees are some of its application.
Key terminologies used
Root:- The Topmost node
Height:- Total Number of edges from root node to last(deepest) node
Leaf:- Node with no children
Depth of a Tree: The number of edges from the tree’s node to the root is.
Internal Node:- Node having at least one Child.
Type of Binary Tree
Perfect Binary Tree
A Binary Tree with all the interior node (all nodes except leaf node) have two children and all leaf node has same depth
Balanced Binary Tree
Every tree where the maximum difference between right and left subtree height is 1.
Complete Binary Tree
All binary tree where every node is completely filled with 2 or 0 node .
Degenerate Binary Tree
Every binary tree, where every internal node has only single child.
Applications of Binary Tree
-Used in 3d Video Games.
-Highly used in router for tabling purpose.
-Scheduling processes in OS.
implementation of binary tree in python
implementing the code
class BinaryTree:
def __init__(self, value):
self.left = None
self.right = None
self.value = value
def insert(self, value):
if self.value:
if data < self.value:
if self.left is None:
self.left = BinaryTree(value)
else:
self.left.insert(value)
elif data > self.value:
if self.right is None:
self.right = BinaryTree(value)
else:
self.right.insert(value)
else:
self.value = value
def PrintTree(self):
if self.left:
self.left.PrintTree()
print( self.data),
if self.right:
self.right.PrintTree()
root = BinaryTree(100)
root.insert(50)
root.insert(55)
root.insert(60)
root.insert(20)
root.insert(52)
root.PrintTree()
Traversal operation
When, we print the values of every node here we are using preorder traversal where left first left most child is printed, then root, then the right child.
Traversal:-
PreOrder Traversal
InOrder Traversal
PostOrder Traversal
PostOrder Traversal:-
Here the Left child is visited first, then the Right child node and then Root node.
The minutes changes in the PrintTree() method is following
def PrintTree(self):
if self.left:
self.left.PrintTree()
if self.right:
self.right.PrintTree()
print(self.value)
PreOrder Traversal
Here the Root is visited first, then left child node and then right child node.
The minutes changes in the PrintTree() method is following
def PrintTree(self):
print(self.value)
if self.left:
self.left.PrintTree()
if self.right:
self.right.PrintTree()
Search Operation
Searching in a Binary Tree
Searching in a binary tree is a very simple step, as we have already discussed traversing a binary tree, so we can use the traversing technique to get all the elements in a tree and and find our required element. Here we are using preorder traversal, you guys can use anyone of them.
def PrintTree(self,element):
if self.left:
self.left.PrintTree()
if(self.data==element):
print("Found",self.data)
return(1)
else:
continue
if self.right:
self.right.PrintTree()
Deletion operation
Deleting a element from the binary tree
def delete_Node(root, key):
if not root:
return root
if root.val > key:
root.left = delete_Node(root.left, key)
elif root.val < key:
root.right= delete_Node(root.right, key)
else:
if not root.right:
return root.left
if not root.left:
return root.right
temp_val = root.right
mini_val = temp_val.val
while temp_val.left:
temp_val = temp_val.left
mini_val = temp_val.val
root.right = deleteNode(root.right,root.val)
return root
Explanation
The above programs explain the procedure to delete a particular element from the given binary tree. Here root represents the root node and key represents the element that needs to be deleted or has been ordered by the user.
Graph traversals techniques
Graphs are very useful data structures in solving many important mathematical challenges.
Depth First Traversal
Also called depth first search (DFS),this algorithm traverses a graph in a depth ward motion and uses a stack to remember to get the next vertex to start a search, when a dead end occurs in any iteration. We implement DFS for a graph in python using the set data types as they provide the required functionalities to keep track of visited and unvisited nodes.
class graph:
def __init__(self,gdict=None):
if gdict is None:
gdict = {}
self.gdict = gdict
# Check for the visisted and unvisited nodes
def dfs(graph, start, visited = None):
if visited is None:
visited = set()
visited.add(start)
print(start)
for next in graph[start] - visited:
dfs(graph, next, visited)
return visited
gdict = {
"a" : set(["b","c"]),
"b" : set(["a", "d"]),
"c" : set(["a", "d"]),
"d" : set(["e"]),
"e" : set(["a"])
}
dfs(gdict, 'a')
Breadth First Traversal
Also called breadth first search (BFS),this algorithm traverses a graph breadth ward motion and uses a queue to remember to get the next vertex to start a search, when a dead end occurs in any iteration. Please visit this link in our website to understand the details of BFS steps for a graph.
We implement BFS for a graph in python using queue data structure discussed earlier. When we keep visiting the adjacent unvisited nodes and keep adding it to the queue. Then we start dequeue only the node which is left with no unvisited nodes. We stop the program when there is no next adjacent node to be visited.
Example
import collections
class graph:
def __init__(self,gdict=None):
if gdict is None:
gdict = {}
self.gdict = gdict
def bfs(graph, startnode):
# Track the visited and unvisited nodes using queue
seen, queue = set([startnode]), collections.deque([startnode])
while queue:
vertex = queue.popleft()
marked(vertex)
for node in graph[vertex]:
if node not in seen:
seen.add(node)
queue.append(node)
def marked(n):
print(n)
# The graph dictionary
gdict = {
"a" : set(["b","c"]),
"b" : set(["a", "d"]),
"c" : set(["a", "d"]),
"d" : set(["e"]),
"e" : set(["a"])
}
bfs(gdict, "a")
Implementation of sorting Algorithms
Sorting is defined as an arrangement of data in a certain order. Sorting techniques are used to arrange data(mostly numerical) in an ascending or descending order.
Some of the real-life examples of sorting are:
1.Telephone Directory: It is a book that contains telephone numbers and addresses of people in alphabetical order.
2.Dictionary: It is a huge collection of words along with their meanings in alphabetical order.
3.Contact List: It is a list of contact numbers of people in alphabetical order on a mobile phone.The different types of order are:
Increasing Order: A set of values are said to be increasing order when every successive element is greater than its previous element. For example: 1, 2, 3, 4, 5. Here, the given sequence is in increasing order.
Decreasing Order: A set of values are said to be in increasing order when the successive element is always less than the previous one. For Example: 5, 4, 3, 2, 1. Here the given sequence is in decreasing order.
Non-Increasing Order: A set of values are said to be in non-increasing order if every ith element present in the sequence is greater than or equal to its (i-1)th element. This order occurs whenever there are numbers that are being repeated. For Example: 1, 2, 2, 3, 4, 5. Here 2 repeated two times.
Non-Decreasing Order: A set of values are said to be in non-decreasing order if every ith element present in the sequence is less than or equal to its (i-1)th element. This order occurs whenever there are numbers that are being repeated. For Example: 5, 4, 3, 2, 2, 1. Here 2 repeated two times.
Sorting Techniques
The different implementations of sorting techniques in Python are:
Bubble Sort
Selection Sort
Insertion Sort
Bubble Sort
Bubble Sort is a simple sorting algorithm. This sorting algorithm repeatedly compares two adjacent elements and swaps them if they are in the wrong order. It is also known as the sinking sort. It has a time complexity of O(n2) in the average and worst cases scenarios and O(n) in the best-case scenario. Bubble sort can be visualized as a queue where people arrange themselves by swapping with each other so that they all can stand in ascending order of their heights. Or in other words, we compare two adjacent elements and see if their order is wrong, if the order is wrong we swap them. (i.e arr[i] > arr[j] for 1 <= i < j <= s; where s is the size of the array, if array is to be in ascending order, and vice-versa).
Example
Here we sort the following sequence using bubble sort
Sequence: 2, 23, 10, 1
First Iteration
(2, 23, 10, 1) –> (2, 23, 10, 1), Here the first 2 elements are compared and remain the same because they are already in ascending order.
(2, 23, 10, 1) –> (2, 10, 23, 1), Here 2nd and 3rd elements are compared and swapped(10 is less than 23) according to ascending order.
(2, 10, 23, 1) –> (2, 10, 1, 23), Here 3rd and 4th elements are compared and swapped(1 is less than 23) according to ascending order
At the end of the first iteration, the largest element is at the rightmost position which is sorted correctly.
Second Iteration
(2, 10, 1, 23) –> (2, 10, 1, 23), Here again, the first 2 elements are compared and remain the same because they are already in ascending order.
(2, 10, 1, 23) –> (2, 1, 10, 23), Here 2nd and 3rd elements are compared and swapped(1 is less than 10) in ascending order.
At the end of the second iteration, the second largest element is at the adjacent position to the largest element.
Third Iteration
(2, 1, 10, 23) –> (1, 2, 10, 23), Here the first 2 elements are compared and swap according to ascending order.
The remaining elements are already sorted in the first and second Iterations. After the three iterations, the given array is sorted in ascending order. So the final result is 1, 2, 10, 23.
** Implementation of bubble sort**
# Python3 program for Bubble Sort Algorithm Implementation
def bubbleSort(arr):
n = len(arr)
# For loop to traverse through all
# element in an array
for i in range(n):
for j in range(0, n - i - 1):
# Range of the array is from 0 to n-i-1
# Swap the elements if the element found
#is greater than the adjacent element
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
# Driver code
# Example to test the above code
arr = [ 2, 1, 10, 23 ]
bubbleSort(arr)
print("Sorted array is:")
for i in range(len(arr)):
print("%d" % arr[i])
Selection Sort
This sorting technique repeatedly finds the minimum element and sort it in order. Bubble Sort does not occupy any extra memory space. During the execution of this algorithm, two subarrays are maintained, the subarray which is already sorted, and the remaining subarray which is unsorted. During the execution of Selection Sort for every iteration, the minimum element of the unsorted subarray is arranged in the sorted subarray. Selection Sort is a more efficient algorithm than bubble sort. Sort has a Time-Complexity of O(n2) in the average, worst, and in the best cases.
Example
Here we sort the following sequence using the selection sort
Sequence: 7, 2, 1, 6
(7, 2, 1, 6) –> (1, 7, 2, 6), In the first traverse it finds the minimum element(i.e., 1) and it is placed at 1st position.
(1, 7, 2, 6) –> (1, 2, 7, 6), In the second traverse it finds the 2nd minimum element(i.e., 2) and it is placed at 2nd position.
(1, 2, 7, 6) –> (1, 2, 6, 7), In the third traverse it finds the next minimum element(i.e., 6) and it is placed at 3rd position.
After the above iterations, the final array is in sorted order, i.e., 1, 2, 6, 7.
Implementation of Selection Sort
# Selection Sort algorithm in Python
def selectionSort(array, size):
for s in range(size):
min_idx = s
for i in range(s + 1, size):
# For sorting in descending order
# for minimum element in each loop
if array[i] < array[min_idx]:
min_idx = i
# Arranging min at the correct position
(array[s], array[min_idx]) = (array[min_idx], array[s])
# Driver code
data = [ 7, 2, 1, 6 ]
size = len(data)
selectionSort(data, size)
print('Sorted Array in Ascending Order is :')
print(data)
Insertion Sort
This sorting algorithm maintains a sub-array that is always sorted. Values from the unsorted part of the array are placed at the correct position in the sorted part. It is more efficient in practice than other algorithms such as selection sort or bubble sort. Insertion Sort has a Time-Complexity of O(n2) in the average and worst case, and O(n) in the best case.
Example
Here we sort the following sequence using the insertion sort
Sequence: 7, 2, 1, 6
(7, 2, 1, 6) –> (2, 7, 1, 6), In the first iteration, the first 2 elements are compared, here 2 is less than 7 so insert 2 before 7.
(2, 7, 1, 6) –> (2, 1, 7, 6), In the second iteration the 2nd and 3rd elements are compared, here 1 is less than 7 so insert 1 before 7.
(2, 1, 7, 6) –> (1, 2, 7, 6), After the second iteration (1, 7) elements are not in ascending order so first these two elements are arranged. So, insert 1 before 2.
(1, 2, 7, 6) –> (1, 2, 6, 7), During this iteration the last 2 elements are compared and swapped after all the previous elements are swapped.
Implementation of Insertion Sort
# Creating a function for insertion sort algorithm
def insertion_sort(list1):
# Outer loop to traverse on len(list1)
for i in range(1, len(list1)):
a = list1[i]
# Move elements of list1[0 to i-1],
# which are greater to one position
# ahead of their current position
j = i - 1
while j >= 0 and a < list1[j]:
list1[j + 1] = list1[j]
j -= 1
list1[j + 1] = a
return list1
# Driver code
list1 = [ 7, 2, 1, 6 ]
print("The unsorted list is:", list1)
print("The sorted new list is:", insertion_sort(list1))
Application of search and sorting in real applications
Searching is the process of locating a given object or data within a large set of data. Sorting, on the other hand, is the arrangement of data in a specific required order. The common application of these algorithms is in databases and other computer applications.
Conculsion
Have handled data structure and algorithms in depth. Am open to additions, corrections and questions. I believe we learn through each other. Happy coding
Top comments (0)