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

Binary Insertion Sort

The straight insertion algorithm presented in the preceding section does a linear search to find the position in which to do the insertion. However, since the element is inserted into a sequence that is already sorted, we can use a binary search instead of a linear search. Whereas a linear search requires O(n) comparisons in the worst case, a binary search only requires tex2html_wrap_inline59121 comparisons. Therefore, if the cost of a comparison is significant, the binary search may be preferred.

Program gif defines the BinaryInsertionSorter class. The BinaryInsertionSorter class extends the AbstractSorter class defined in Program gif. The framework of the Sort method is essentially the same as that of the StraightInsertionSorter class.

   program35074
Program: BinaryInsertionSorter class Sort method.

Exactly, n-1 iterations of the outer loop are done (lines 5-20). In each iteration, a binary search search is done to determine the position at which to do the insertion (lines 7-17). In the tex2html_wrap_inline57621 iteration of the outer loop, the binary search considers array positions 0 to i (for tex2html_wrap_inline68978). The running time for the binary search in the tex2html_wrap_inline57621 iteration is tex2html_wrap_inline68982. Once the correct position is found, at most i swaps are needed to insert the element in its place.

The worst-case running time of the binary insertion sort is dominated by the i swaps needed to do the insertion. Therefore, the worst-case running time is tex2html_wrap_inline58403. Furthermore, since the algorithm only swaps adjacent array elements, the average running time is also tex2html_wrap_inline58403 (see Section gif). Asymptotically, the binary insertion sort is no better than straight insertion.

However, the binary insertion sort does fewer array element comparisons than insertion sort. In the tex2html_wrap_inline57621 iteration of the outer loop, the binary search requires tex2html_wrap_inline68994 comparisons, for tex2html_wrap_inline68978. Therefore, the total number of comparisons is

eqnarray35087

(This result follows directly from Theorem gif).

The number of comparisons required by the straight insertion sort is tex2html_wrap_inline58403 in the worst case as well as on average. Therefore on average, the binary insertion sort uses fewer comparisons than straight insertion sort. On the other hand, the previous section shows that in the best case the running time for straight insertion is O(n). Since the binary insertion sort method always does the binary search, its best case running time is tex2html_wrap_inline59127. Table gif summarizes the asymptotic running times for the two insertion sorts.

 

 

running time

algorithm

best case average case worst case
straight insertion sort O(n) tex2html_wrap_inline58403 tex2html_wrap_inline58403
binary insertion sort tex2html_wrap_inline59127 tex2html_wrap_inline58403 tex2html_wrap_inline58403
Table: Running times for insertion sorting.


next up previous contents index

Bruno Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.