Data Structure and Algorithms 102: Deep Dive into Data Structure and Algorithms

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")