The first class of algorithms that I am going to discuss are sorting and searching algorithms. They are the most basic type of algorithms. Many times in a programming problem ( real world or in competitions), we need to sort a list of numbers or strings in ascending or descending order. The most basic sorting algorithms are Bubble Sort, Selection Sort, Insertion Sort and Quick Sort. But, none of these are good enough. As the length of the array to sort increases, these algorithms start taking too much time to sort. Merge Sort and Heap sort, on the other hand, respond well even on large inputs.
Implementation of good sorting algorithms is already available in the libraries of C++, Java and Python, so one doesn’t need to write a sort function from scratch in a programming competition.
But still I’ll discuss about one sorting technique that demonstrates a little trick that will help you in understanding other algorithms.
The algorithm is the ‘Counting Sort‘. It is a very simple way to sort numbers. The reason I am discussing it is that it demonstrates how the array indices can be cleverly used to simplify many tasks.
Sources to read from…
Counting sort:
http://www.cs.miami.edu/~burt/learning/Csc517.091/workbook/countingsort.html
http://www.geeksforgeeks.org/counting-sort/
Related problems:
Codechef problem named ‘Turbo Sort’: http://www.codechef.com/problems/TSORT
NOTE:
Even though inbuilt sorting functions are available in C++, Java and Python, still I would suggest you to understand how the different sorting algorithms work as it will help you to develop your understanding. Also,NEVER use code templates from websites blindly. Always understand how they work first.
How to use sorting function in C++, Java and Python:
For C++ users,
add the following line in the beginning of the program.
#include<algorithm> // ‘algorithm’ is a header file that contains implementation of some commonly used algorithms
and then you can use the following statement to sort an array (named ‘arr’ )
sort(arr,arr+n); // where n is the number of elements in the array
For Python users:
Just a make a list,
arr=[6,53,2,7,3]
and use
arr.sort()
For Java users:
Make an array and use
Arrays.sort(arr);
and the array arr will be sorted
If you have any problem in understanding the algorithm then you may leave a comment the comments section below and I’ll try to answer it as soon as I can.
Code Accepted 