Skip to main content

Searching and Sorting

Binary Search#

Binary Search is one of the underdogs algorithm that is about to become one of your favourites, everyone who knows a fair bit of coding knows this algorithm but fails to understand the potential of it, here you will unlock the potential of binary search for yourself but only if you read through completely and understand thoroughly.

Caution

Go through the step1 to step5 of binary search lessons of the codeforces article to learn in depth about the use cases of binary search outside of the box. The main theorem in the topcoder article is a gem, read it and own it.

Tips

Learn to identify the pattern of problems and scenarios where a particular algorithm or data structure can be applied, in this case binary search. Many of the difficult binary search problems at first look like a DP problems, but if you look closer and if you have read and understood the main theorem, you won’t have a hard time discovering that BS can be applied instead of wasting time on DP. The same goes for other data structures and algorithms.

Concept of Lower Bound and Upper Bound#

In C++, using the STL you can easily apply binary search to find the lower bound and upper bound of an element in a container. So what is lower bound and upper bound, you ask, don’t ask just read on.

Sorting#

Keeping the items of an array or vector organised has many advantages, one being you get to apply binary search, but there is a catch, the catch is your sorting can become disadvantageous if it takes too much time, luckily there are a few sorting algorithms that runs in O(nlogn) while there are few which run in O(n) as well, so read on to find out about these different sorting algorithms.

Remember that sorting algorithms that run in O(n*n) time is not entirely useless, for very small ‘n’, these algorithms are preferred as they don’t blow up and are also easier to write. However, C++ STL has got you covered you don’t have to write the sorting algorithm, just use the internal library method which will sort for you in O(nlogn) time.

Merge Sort#

Merge Sort algorithm will not just teach you how to sort but you will also learn the application of another fundamental concept of Divide and Conquer. It has a dependable time complexity of O(nlogn), but can you prove it? No you cannot, not until you have learnt the algorithm, so what are you waiting for, jump into some action and start reading.

Quick Sort#

As an alternative to merge sort is quick sort, the algorithm is quite unique and surely worth your efforts. Like merge sort it also applies Divide and Conquer, but unlike merge sort whose worst case time complexity is O(nlogn) , quick sort has a worst case time complexity of O(n*n), but wait it is only a rare case and mostly it has time complexity is O(nlogn). I am sure you must be curious how can this be, you can dwell on it after you have read the algorithm, so go on read ahead.

Counting Sort#

Radix Sort#

Bubble Sort#

Now that you have learnt about the faster sorting algorithms, you will be able to appreciate the simplicity of the slower sorting algorithms. Have an apprehension of all the algorithms you never know which one might come in handy. So go ahead and read the O(n*n) sorting algorithms

Insertion Sort#

Selection Sort#

Sorting custom data type using STL#

So far you have seen sorting applied to primitive data types but what if you have a custom data type declared, can you use the STL sort() method then? The answer is YES, you can, but you will have to read on to find out how.

Questions#