An algorithm is a procedure used for solving a problem or performing a computation. Algorithms act as an exact list of instructions that conduct specified actions step by step in either hardware- or software-based routines.
Machine learning is a good example of an algorithm, as it uses multiple algorithms to predict outcomes without being explicitly programmed to do so. Machine learning uses supervised learning or unsupervised learning. In supervised learning, data scientists supply complex algorithms with labeled training data and define the variables they want the algorithm to assess for correlations. Both the input and the output of the algorithm are specified.
Below are the top basic algorithms everyone should learn:
1. Quick Sort
QuickSort is a Divide and conquer algorithm. It picks an element as a pivot and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivots in different ways.
Always pick the first element as a pivot.
Always pick the last element as a pivot (implemented below)
Pick a random element as a pivot.
Pick median as the pivot.
The key process in quickSort is a partition(). The target of partitions is, given an array and an element x of an array as the pivot, put x at its correct position in a 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.
Where it is used:
It is used in operational research and event-driven simulation. Numerical computations and in scientific research, for accuracy in calculations most of the efficiently developed algorithm uses priority queue and quick sort is used for sorting
2. Merge Sort
The Merge Sort algorithm is a sorting algorithm that is based on the Divide and Conquer paradigm. In this algorithm, the array is initially divided into two equal halves and then they are combined in a sorted manner.
If the array becomes empty or has only one element left, the dividing will stop, i.e. it is the base case to stop the recursion. If the array has multiple elements, split the array into halves and recursively invoke the merge sort on each of the halves. Finally, when both halves are sorted, the merge operation is applied. Merge operation takes two smaller sorted arrays and combines them to eventually make a larger one.
Where it is used?
If we want the relative order of equal elements after sorting the data to be preserved, merge sort would be the preferred choice since merge sort is a stable sorting algorithm
The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from the unsorted part and putting it at the beginning.
The algorithm maintains two subarrays in a given array.
The subarray which already sorted.
The remaining subarray was unsorted.
In every iteration of the selection sort, the minimum element (considering ascending order) from the unsorted subarray is picked and moved to the sorted subarray.
Where it is used?
Selection Sort is used when: Only O(N) swaps can be made or is a requirement. Memory writing is costly in terms of time or hardware durability.
When the array is NOT partially sorted. When we have memory usage constraints. When a simple sorting implementation is desired. When the array to be sorted is relatively small.
4. Bubble Sort
Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order. This algorithm is not suitable for large data sets as its average and worst-case time complexity is quite high.
Where it is used:
It is used to detect a very small error in almost-sorted arrays and fix it with just linear complexity (2n)
A real-world example of a bubble sort algorithm is how the contact list on your phone is sorted in alphabetical order. Or the sorting of files on your phone according to the time they were added.
Insertion sort is a simple sorting algorithm that works similar to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.
This algorithm is one of the simplest algorithms with a simple implementation
Basically, Insertion sort is efficient in small we must ensure that the list is sorted to search an element into some list using the binary search technique
Insertion sort is adaptive in nature, i.e. it is appropriate for data sets that are already partially sorted.
Where it is used:
When the array is nearly sorted - since insertion sort is adaptive. When we have memory usage constraints. When a simple sorting implementation is desired. When the array to be sorted is relatively small.
conquer search is the search technique that works efficiently on sorted lists. Hence, to search an element into some list using the binary search technique, we must ensure that the list is sorted.
Binary search follows the divide and conquer approach in which the list is divided into two halves, and the item is compared with the middle element of the list. If the match is found then, the location of the middle element is returned. Otherwise, we search into either of the halves depending upon the result produced through the match.
Where it is used:
A binary search is an algorithm that is best applied to search a list when the elements are already in order or sorted.
Huffman coding is a lossless data compression algorithm. The idea is to assign variable-length codes to input characters, the lengths of the assigned codes are baswhich ed on the frequencies of corresponding characters. The most frequent character gets the smallest code and the least frequent character gets the largest code.
The variable-length codes assigned to input characters are Prefix Codes, means the codes (bit sequences) are assigned in such a way that the code assigned to one character is not the prefix of code assigned to any other character. This is how Huffman Coding makes sure that there is no ambiguity when decoding the generated bitstream.
Where it is used:
It is used for lossless data compression. The process of finding or using such a code proceeds using Huffman coding, an algorithm developed by David A.
Breadth-First Search
It is a vertex-based technique for finding the shortest path in the graph. It uses a Queue data structure that follows first in first out. In BFS, one vertex is selected at a time when it is visited and marked then its adjacent are visited and stored in the queue. It is slower than DFS.
Where it is used:
The breadth-first search or BFS algorithm is used to search a tree or graph data structure for a node that meets a set of criteria.
Depth-First Search
It is an edge-based technique. It uses the Stack data structure and performs two stages, first visited vertices are pushed into the stack, and second if there are no vertices then visited vertices are popped.
Where it is used:
Depth-first search is used in topological sorting, scheduling problems, cycle detection in graphs, and solving puzzles with only one solution, such as a maze or a sudoku puzzle.
The Tech Platform
コメント