Java Reference
In-Depth Information
/**
Sorts the array managed by this insertion
sorter.
*/
public void sort()
{
for (int i = 1; i < a.length; i ++)
{
int next = a[i];
// Find the insertion location
// Move all larger elements up
int j = i;
while (j > 0 && a[j - 1] > next)
{
a[j] = a[j - 1];
j--;
}
// Insert the element
a[j] = next;
}
}
private int[] a;
}
638
How efficient is this algorithm? Let n denote the size of the array. We carry out
nɨ1 iterations. In the kth iteration, we have a sequence of k elements that is
already sorted, and we need to insert a new element into the sequence. For each
insertion, we need to visit the elements of the initial sequence until we have found
the location in which the new element can be inserted. Then we need to move up
the remaining elements of the sequence. Thus, k+1 array elements are visited.
Therefore, the total number of visits is
n(n +1)
2
2 +3 + ș +n =
ɨ1
We conclude that insertion sort is an O(n
2
) algorithm, on the same order of
efficiency as selection sort.
Insertion sort is an O(n
2
) algorithm.
