Cover Data Structures and Algorithms with Object-Oriented Design Patterns in Java
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_inline58840 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.

   program34823
Program: BinaryInsertionSorter class sort method.

Exactly, n-1 iterations of the outer loop are done (lines 6-21). In each iteration, a binary search search is done to determine the position at which to do the insertion (lines 8-18). In the tex2html_wrap_inline57340 iteration of the outer loop, the binary search considers array positions 0 to i (for tex2html_wrap_inline68695). The running time for the binary search in the tex2html_wrap_inline57340 iteration is tex2html_wrap_inline68699. 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_inline58122. Furthermore, since the algorithm only swaps adjacent array elements, the average running time is also tex2html_wrap_inline58122 (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_inline57340 iteration of the outer loop, the binary search requires tex2html_wrap_inline68711 comparisons, for tex2html_wrap_inline68695. Therefore, the total number of comparisons is

eqnarray34836

(This result follows directly from Theorem gif).

The number of comparisons required by the straight insertion sort is tex2html_wrap_inline58122 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_inline58846. 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_inline58122 tex2html_wrap_inline58122
binary insertion sort tex2html_wrap_inline58846 tex2html_wrap_inline58122 tex2html_wrap_inline58122
Table: Running times for insertion sorting.


next up previous contents index

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