Algorithms in Python

Types of Algorithms in Python

We can be implement wide range of algorithms in Python, but some of the most used python algorithms examples are graph algorithms, tree traversal, searching and sorting.

• Tree traversal algorithms are implemented on trees, are used to access/visit all the nodes of the tree, involve starting traversing the tree from the root node, then go to further nodes according to the traversal type. Tree traversal can be in order in which we traverse from nodes to the branches or the edges, or we can also do it oppositely from branches or edges to the root.

Complexity: Time complexity of tree traversal algorithms is O(n), where n is number of nodes in tree.

• Sorting is basically arranging the data in a particular format, sorting algorithms help us in arranging the data. There are multiple sorting algorithms in Python such as bubble sort, merge sort, quick sort, insertion sort, selection sort and shell sort. Every sorting algorithm has its own features.

Complexity: Every sorting algorithm has different time complexity, like best case complexity of quick and merge sort is O(nlogn), and best case complexity of selection sort is O(n^2)

• Searching algorithms in Python are used for searching and fetching the elements from the data strcuture. Searching algorithms have two variations binary search and linear search.

Complexity: Time complexity of linear search is O(n), and binary search has O(logn) time complexity

• Graph traversal algorithms in Python are used for graph traversal, which includes visiting/ accessing all the nodes of the graph, depth-first search (DFS) and breadth-first search(BFS) are two graph traversal algorithms.

Complexity: Time complexity of BFS and DFS is O(V + E)

Tree traversal algorithms

Tree traversal algorithms in Python is a process of visiting every node of a tree, starting from the root of the tree. Three algorithms are available which can be used for tree traversal:

• In-order traversal: In-order traversal includes first visiting the left subtree, then the root, then the right subtree of the node will be visited.
• Pre-order traversal: Pre-order traversal includes first visiting the root, then the left subtree of the root, and then the right subtree of the node will be visited.
• Post-order traversal: Post-order traversal includes first visiting the left subtree, then the right subtree of the node will be visited and then the root will be visited.

Python Implementation of tree traversal algorithms:

Output:

Sorting algorithm

Sorting algorithms in Python provide us with a way of arranging the elements in a particular manner. Sorting helps us in making the collection of data more readable and it also helps in optimizing the searching of an element. Below are the different sorting algorithms in Python:

• Bubble sort: Bubble sort is considered as the simplest sorting algorithm. It sorts the data by swapping the adjacent elements repeatedly, bubble sort is not a good sorting algorithm for the large size of data, as it has its complexity is high.

• Merge Sort – The merge sort algorithm works on the divide and conquer principle, merge sort divides the arrays in two halves recursively, then it sorts both the halves independently, then merges the elements of both halves.

• Insertion Sort – The Insertion sort algorithm works similarly to arranging the playing cards. It traverses the unsorted elements and inserts elements one by one in the sorted section at the correct position.

• Selection Sort – It is a comparison-based simple sorting algorithm that divides the list of elements into two parts sorted and unsorted part, and it searches for the smallest element from unsorted elements and inserts it into the sorted list of the elements. This process is continued until we get the complete list of sorted elements.

• Quick Sort: Quick sort algorithm also works on the divide and conquer algorithm, it is an efficient sorting algorithm, it divides the element into the smaller part based on the pivot element, and then sort every part independently.

Searching algorithms

Searching algorithms in Python find and retrieve the element from the list of the elements. There are two types of search algorithms in Python:

• Linear search: Linear search traverses every element of an array one by one and compares the target element to every element. And when the target is found in the array then it will return.

Linear Search Implementation in Python:

Output:

• Binary Search: It searches the element by repeatedly dividing the list into half. It compares the target element with the middle element, if the target is less than the middle element, then it will move towards the left otherwise it will move towards the right part, and this process will be continued until we find the element in an array.

Binary Search Implementation in Python:

Output:

Graph algorithms

Graph traversal includes visiting all the nodes of the graph. There are two graph traversal algorithms in Python:

• Depth-First Search(DFS): This algorithm traverse graph in depthward manner. When an iteration reaches the dead end of the graph, then it will be backtracked and it will go to the next vertex available in the stack and start traversing from there, this will be continued until all the nodes of the graph are visited.

DFS Python Implementation:

Output:

• Breadth-First Search: This algorithm traverses the graph in a breadthward manner. Queue data structure is used in BFS, it visits the vertex mark it visited and then goes to its adjacent vertices and stores it in a queue.

BFS Python Implementation:

Output:

Steps to write an efficient Algorithm

Below are the steps to be followed for writing an efficient algorithm:

1. Understand the Problem: It is the first and foremost step of writing an efficient algorithm, forst we need to understand what the problem expects, it also involves analysing the constraints, requirements and some input and output test cases.
2. Selecting the data structure: The Next step is to choose the data structure which suits best our problem statement, and we have to choose the data structure which we most efficient in terms of time and space for our algorithm.
3. Analyse the space and time complexity: Our main is to always choose the algorithm which will be optimized in terms of time and space.
4. Design and Test the Algorithm: Based on the requirements and understanding, design the algorithm with the help of flowcharts and pseudocodes generate some test cases and test your algorithm on that.
5. Algorithm Optimization: Try to find some optimizations for the algorithms, remove unnecessary lines of code, and try to find more time and space-optimized solutions.
6. Document the Algorithm: Last step algorithm documentation includes providing a clear explanation of the inputs, output, logic and complexitiies.

Is Python Good for Developing and Implementing Algorithms?

Yes, Python is a good programming language for the implementation of the development of algorithms, in spite of this it can handle every aspect of the algorithm very smoothly.

Python programming language is considered as the best and most powerful language for the algorithm implementation. The syntax of Python is easy and simple which looks like a pseudocode of the algorithm, and the pseudo-code is not at all language dependent. And it also allows users to focuse more on solving and understanding the problem instead of focusing on learning and memorizing the syntax.

And it is also good in terms of dealing with data structures and a wide range of libraries are also provided by it which also makes it best for the machine learning and data science domains.

Explore Scaler Topics Python Tutorial and enhance your Python skills with Reading Tracks and Challenges.

Learn More

• Difference Between BFS and DFS.