The following sections deal with three different sorting algorithms, which require θ(n2 ) system runtime to execute both average-and worst-case scenarios. These algorithms are simple to implement, but show poor computational performance.
Consider a vector V of numeric elements which needs to be sorted in ascending order. The most intuitive way is to iterate through the vector of elements and then perform element insertions at relevant positions within the vector, satisfying the ordering criterion. This kind of ordering based on a series of insertions is termed insertion sorting. The following Figure 5.1 illustrates the approach for insertion sorting in which each row represents the modified vector for the corresponding ith iteration. The sorting operation is indicated by the arrows:
Figure 5.1: Illustration of insertion sort
The following is the code in R which performs insertion sorting to arrange a vector in increasing order:
Insertion_Sort ...