What are the Important Data Structures and Algorithms in Python?

Last updated on 30th Dec 2021, Blog, General

(5.0) | 19674 Ratings 953

Share:

A data structure is a collection of data type ‘values’ which are stored and organized in such a way that it allows for efficient access and modification. When we think of data structures, there are generally four forms: Linear: arrays, lists. Tree: binary, heaps, space partitioning etc.

• Introduction to Data Structures
• Algorithm
• Elements of a Good Algorithm
• Algorithm Classes
• Tree Traversal Algorithms
• Sorting
• Searching Algorithm
• Algorithm Analysis
• Why Learn DSA?
• Conclusion

Introduction to Data Structures:

Built-in data-structures:

Lists: stores indexed elements that are mutable and may contain duplicate items

Tuples: stores indexed, immutable elements that can have duplicate copies

dictionary: store key-value pairs that are changeable

Set: Contains unordered, unique elements that are mutable




User-defined data-structures:

Arrays: Similar to lists, but store elements of a single type

Stack: Linear LIFO (last-in-first-out) data structure

Queues: Linear FIFO (First-In-First-Out) Data Structure

Trees: Non-linear data structures with roots and nodes

Linked Lists: Linear data structures that are linked by pointers

Graph: Store a collection of points or nodes along an edge

HashMaps: In Python, HashMaps are Similar to Dictionary

Algorithm:

What are algorithms?

Algorithms are rules or instructions that are formulated in a finite, sequential order to solve problems and obtain the required results. They give pseudocode for problems and can be implemented in many languages ​​because they are not language-specific.




How do you write algorithms?

Algorithms are usually written as a combination of a user-understandable language and some common programming languages. They are usually written in stages, but it is not always necessary to do so. There are no separate rules for building an algorithm but you need to keep the following in mind:

• find out what the exact problem is
• Decide where you want to start
• Decide where you want to stop
• prepare intermediate steps
• review your steps

For example, if you need to design an algorithm to check whether a student has passed an exam or not, you can follow the given steps:

• Step 1: Get Started
• Step 2: Two variables x, y. declare
• Step 3: Marks obtained by the student as x. store in
• Step 4: Set the minimum passing score as y. store in
• Step 5: Check whether x is greater than or equal to y. If yes, return “pass” otherwise return “fail”
• Step 6: Stop

However, you can manipulate the steps to your liking. For example, you can assign values ​​to variables in step 2 instead of taking steps 3 and 4. In this way, a problem can have multiple solutions and it is up to the problem and the programmer to choose the most feasible and reliable solution. ,

Elements of a Good Algorithm:

• Steps should be limited, clear and understandable
• There should be clear and precise description of inputs and outputs
• Each stage must have a defined output that depends only on the inputs in that stage or the previous steps
• The algorithm needs to be flexible enough to mould it to allow for multiple solutions
• Steps should use general programming fundamentals and not be language-specific

Algorithm Classes:

• Class description
• Divide and conquer

Divides the problem into sub-parts and solves each one separately

Dynamic programming

Divides the problem into sub-parts, remembers the results of the sub-parts and applies it to equal parts

Greedy algorithm

Involves taking the easiest step while solving a problem without worrying about the complexity of future steps Continuing with this Data Structures and Algorithms in Python article, let’s take a look at some of the important algorithms like Tree Traversal Algorithm, Search Algorithm, Sorting Algorithm, etc.

Tree Traversal Algorithms:

Tree Traversal Algorithm:

Trees in Python are non-linear data structures that have roots and nodes as mentioned earlier. Tree traversal refers to viewing each node in the tree exactly once to update or check it. Take a look at the tree shown below:

• Tree-data structures and algorithms in python-ACTE
• Depending on the order in which the nodes are visited, there can be three types of tree traversal:
• Pre-order traversal (route-left-right)
• In-order traversal (left-route-right)
• Post-order traversal (left-right-route)
• Before creating a function for each of these traversals, you’ll need to create a Node class and build the tree using the following piece of code (run all functions with it):
• # Creating a node class
• class node:
• def __init__(self, val):
• self.child left = none
• self.childhood = none
• self.nodedata = val
• # Creating an instance of the Node class to build the tree shown in the image above
• root = node(1)
• root.child left = node(2)
• root.childright = node(3)
• root.child left.child left = node(4)
• root.child left.child right = node(5)
• In-order traversal:
• In-order traversal means traversing the tree in such a way that you first visit the left nodes and then the root and then the right nodes. You start your traversal from all nodes in the left subtree, then move to the root and finally the right subtree.
• Step 1: Traverse through the nodes present in the left subtree
• Step 2: Go to the Root Node
• Step 3: Traverse the Right Subtree
• In-order function:
• def inord(root):
• if root:
• InOrd(root.childleft)
• print(root.nodedata)
• InOrd(root.childright)
• inord (root)
• When you run this function with the code shown earlier, you will get an in-order traversal for the given binary tree.
• Inorder-Data Structures and Algorithms in Python
• Pre-Order Traversal:
• In pre-order traversal, the root node is visited first, followed by the left subtree, and then the right subtree. So, in the above example, you first go to node 1 followed by node 2, which we move to the left of node 1. Then, you should go to the left of node 2 and go to node 5 after node 4. With this, the root and left subtree are done and hence, you need to move to the right subtree.
• The algorithm for pre-order traversal will be as follows:
• Step 1: Go to the Root Node
• Step 2: Traverse through the nodes present in the left subtree
• Step 3: Traverse the Right Subtree
• Pre-order function:
• def preorder (root):
• if root:
• print(root.nodedata)
• preOrd(root.childleft)
• preOrd(root.childwrite)
• preorder (root)
• The post-order traversal starts from left to right and ends at the root. In the above example, you go to node 4 and then go right to node 5. Once this is done, you need to go to the root i.e. node 2. With this, the left subtree is complete, so you need to move to the right subtree and finally the root.
• post-order traversal-edureka
• The algorithm for postorder traversal would be as follows:
• Step 1: Traverse through the nodes present in the left subtree
• Step 2: Traverse the Right Subtree
• Step 3: Go to the Root Node
• Post-order function:
• def postord (route):
• if root:
• postOrd(root.childleft)
• postOrd(root.childWrite)
• print(root.nodedata)
• postorder (route)

Sorting:

Sorting data is a real-time problem and requires multiple sorting algorithms to solve it. So moving forward with this Data Structures and Algorithms in Python article, let us take an in-depth look at the sorting algorithms in Python.

Sorting Algorithm:

Sorting algorithms are used to sort the data in a given order. Sorting algorithms can be classified into five types which are:

• Merge sort
• Bubble shot
• Insertion sort
• Selection sort
• Shell sort

Merge sort:

Merge sort algorithm follows divide and conquer rule. Here, the given list of items is first divided into smaller lists until it reaches a point where each list contains exactly one item. By default, a list containing one item will be sorted and the merge sort algorithm then compares adjacent lists and rearranges them in the desired order. This process is done recursively until it reaches a point where only one, sorted list exists.

Merge Sort Algorithm:

Step 1: Check if the list contains more than one item; If yes, split the list into two parts, otherwise the list is sorted.

Step 2: The list is to be split repeatedly until each sub-list has only one element left.

Step 3: Recursively merge the sub-lists by arranging them in the given order until you get a single sorted list.




Bubble Shot:

Bubble sort is a comparison algorithm that first compares and then sorts adjacent elements if they are not in the specified order.

Bubble Sort Algorithm:

Step 1: Starting from the first element i.e. the element at index 0, progressively compare adjacent elements of an array

Step 2: If the current element and the next element are not in the specified order, swap the elements

Step 3: If the current element and the next element are in the specified order, move to the next element




Insertion Sort:

Insertion sort selects one element of the given list at a time and places it exactly where it is to be placed.

Insertion Sort Algorithm:

Step 1: Compare the first element with the next element (key) and swap them if the leftmost element and the head element are not in order.

Step 2: Take the next element (key) and if a new key element needs to be repositioned, move the elements of the sorted list to the right until a suitable space is created for the element in question.

Step 3: Repeat step 2 until all the elements of the given list are sorted.




Develop Your Skills with Advanced Python Certification Training
Weekday / Weekend BatchesSee Batch Details

selection sort:

The selection sort algorithm splits the given list into two halves where the first half would be the sorted list and the second would be an unsorted list. First, the sorted list is empty and all the elements to be sorted are present in the unsorted list.

Selection Sort Algorithm:

Step 1: Make the first element the minimum and compare it with the next element. If the next element is less than the selected element, mark it as minimum and compare it to the next element. Repeat this process until you have compared all the elements of the sorted list.

Step 2: Put the minimum in the sorted array (it becomes the first element of the sorted array)

Step 3: Increment the position of the counter to point at the first element of the sorted array and repeat steps 1 and 2 for all elements of the sorted array




Shell Sort:

The shell sort algorithm allows you to sort elements that are different from each other. The basic order of sorting the elements follows the order n/2, n/4,…, 1 where n is the number of elements present in the sorted list. For example, if you have a list of 8 elements, then the length of that list will be divided by 2 i.e. 8/2 = 4. Now, the first element will be compared with the element at index number 4 and then, the interval 8 will be generated when divided by 4. This time the gap will be 2 and the elements located at these gaps will be compared. Finally, 8/8 = 1, so adjacent elements will be compared and sorted. (For odd number lists, the whole part of the quotient will be taken as the interval)

Shell Sort Algorithm:

Step 1: Set the number of elements to 2. find the value of the interval by dividing by

Step 2: Split the given array into smaller sub-arrays with equal spacing intervals

Step 3: Sort the sub-arrays, using insertion sort

Step 4: Repeat steps 1, 2 and 3 until the whole array is sorted

Searching Algorithm:

Looking for Algorithms:

Search algorithms are used to find or fetch certain elements present in some given dataset. There are many types of search algorithms like linear search, binary search, exponential search, interpolation search etc.

Linear Search:

Linear Search Algorithm is used to find a given element sequentially by comparing it with each element of the given array. It is one of the simplest search algorithms but very important for understanding other sorting algorithms.

Linear Search Algorithm:

Step 1: Create a function that will accept the data list, the length of the list, and the key element

Step 2: If any element in the given list matches the leading element, return the corresponding index number

Step 3: If the element is not found, -1 . return




Binary search:

Binary search is used to find a given element in an ordered array using the Decrease and Conquer algorithm. Here, the key is first searched for by comparing it with the middle element and then dividing the array in half. The left half is searched if the element to be searched is smaller than the middle element and vice versa. The appropriate sub-arrays are then split in half and the process is repeated again.

Binary Search Algorithm:

Step 1: Compare Key to Middle Element

Step 2: If matches, return the middle index value

Step 3: If the key element is greater than the middle element, then find the key element to the right of the middle element, otherwise find the left of it

Algorithm Analysis:

Algorithms can be analysed before and after their implementation. These analyses are called a priori analysis and a posterior analysis. A priori analysis (theoretical analysis): The efficiency of an algorithm is measured by assuming that all other factors are constant and do not affect the implementation of the algorithm.

A posteriori analysis (empirical analysis): Algorithms are executed on some computer after being implemented using some programming language. So in this analysis, real values ​​such as time complexity or execution time of an algorithm until it completes the task, space complexity or the space required by the algorithm for its complete life cycle, etc. are collected. I hope you are clear about everything I have shared with you in this tutorial. This brings us to the end of our article on Data Structures and Algorithms

Why Learn DSA?

Write optimised and scalable code – Once you have knowledge about different data structures and algorithms, you can determine which data structure and algorithm to choose in different situations.

Effective use of time and memory – Having knowledge about data structures and algorithms will help you write code that runs faster and requires less storage.

Better Job Opportunities – Data Structure and Algorithms questions are frequently asked in job interviews of various organisations including Google, Facebook, etc

Conclusion:

Data structures vary based on variability and ordering. Mutability refers to the ability of an object to change after its creation. Mutable objects can be modified, added or removed after their creation, whereas immutable objects cannot be modified after their creation. The order, in this context, is related to whether the position of the element can be used to access the element.

Data structures are a way of being organised so that they can be accessed more efficiently depending on the situation. Data structures are the basic elements of any programming language around which a program is built. Python helps in learning the basics of these data structures in a simpler way as compared to other programming languages.

Lists, sets, and tuples are basic data structures in the Python programming language. One of the distinguishing points between data structures is variability, which is the ability of an object to change after it has been created. Lists and tuples are the most useful data types, and they can be found in almost every Python program.