The Sorting problem - PART II

In this session, we will talk about insertion sort. Insertion sort is a sorting technique which has the same running time as the bubble sort.
First the technique behind the insertion sort. The input that is the array of numbers will be iterated and during iteration each element is taken as the key and this number is inserted in the list of elements before this element preserving the non decreasing order property. So the algorithm will start from the second element and compare with the previous element and find its place. then the next iteration and so on. I think now you got why the name as insertion sort.

This is the java implementation of the insertion sort.

public class InsertionSort {

public int[] sort(int []input){


for(int i=1;i<input.length;i++){
int key = input[i];
int j=i-1;
while(j>=0 && input[j]>key){
input[j+1] = input[j];
j--;
}
input[j+1] = key;
   }
return input;
}
public static void main(String[] args) {
new InsertionSort().sort(new int[]{10,23,2,5,23,675,1,23});
}

}

Here you can see that the algorithm consists of a for loop which iterates n-1 times and and while loop which iterates n-1 times. so the running time will be O(n^2).

We can easily prove the correctness of the algorithm by stating the loop invariant as previous terms will be in sorted order. This is true before the first iteration (Initialization) and before the start of every iteration(Maintenance) and at the completion of the algorithm(Termination).

Now lets look at another algorithm which is very similar to the one that we discussed. It is called the selection sort which has the same running time as the insertion sort.
The design of this algorithm is as follows. Sorting n numbers stored in array A by first finding the smallest element of A and exchanging it with the element in first element. Then find the second smallest element of A, and exchange it with second element. Continue in this manner for the first n-1 elements of A.

This is the java implementation of the selection sort.


package sorting;

public class SelectionSort {

public int[] sort(int []input){


for(int i=0;i<input.length-1;i++){
          int j=i+1;
while(j<input.length){
if(input[i]>input[j]){
int temp = input[i];
//swapping the elements
input[i] = input[j];
input[j] = temp;
}
j++;
}
   }
return input;
}
public static void main(String[] args) {
new SelectionSort().sort(new int[]{10,23,2,5,23,675,1,23});
}

}

Here you can see that the algorithm consists of a for loop which iterates n-1 times and and while loop which iterates n-1 times. so the running time will be O(n^2).

We can easily prove the correctness of the algorithm by stating the loop invariant as previous terms will be in sorted order. This is true before the first iteration (Initialization) and before the start of every iteration(Maintenance) and at the completion of the algorithm(Termination).This is the same as the insertion sort.

more to come .. merge sort, quick sort, heap sort