Algorithm #1!

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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s