One of
the simplest sorting algorithms is the insertion sort. The code
for the algorithm is as follows:
for(i = 1; i < n; i++){
Inserted = false; //boolean variable
j = i;
while((j >= 1) && (Inserted == false){
if(List[j] < List[j-1])
swap(List[j], List[j-1]);
else
Inserted=true;
j--;
}
}
This algorithm works by first
considering the first element of the list (element 0) to be correctly placed.
It proceeds to the next element (element 1) and compares its value with.
If the magnitude is smaller, it swaps it with element 0. Now, elements
0 and 1 are sorted, but only with respect to each other. Element 2 is now
considered, and is moved to its correct position with respect to elements
0 and 1, i.e., it may stay where it currently is, or it may be placed between
what are now elements 0 and 1, or it may be placed before element 0. To
do this, elements 2 and 1 may be swapped, resulting in the placement of
element 2 between what is currently element 0 and element 1, and then another
swap between what are now elements 0 and 1 may be done to place the element
before what is now element 0. This continues over and over again, considering
the elements from element 3 through the last element of the list. Each
element is placed in its proper position in the part of the list already
consider to be sorted. Each element under consideration is swapped with
its immediately preceeding neighbour as it moves towards the front of the
list. The moment the swapping stops, the element's immediately preceding
neighbor has lesser magnitude, and so the current element may be considered
to be properly placed.
In this method there are N-1
insert operations. The j-th insert operation inserts a new element into
a sorted array of j elements and hence takes at most j comparisions. Thus
the total number of comparisions are:
1 + 2 + 3 + ... + (N-1) = N*(N-1)/2
= O(N^2)
