In the last article we introduced ourselves into what data structures are, listing some few examples.
Today we're going to dive a little bit deeper giving code examples in python on how to implement the data structures and algorithms mentioned. We'll dig into abstract data structures,searching algorithms and sorting algorithms
ABSTRACT DATA STRUCTURES
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.It is called “abstract” because it the results to be achieved are given but how they are to be achieved is not defined or restricted.
Abstract data structure types include arrays,lists,queues,stacks,trees,vectors,maps,etc. Today we're going to focus on lists,stacks and queues.
Lists ADTs
Lists are used to store data in a sequential manner. The items in the list are ordered and their positions are marked by indexing. Positive indexing marks the first element from 0 and continues till the last element. Negative indexing marks the data starting from the last element in the list to the first element. Just the opposite of positive listing.
Lists can contain multiple data types eg strings,integers,floats,etc.Below is a code example of a list containing multiple data types:
data = ['hello', 3.14, 420]
A number of methods or operations can be done with lists. Examples are as below:
list.index()
This returns the index(position) of an item in a list.
# items list
items = ['book', 'pen', 'car', 'ruler', 'phone', 'sun']
# index of 'car' in items
index = items.index('car')
# Output: 3
print(index)
list.append()
Adds an item to end of the list.
cars = ['BMW']
cars.append('Audi')
# Output: ['BMW', 'Audi']
print(cars)
list.extend()
Extends a list by adding items even from another list
items1 = ['spoon', 'plate']
items2 = ['fork', 'knife'] items1.extend(items2)
print(items1)
# Output: ['spoon', 'plate', 'fork', 'knife']
Other list methods are:
- list.sort()
- list.copy()
- list.insert()
- list.remove()
- list.pop() etc.
Stacks
A stack is a linear data structure that stores items in a Last-In/First-Out (LIFO) or First-In/Last-Out (FILO) manner.Pop and push functions are used to insert and delete items in a stack.
The functions associated with stack are:
empty() – Returns whether the stack is empty.
size() – Returns the size of the stack.
top() / peek() – Returns a reference to the topmost element of the stack.
push() – Inserts an element at the top of the stack.
pop() – Deletes the topmost element of the stack.
Example code of some of the operations on stacks is below.
#Create an empty stack.
stack = []
#using append() function to add items to the stack
stack.append('a')
stack.append('b')
stack.append('c')
print(stack)
Output
['a', 'b', 'c']
pop()
#pop() function to pop element from stack in
#LIFO order
print('\nElements popped from stack:')
print(stack.pop())
print(stack.pop())
print(stack.pop())
Output
Elements popped from stack:
c
b
a
New stack
print('\nStack after elements are popped:')
print(stack)
Output
Stack after elements are popped: []
Queues
Items in queues also have a first-in/last-out and last-in/first-out manner.Data is inserted into Queue using the put() function and get() takes data out from the Queue.
Functions available in this module include:
maxsize – Number of items allowed in the queue.
empty() – Return True if the queue is empty, False otherwise.
full() – Return True if there are maxsize items in the queue. If the queue was initialized with maxsize=0 (the default), then full() never returns True.
get() – Remove and return an item from the queue. If the queue is empty, wait until an item is available.
get_nowait() – Return an item if one is immediately available, else raise QueueEmpty.
put(item) – Put an item into the queue. If the queue is full, wait until a free slot is available before adding the item.
put_nowait(item) – Put an item into the queue without blocking. If no free slot is immediately available, raise QueueFull.
qsize() – Return the number of items in the queue.
Code implementations are as below:
# Initializing a stack
stack = LifoQueue(maxsize=3)
# qsize() show the number of elements in the stack
print(stack.qsize())
Output
0
put()
#put() function to push element in the stack
stack.put('a')
stack.put('b')
stack.put('c')
print("Full: ", stack.full())
print("Size: ", stack.qsize())
Output
Full: True
Size: 3
get()
#get() function to pop element from stack in LIFO order
print('\nElements popped from the stack')
print(stack.get())
print(stack.get())
print(stack.get())
Output
Elements popped from the stack
c
b
a
Empty stack
print("\nEmpty: ", stack.empty())
Output
Empty: True
SORTING
Sorting is basically organizing data in a certain order.
Python sorting algorithms
- Merge sort
- Buble sort
- Insertion sort
- Selection sort
Insertion sort
Insertion sort is appropriate for snall data which is partially sorted.
To sort items in ascending order:
1.Iterate from arr[1] to arr[N] over the array.
2.Compare the current element (key) to its predecessor.
3.If the key element is smaller than its predecessor, compare it to the elements before. Move the greater elements one position up to make space for the swapped element.
An example code is as below:
def insertionSort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i-1
while j >= 0 and key < arr[j] :
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
# Code to test above
arr = [12, 11, 13, 5, 6]
insertionSort(arr)
for i in range(len(arr)):
print ("% d" % arr[i])
Output
5 6 11 12 13
MERGE SORT ALGORITHM
This method uses divide and conquer technique.That is it divides the problem into smaller problems, when the solutions for each problem is arrived at the solutions are combined to give the solution for the bigger problem.
# MergeSort in Python
def mergeSort(array):
if len(array) > 1:
# r is the point where the array is divided into two subarrays
r = len(array)//2
L = array[:r]
M = array[r:]
# Sort the two halves
mergeSort(L)
mergeSort(M)
i = j = k = 0
# Until we reach either end of either L or M, pick larger among
# elements L and M and place them in the correct position at A[p..r]
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
# When we run out of elements in either L or M,
# pick up the remaining elements and put in A[p..r]
while i < len(L):
array[k] = L[i]
i += 1
k += 1
while j < len(M):
array[k] = M[j]
j += 1
k += 1
# Print the array
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)
BUBBLE SORT
It compares two adjacent elements and swaps them until they are in the intended order.
# Bubble sort in Python
def bubbleSort(array):
# loop to access each array element
for i in range(len(array)):
# loop to compare array elements
for j in range(0, len(array) - i - 1):
# compare two adjacent elements
# change > to < to sort in descending order
if array[j] > array[j + 1]:
temp = array[j]
array[j] = array[j+1]
array[j+1] = temp
data = [-2, 45, 0, 11, -9]
bubbleSort(data)
print('Sorted Array in Ascending Order:')
print(data)
SEARCHING ALGORITHMS
We do search every day.It is basically retrieving sth from where it was stored . Searching in this case means retrieving it be it from a list,stack,etc
There are a number of searching algorithms including:
-binary search
-linear search
-interpolation search
-exponential search.
Linear search
It involves sequential searching for a element beginning with the first element until the desired element is found.
# Linear Search in Python
def linearSearch(array, n, x):
# Going through array sequencially
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)
Binary search
It is used to search for an element in a sorted array.It can be implemented in a iterative method or a recursive method.
Iterative method
# Binary Search in python
def binarySearch(array, x, low, high):
# Repeat until the pointers low and high meet each other
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")
Recursive method
# Binary Search in python
def binarySearch(array, x, low, high):
if high >= low:
mid = low + (high - low)//2
# If found at mid, then return it
if array[mid] == x:
return mid
# Search the left half
elif array[mid] > x:
return binarySearch(array, x, low, mid-1)
# Search the right half
else:
return binarySearch(array, x, mid + 1, high)
else:
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")
Top comments (0)