An Algorithm is essentially a finite set of instructions, which when executed produces a desired result. The calculation it perform could require some input data, or it could also require access to some resources depending on the application it serves. Algorithms are not new, as many people would perceive them to be. They date back to atleast ancient Babylonion era (around 2500 BC.) if not prior. As per wikipedia,
"Arithmetic algorithms, such as a division algorithm, was used by ancient Babylonian mathematicians c. 2500 BC and Egyptian mathematicians c. 1550 BC. Greek mathematicians later used algorithms in the sieve of Eratosthenes for finding prime numbers"
As of today, there are a ton of algorithms out there. Speaking specifically of programming language C++, if you have gone through the STL library, there are at least 105 major algorithms in STL itself. The thing with Algorithms is that you need to practice a lot to feel confidant. However, for the beginners, the most difficult conundrum is to determine where to start and which algorithms to master first. The plethora of algorithms out there for every niche tends to baffle the beginners. But there’s a good news for those already intimidated beginners. You surely need to learn a lot of algorithms, but you don’t need to know all of them to start working. We can classify all the algorithms into some bunch of sections. What you can do instead, is learn a few algorithms from each section and thus you’ll not be marooned on the island when someone asks you about algorithms.
Below is a list of ten algorithm classes in which all the algorithms from the STL library can be classified into and under each class, there are a handful of algorithms that you can befriend with for the time being. Also mentioned are the situations under which you will find those algorithms useful.
So, to start with, lets go through the list of ten algorithms classes (and one bonus class) that we will discuss here and then we will elaborate each one.
- Query a Value
- Query a Property
- Search a Value or a Range
Heap, in real life which can be represented as a tree where every node is smaller than its child or the node below it. Figure 1(a) shows how a heap might look like in real life. However, a heap in C++ is slightly different. Unlike in real life, heap in C++ can be represented like a tree where parent node is always larger than its children, as shown in figure 1(b).
To represent Heap in Memory, we can use an Array. To initialize an array, we simply add elements row-wise. Heap initialization is shown in figure 2. As seen in the figure, for a heap which appears like a tree, elements are stored in array in a row-wise manner.
At the moment, this array is merely a collection of integers (in given example). To make it a heap, we can call the STL algo make_heap.
To add a new element to the heap and bubble its way to its appropriate position, we use push_back(element) and then push_heap as shown below.
To pop something from a heap, we can only remove elements from one end which can only be largest element. To do so, we swap its position with the last element of the heap (which is probably the smallest element of the heap) & then pop it out. We use pop_heap and then pop_back as shown below.
NOTEIf pop_back is not called, then calling pop_heap() will cause all the largest elements fall in order at the end of the heap. This will cause heap to be sorted and this is the actual mechansm of sort_heap
Sorting a collection is basically rearranging the elements of a collection in a certain order depending on the criteria. There are lots of sorting algorithms. In STL, simplest sorting algorithm is Sort. This sorts the collection in ascending order.
When we need to sort only a subset of a collection, we can use partial_sort. This algorithm takes in, the beginning of the collection and the point up to where collection needs to be sorted.
When we need to know an element that would have been there, had the collection been sorted, we can do so by using nth_element algorithm.
When there are two sorted sub-collections that are adjacent to each other, however the entire collection as a whole is not sorted, we can use inplace_merge.
It is basically organizing a collection based on a predicate. One example could be a situation where a collection has mixed values of zeroes and ones but we need to partition the collection into two parts based on whether the element is a zero or a one as shown below.
we can use partition to put all the zeroes in the beginning and all the ones at the end. The point which creates the divide between the two regions is called “Partition Point”.
The algorithm which retrieves the partitioning point is called partition_point.
These are the algorithms which change the order of the elements of a collection without changing their values.
Rotate It is one algorithm where elements in the middle and end goes to the beginning and that is decided by where the middle points to as shown in the figure below.std::rotate()
ShuffleIt uses a random generator and reorganizes the collection randomly.std::shuffle()
Next_permutationElements can be compared to each other depending on their order which is similar to order of alphabets that appears in a Dictionary. By calling this algorithm, it will rearrange the elements of the collection in such a way that the new collection order is just the next order of permutation in respect of order of elements.
The figure shown below clarifies what the order means in this context.std::next_permutation()
Prev_permutationJust like Next_permutation, prev_permutation gives the previous order.std::prev_permutation()
Finally, reverse simply reverses the order of collection entirely.std::reverse()
Query a Value
Querying forms a fundamental class in algorithms as many times, we only need to know what value or property certain variable or objects have. This class has numeric algorithms which return a specific value (or No value as No values is also technically a value)
Count This algorithm counts the occurrence of an input value in a collection of elements and returns the occurrence as integer value. As shown in the figure, count(a) returns 3 as there are three times ‘a’ has occurred in the collection.std::count()
Accumulate / (Transform_) reduceAccumulate find the sum of all the elements of a collection and returns it. Reduce works just like accumulate except for the fact that it doesn’t take initial value (which certainly saves some overhead) and this algorithm can be parallelized which means, it can be programmed to utilize multiple cores of a microprocessor simultaneously (Obviously, if the microprocessor has multiple cores in the first place. No points for guessing that. :p).
Following figure shows how accumulate works.std::accumulate()
Transform_reduceTransform_reduce works same as reduce but it works on functions and templates. Its like the cousin twin brother who also happen to go and live abroad with his rich parent (poor reduce couldn’t afford all that ).std::transform_reduce()
Partial_sumPartial_sum is used to calculate sum of adjacent elements upto a given position in a collection of elements.
For instance, the element at position three will constitute of the sum of first two elements elements and the third element (which basically means sum of first three elements) as shown below.std::partial_sum()
Inclusive_scan / Transform_Inclusive_scanInclusive_scan performs the same functionality as partial_sum but can be parallelized. Exlusive_scan, on the other hand, doesn’t include the current element while calculating the sum upto that position. It only calculates up until that position as shown below.std::inclusive_scan()
Transform_inclusive_scan and Transform_exclusive_scan are applied on the functions and objects.std::transform_inclusive_scan()
Inner_productInner_product calculates product of corresponding elements of two collection before adding the sum. This could be hard to comprehend. To understand this, have a look on the figure below. First the corresponding elements of both the collections are multiplied to create a single collection having elements as the result of multiplication and then the sum of all the elements of that collection is taken which is given by inner_product algorithm.std::inner_product()
Adjacent_differenceThis algorithm calculates the difference of adjacent elements of a collection.std::adjacent_difference()
SampleThis algorithm randomly pick out specified number of elements from a collection using a random generator.std::sample()
Query a Property
This class of algorithm proves extremely useful for day to day basis. One can query a property on one collection as well as on two ranges.
Following is a list of algorithms used to query a property on one collection.
All_ofTakes a predicate and a collection and returns TRUE (boolean value) if all the elements satisfy the property (predicate)
Any_ofReturns TRUE if any of the element of the collection satisfy the condition (property/predicate)
None_ofReturns TRUE if none of the element of the collection satisfy the property.
Following is a list of algorithms used to query property on two ranges where the idea is to compare two ranges.
EqualIf, given two ranges, all the elements are same in same order in both the ranges (or collection) and both the collections have same size, the algorithm returns a boolean true
Is_permutationIf two collections have same size and same elements but Not in same order, then this algorithm returns a boolean true.
Lexicographical_compareGiven two collection, this algorithm returns true if the first collection is smaller in order than the second collection.
MismatchThis algorithm matches two collections and stops at the point where two collections differ which is a way gives back the first point of mismatch.
Search Value or Range
When searching for a value, algorithms are broadly classified into two groups – Sorted and Unsorted.
This group consist of two algorithms namely find and adjacent_find which are both briefed below.
FindWhen we need to find something in a collection, we can call this algorithm and it returns the position of the searched item in the collection if the searched item is present in the collection. Else, it returns Null.
Adjacent_findWhen we need to find two consecutive occurrence of a value, we can use this algorithm. For instance, if we have to find where in a collection of numbers, two consecutive ‘3’ appears, we can use this algorithm. This algorithm returns the position of first element and the next element is adjacent to the returned position ( quite obviously)
In a sorted collection, all the occurrences of a same value are going to lie together, adjacent to each other. Hence, they form like a subrange.
Equal_rangeThis algorithm returns the position of of the sub-range that we intend to find in a sorted collection.
Lower_bound / upper_boundIf we have to add another element of a value which already exist in a sorted collection, we can either add the element on the left of the existing element ( or group of elements) or on the right of element. To add an element to the left of an existing element, we can use this algorithm which returns the position where to insert the new element. Upper_bound returns the position which lies on right of the existing element. This can be better explained using figure shown below.
Binary_searchThis algorithm returns a boolean True if it finds the item we are looking for in the collection. It performs Binary Search to find the item but it doesn’t return the position of the item, if the item is found. It only returns a confirmation in the form of boolean True or False.
The Search can be performed for a range of values (also called as sub-range) as well.
SearchThis algorithm returns the first occurrence of a sub-range in a collection. It basically gives the position where the sub-range starts.
Find_endThis algorithm returns the Last occurrence of the sub-range in a collection. In a way, this is opposite of search algorithm.
Find_first_ofIf you want to search the first occurrence of any of the value of the small sub-range in a collection, we can use find_first_of.
A set in C++ is actually just a sorted collection. It can be a Suit-set which happen to be sorted or it can be sorted-vector. The operation on sets look very similar to mathematical operation on sets.
Set_differenceThis algorithm returns what elements which are present in first collection but Not in second collection. This has linear complexity
Set_intersectionThis algorithm returns the elements which are common to both first and second collection.
Set_unionThis algorithm returns the combined elements of both first and second collection.
Set_symmetric_differenceThis algorithm returns the elements which are exclusive to each other which means elements as shown in Figure below.
IncludesThis algorithm returns a boolean indicating whether all the elements of second collection form a sub set of first collection as shown in the figure below.
MergeThis algorithm takes in two sorted collections and returns one sorted collection having member elements of both the individual sorted algorithms used as input.
This section has probably some of the easiest algorithms which you can find useful on a day-to-day basis.
CopyThis algorithm copies the elements from source collection to destination collection defined by the address.
MoveThis algorithm moves the elements from source collection to destination collection which means it copies the elements from source collection to destination collection and then deletes from the original source location.
swap_rangesThis algorithm interchanges the contents of two collections.
copy_backwardsThis algorithm copies the elements starting from back. One use case could be when we need to copy some elements of the source collection partially to overwrite other elements in the same collection as shown in the figure below.
Move_backwardsThis algorithm works similar to copy_backwards, but it deletes elements from source once it has copied successfully to destination.
Modifiers simply change the value of the elements of a collection.
FillTo fill all elements of a collection with a specific value, we can use this algorithm.
GenerateThis algorithm is used to generate random numbers up until the input number.
There also exist some keywords which are used as prefix and some as suffix to the already existing algorithms changing the algorithm’s functionality slightly. Following is the list of prefix and suffix used :-
All these algorithms are easy to understand and can be used in day to day programming which essentially make tasks easier to execute. You can practice with just a few algorithms from each section and soon you will find all the other algorithms easy to comprehend. This will also instill the knowledge of writing your own algorithms.