Saturday 1 December 2012

Sorting Algorithms - A Comparison




  Here I am comparing three Sorting Algorithms which takes quadratic time to perform the operation. The three sorting techniques under consideration are Bubble Sort, Selection Sort and Insertion Sort.

                                      Bubble Sort

  Bubble Sort is a comparison sort, which means the sorting is done by comparing elements in the list to be sorted. Bubble Sort is an in-place sorting technique, which means it only requires constant additional space to perform the sorting. The additional space requirement is to hold the temporary values while swapping two numbers. Bubble Sort takes O(n2) time to perform the sorting. The two advantages with Bubble Sort are the best case performance of linear time ( O(n) ) if the list is already sorted and the inherent simplicity of the algorithm. Most often this is the algorithm which comes to the mind of a person when asked to perform sorting.

Click here to download the C Program to perform Bubble Sort.
Click here to download the C++ Program to perform Bubble Sort.


                                      Selection Sort

  This is another sorting algorithm which takes quadratic time to perform the operation. Selection sort is also an in-place comparison sort. One advantage with Selection Sort is its simplicity. Unlike Bubble Sort, Selection Sort constructs the sorted list one by one after each iteration of the outer loop. So in situations where you can start working with the list even when it is not complete we must go for Selection Sort.

Click here to download the C Program to perform Selection Sort. 
Click here to download the C++ Program to perform Selection Sort. 

                                      Insertion Sort

  Insertion Sort also takes quadratic time to sort. It is also an in-place comparison sort. Insertion Sort gives slightly better performance when compared with the other two quadratic time sorts. The best case performance of Insertion Sort is linear just like Bubble Sort. But Insertion Sort also performs well if the list is partially sorted. So if you have to choose between the quadratic sorts, it is slightly better to choose Insertion Sort.

Click here to download the C Program to perform Insertion Sort. 
Click here to download the C++ Program to perform Insertion Sort. 



1 comment: