## 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.

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.