R Data Structures and Algorithms

Three Θ(n²) sorting algorithms

The following sections deal with three different sorting algorithms, which require θ(n² ) system runtime to execute both average-and worst-case scenarios. These algorithms are simple to implement, but show poor computational performance.

Insertion sort

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