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

General Introduction

Computers store and process data with an extra ordinary speed and accuracy. So, it is highly essential that the data is stored efficiently and can be accessed fast. Also, the processing of data should happen in the smallest possible time, but without losing the accuracy.
Data structures deal with how the data is organized and held in the memory, when a program processes it. It is important to note that, the data that is stored in the disk as part of persistent storages (like relational tables) are not referred as data structure here.
An Algorithm is step by step set of instruction to process the data for a specific purpose. So, an algorithm utilizes various data structures in a logical way to solve a specific computing problem.

Python Data Structure

Python is a high-level, interpreted, interactive and object-oriented scripting language using which we can study the fundamentals of data structure and algorithms in a simpler way as compared to other programming languages.
In this article we are going to study a short overview of some frequently used data structures in general and how they are related to some specific python data types. There are also some data structures specific to python which is listed as another category.
Context
The various data structures in computer science are divided broadly into two categories shown below. We will discuss about each of the below data structures in detail in subsequent chapters.

Liner Data Structures

These are the data structures which store the data elements in a sequential manner.

Array − It is a sequential arrangement of data elements paired with the index of the data element.
Linked List − Each data element contains a link to another element along with the data present in it.
Stack − It is a data structure which follows only to specific order of operation. LIFO(last in First Out) or FILO(First in Last Out).
Queue − It is similar to Stack but the order of operation is only FIFO(First In First Out).
Matrix − It is two dimensional data structure in which the data element is referred by a pair of indices.

Non-Liner Data Structures

These are the data structures in which there is no sequential linking of data elements. Any pair or group of data elements can be linked to each other and can be accessed without a strict sequence.
Binary Tree − It is a data structure where each data element can be connected to maximum two other data elements and it starts with a root node.
Heap − It is a special case of Tree data structure where the data in the parent node is either strictly greater than/ equal to the child nodes or strictly less than it’s child nodes.
Hash Table − It is a data structure which is made of arrays associated with each other using a hash function. It retrieves values using keys rather than index from a data element.
Graph − It is an arrangement of vertices and nodes where some of the nodes are connected to each other through links.

Python Specific Data Structures

These data structures are specific to python language and they give greater flexibility in storing different types of data and faster processing in python environment.
List − It is similar to array with the exception that the data elements can be of different data types. You can have both numeric and string data in a python list.
Tuple − Tuples are similar to lists but they are immutable which means the values in a tuple cannot be modified they can only be read.
Set - Set is a mutable and unordered collection of unique elements. It can permit us to remove duplicate quickly from a list.

Dictionary − The dictionary contains Key-value pairs as its data elements.

Python Algorithms

As you already know algorithms are instructions that are formulated in a finite and sequential order to solve problems.

When we write an algorithm, we have to know what is the exact problem, determine where we need to start and stop and formulate the intermediate steps.

There are three main approaches to solve algorithms:

Divide et Impera (also known as divide and conquer) → it divides the problem into sub-parts and solves each one separately
Dynamic programming → it divides the problem into sub-parts remembers the results of the sub-parts and applies it to similar ones
Greedy algorithms → involve taking the easiest step while solving a problem without worrying about the complexity of the future steps
Tree Traversal Algorithm Trees in python are non-linear data structures. They are characterized by roots and nodes. I take the class I constructed before for the binary tree.
Tree Traversal refers to visiting each node present in the tree exactly once, in order to update or check them.
There are three types of tree traversals:
In-order traversal → refers to visiting the left node, followed by the root and then the right nodes.
Here D is the leftmost node where the nearest root is B. The right of root B is E. Now the left sub-tree is completed, so I move towards the root node A and then to node C.

On the other hand:

Searching Algorithms

Linear Search Start from the leftmost element of arr[] and one by one compare x with each element of arr[]
If x matches with an element, return the index.
If x doesn’t match with any of the elements, return -1.
Binary Search Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise, narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.

Sorting Algorithms

Selection Sort. The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning. In every iteration of selection sort, the minimum element (considering ascending order) from the unsorted subarray is picked and moved to the sorted subarray.
Bubble Sort Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.
Merge Sort Like QuickSort, Merge Sort is a Divide and Conquer algorithm. It divides the input array into two halves, calls itself for the two halves, and then merges the two sorted halves. The merge() function is used for merging two halves. The merge(arr, l, m, r) is a key process that assumes that arr[l..m] and arr[m+1..r] are sorted and merges the two sorted sub-arrays into one.
QuickSort Like Merge Sort, QuickSort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways. Always pick first element as pivot. The key process in quickSort is partition(). Target of partitions is, given an array and an element x of array as pivot, put x at its correct position in sorted array and put all smaller elements (smaller than x) before x, and put all greater elements (greater than x) after x. All this should be done in linear time.
ShellSort ShellSort is mainly a variation of Insertion Sort. In insertion sort, we move elements only one position ahead. When an element has to be moved far ahead, many movements are involved. The idea of shellSort is to allow the exchange of far items. In shellSort, we make the array h-sorted for a large value of h. We keep reducing the value of h until it becomes 1. An array is said to be h-sorted if all sublists of every hth element is sorted.