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

kimutaielon — Tue, 28 Jun 2022 12:17:06 +0000

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

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

INTRODUCTION TO DATA STRUCTURES AND ALGORITHMS.

kimutaielon — Tue, 21 Jun 2022 06:02:14 +0000

Introduction to data structures and algorithms.

What is a data structure?
A data structure is a specialized format for organizing, processing, retrieving and storing data. Anything that can store data is called a data structure. Primitive data structures
include an integer, Float, Boolean, Char etc while complex data structures include linked lists,trees,graphs,stacks,queues etc.

What is an algorithm?
Algorithms are all about problem solving. An algorithm is a procedure used for solving a problem or performing a computation. Every algorithm must satisfy the following:

1.Input- There must be an external input to the algorithm.
2.Output- There algorithm must eventually give out at least one output.
3.Definiteness- Every step of the algorithm should be clear and well defined.
4.Finiteness- The algorithm should have finite number of steps.
5.Correctness- Every step of the algorithm must generate a correct output.
An algorithm must be efficient and use less memory. This performance is arrived at using time and space complexity.
TIME COMPLEXITY
Time complexity is the amount of time taken by an algorithm to run, as a function of the length of the input.
The different types of time complexities include:

Constant time – O (1) -Irrespective of the input size n, the runtime will always be the same.
Linear time – O (n) -This is when the running time increases linearly with the length of the input.
Logarithmic time – O (log n) -This is when it reduces the size of the input data in each step eg binary search tree.
Quadratic time – O (n^2) - This is where the running time increases non-linearly (n^2) with the length of the input.
Cubic time – O (n^3)
SPACE COMPLEXITY
The space complexity of an algorithm quantifies the amount of space taken by an algorithm to run as a function of the length of the input.
Space complexity differs from auxiliary space in that whereas space complexity quantifies the total space used by the algorithm, auxiliary space quantifies the extra space that is used in the algorithm apart from the given input.

Forem: kimutaielon

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

INTRODUCTION TO DATA STRUCTURES AND ALGORITHMS.