Logo Data Structures and Algorithms with Object-Oriented Design Patterns in Java
next up previous contents index

Insertion Sorting

The first class of sorting algorithm that we consider comprises algorithms that sort by insertion  . An algorithm that sorts by insertion takes the initial, unsorted sequence, tex2html_wrap_inline68501, and computes a series of sorted sequences tex2html_wrap_inline68585, as follows:

  1. The first sequence in the series, tex2html_wrap_inline68587 is the empty sequence. That is, tex2html_wrap_inline68589.
  2. Given a sequence tex2html_wrap_inline68591 in the series, for tex2html_wrap_inline61638, the next sequence in the series, tex2html_wrap_inline68595, is obtained by inserting the tex2html_wrap_inline62458 element of the unsorted sequence tex2html_wrap_inline68599 into the correct position in tex2html_wrap_inline68591.
Each sequence tex2html_wrap_inline68591, tex2html_wrap_inline61638, contains the first i elements of the unsorted sequence S. Therefore, the final sequence in the series, tex2html_wrap_inline68611, is the sorted sequence we seek. That is, tex2html_wrap_inline68613.

Figure gif illustrates the insertion sorting algorithm. The figure shows the progression of the insertion sorting algorithm as it sorts an array of ten integers. The array is sorted in place  . That is, the initial unsorted sequence, S, and the series of sorted sequences, tex2html_wrap_inline68617, occupy the same array.

   figure34225
Figure: Insertion sorting.

In the tex2html_wrap_inline57420 step, the element at position i in the array is inserted into the sorted sequence tex2html_wrap_inline68591 which occupies array positions 0 to (i-1). After this is done, array positions 0 to i contain the i+1 elements of tex2html_wrap_inline68595. Array positions (i+1) to (n-1) contain the remaining n-i-1 elements of the unsorted sequence S.

As shown in Figure gif, the first step (i=0) is trivial--inserting an element into the empty list involves no work. Altogether, n-1 non-trivial insertions are required to sort a list of n elements.