What Are Data Structures and Algorithms in Python?
Data structures are a group of data elements put together under a single name. They represent a particular way of storing and organizing data in a computer to use them efficiently, whenever required. We can characterize data structures based on how we keep individual data and what operations are available for accessing and manipulating the data.
Data structures are of two types:
.png)
Primitive data structures are the most basic form of representing data. They contain pure and simple data. The four primitive data types in Python are:
Integer
Integer data types represents a whole number ranging from negative infinity to infinity – the same way we define integers in mathematics. You can store both positive and negative values, even zero. Here is an example of how to define integers in Python. Python automatically understands the data type defined; even when the data type name is not mentioned. The credit for this goes to the dynamic nature of the Python programming language.
Float
The float data type is a floating-point number and is used to define rational numbers. Like int data type, you can define both positive and negative values, even zero. Here is an example of how to define integers in Python.
String
String data type refers to the collection of characters. If you want to use text, use a string. In Python, you can define a String using a single or double quote. Here is an example of how to define integers in Python.
Boolean
Boolean data type refers to truth statements. A variable of Boolean data type can have either of the two values – True or False. Here is an example of how to define integers in Python.
Non-primitive data does not store a single value but a collection or group of values. The built-in non-primitive data types in Python are:
List
List is a versatile data type in Python. It is a sequence in which elements are present, separated by a comma.
Tuple
Similar to a list, a tuple is another built-in data type but differs in two things. Firstly, tuples are immutable; once you define values in a tuple, you cannot make any changes. Secondly, we use parentheses to define the set of values in a tuple.
Dictionary
Dictionary is a data structure where we can store a pair of a key and value. Every key-value pair is separated by a colon (:), and consecutive items are stored by a comma.
Set
A set comprises of unique and unordered elements. To make it simpler, even if the element is present more than once, it will be counted once in the set list. We use a flower or curly braces to define elements in a set.
Many data structures are not available in Python. Through user-defined data structures, you can define those data structures and reflect their functionality. We can implement data structures directly in Python using:
A linked list is a linear data structure where elements are not linked explicitly in memory locations but linked with pointers. All linked list creates a series of node or a chain like structure. It is second mode preferred technique after array.
Stack
A stack is a linear data structure that uses the last in first out (LIFO) principle. That means the element inserted last is the first to be taken out. Stack supports push, pop, and peep operations.
Queue
A stack is a data structure that follows the first-in-first-out (FIFO) principle. That means the element inserted first is the first to be taken out. Stack supports insert, delete, and peep operations.
Tree
A tree is a non-linear data structure consisting of roots and nodes. The topmost base node is the root, and the elements present at the end of the tree are leaves.
Graph
A graph is a non-linear data structure consisting of nodes and edges. Nodes are known as vertices, and the lines connecting two nodes are generally called nodes.
HashMap
Hash Maps are indexed data structures and perform the same function as that performed by dictionary in Python. A hash map uses a hash function to compute index-key values into arrays.
An algorithm is a step-by-step approach followed in a sequential order to solve problems. They are not language-oriented; there is no particular language used to write algorithms.
There is no one way to write an algorithm—just as there is no one way to parent a child or roast a turkey. But there are incredible ways to do all three. Simply put, there is no hard and fast rule to write an algorithm. However, the following steps in the sequence are generally preferred by most of the programmers. Here are a few steps you must follow when writing an algorithm:
Step-1: Define the problem
Step-2: Decide where to start
Step-3: Decide where to stop
Step-4: Take care of intermediate steps
Step-5: Review and revise
Divide and Conquer: This class of algorithm involves dividing the problem into parts and calling the divided parts explicitly using recursive function until we obtain the desirable solution.
Dynamic Programming: Dynamic Programming or simply DP is an algorithmic approach used for solving a problem by breaking it down into simpler subproblems where the overall problem depends upon the optimal solution to its subproblems.
Greedy Algorithms: As the name suggests, this involves building solutions piece by piece and choosing the most lucrative. Simply put, we choose the easiest-step first without thinking over the complexities of the later steps.
Tree Traversal involves processing the data of a node exactly once in some order in a tree. Unlike an array or linked list, the tree is a non-linear data structure — a tree can be transverse in many ways.
Tree Traversal Algorithms are of two types:
As the name suggests, the transverse mode in a level-by-level fashion.
Pre-order Traversal –> <root><left><right>
In-order Traversal–> <left><root><right>
Post-order Traversal –> <left><right><root>
We use Sorting algorithms to sort data into some given order. The most common sorting algorithms include:
Bubble sort is a comparison algorithm that first compares and then sorts adjacent elements if they are not in the specified order.
Time Complexity: Ω(n)
Step 1: Starting from the first element indexed at 0 and comparing the next item in the sequence.
Step 2: While comparing, check whether the elements you are comparing are in order or not. If not, start swapping.
Step 3: After each swap, keep moving to the next element.
Selection Sort
The problem with bubble sort is that we have to swap multiple times, which is strenuous, time-consuming, and memory draining.
The Selection sort algorithm divides the given list into two halves – a sorted list and an unsorted list. The sorted list is empty, and all elements to sort are present in the unsorted list.
Time Complexity: Ω(n^2)
Insertion Sort: The insertion_sort() function starts by assuming that the first item is in its proper position. Next, an iteration is performed over the remaining items to insert each element into its right location within the sorted portion of the sequence.
It is not a fast-sorting algorithm because it uses nested loops to sort and is useful for only small data sets.
Time Complexity: Ω(n^2)
The merge sort algorithm uses the divide and conquer approach to sort the elements stored in a mutable sequence. The sequence of values is recursively divided into smaller sub-sequences until each value is present within its sub-sequences. The sub-sequences get merged back together to create a sorted sequence.
Time Complexity: Ω(nlogn)
When there is a need to find an element from a sequence, we use searching algorithms. The two most renowned searching algorithms are:
Linear Search
For finding elements within a list, we use a linear search algorithm. It checks each value presents in the sequence until it finds a match.
Binary Search
Make sure to sort all the elements. The value present at the first position is the lower bound, and the value present at the nth position is the upper bound.
If the value you are searching for is smaller than the mid-value, change the upper bound, and the mid-value becomes the upper bound.
If the value you are searching for is larger than the mid-value, change the lower bound, and the mid-value becomes the lower bound.
Time Complexity: O(logn)
Algorithms help in solving problems in a straightforward and tech-savvy way. Of course, a problem can have many different solutions, but not all are effective. How then are we to decide which solution is the most efficient for that problem? One approach is to measure the execution time. We can implement the solution by constructing a computer program using any preferable programming language of our choice.
Algorithm execution time depends on the amount of data processed. With the increase in data size, the execution time also increases. Second, the execution times vary depending on the type of hardware. With the use of a multi-processor multi-user system, the execution time of the program differs. Finally, the preference of programming language and compiler used to implement an algorithm impacts the execution time. Some compilers are just better at optimizing than others, and some languages produce better-optimized code than others.
Conclusion
Data structures store a collection of values but differ in how they organize and are handled. The choice of a particular data structure depends on the problem at hand. Some data structures work better than others. The process becomes seamless with practice and experience.
Research & References of What Are Data Structures and Algorithms in Python?|A&C Accounting And Tax Services
Source