next up previous contents index CD CD Algorithms
Next: Divide and Conquer Up: Approaches to Sorting Previous: Data Structures

Incremental Insertion

Now consider a different approach to sorting that grows the sorted set one element at a time. Select an arbitrary element from the unsorted set, and put it in the proper position in the sorted set.   



for i = 1 to n-1 do


while (A[j] > A[j-1]) do swap(A[j],A[j-1])

Although insertion sort takes tex2html_wrap_inline24060 in the worst case, it will perform considerably better if the data is almost sorted, since few iterations of the inner loop will suffice to sift it into the proper position. Insertion sort is perhaps the simplest example of the incremental insertion technique, where we build up a complicated structure on n items by first building it on n-1 items and then making the necessary changes to fix things in adding the last item. Incremental insertion proves a particularly useful technique in geometric algorithms.

Mon Jun 2 23:33:50 EDT 1997