Insertion Sort |
|
Insertion sort maintains a sorted front section of the array [1..i-1]. At each stage, a[i] is inserted at the appropriate point in this sorted section and i is increased.
Part way through sorting, a[1..i-1] is sorted. Consider a[i], and how to insert it into a[1..i-1] so as to make a[1..i] sorted:
Examine the elements a[i-1], a[i-2], ..., a[1], moving each of them one place right, and stopping when an element less than or equal to (the original) a[i] is found, or at the left-hand end of the array if no such element is found.
Place the original a[i] in the vacant location:
Now a[1..i] is sorted. Repeat until i=N. Insertion Sort DemonstrationChange the data in the HTML FORM below, click `go', and experiment. The sorted section of the array is [bracketted] in the trace area:
ComplexityTimeThe number of comparisons of elements in the worst case is (N-1) + (N-2) + ... + 1 = (N-1)*N/2i.e. O(N2). The average case time-complexity is O((N-1)*N/4), i.e. O(N2). The best-case time complexity is when the array is already sorted, and is O(N). SpaceThe space-complexity is O(1), just a few scalar variables. StabilityInsertion sort is stable, i.e. the relative order of equal keys is not changed, provided that you are careful about scanning the sorted region from right to left. Notes
L.A. © Department of Computer Science UWA 1984, Department of Computer Science Monash 1986, and (HTML) School of Comp. Sci. & Software Engineering, Monash University 1999 |
|
|