Tuesday, November 17, 2009

Art of computer programming -Sorting #2

Insertion sort
Insertion sort is one of those very traditional sorting methods. In this method, we scan through the list element by element and we assume that all elements preceding the present element is sorted. We start with the assumption that first element is sorted and we need to place the 2nd element to the left or the right of the first element based on whether its greater than or less than the 1st element. So we can generalize that for the i'th element we assume that the list from 0...i-1 is sorted and we can insert the ith element at the the correct position in this sorted sublist. So the problem reduces to inserting an element in a sorted list. But its not as simple as it sounds. Inserting in a sorted list may need shifting the elements of the sublist. Its a reasonably expensive operation. Hence using arrays will be quite expensive for insertion sort. Whereas if you are using linked lists, then shifting operations become much more easier(as it involves only 2-3 pointer operations).
On an average we will need a total of 0.5(1+2+...+n) shiftings ~ 0.25n^2

A method to improve this will be to use binary search to find the position of the element in the sorted list. This will reduce the position search time to log n. Hence the algorithm improves.

Points of interest
To check whether a list is already sorted insertion sort is highly recommended.
It can receive data as it is working. This is particularly useful when you have only an incomplete piece of data.
While insertion sort typically makes fewer comparisons than selection sort, it requires more writes because the inner loop can require shifting large sections of the sorted portion of the array.

insertionSort(array A)
for i := 1 to length[A]-1 do
value := A[i];
j := i - 1;
while j >= 0 and A[j] > value do
A[j + 1] := A[j];
j := j - 1;
A[j + 1] := value;

Worst case performance О(n^2)
Best case performance O(n)
Average case performance О(n^2)
Worst case space complexity O(1)

No comments:

Post a Comment