Logo 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_inline59891 comparisons. Therefore, if the cost of a comparison is significant, the binary search may be preferred.

Program gif defines the DoSort routine of the BinaryInsertionSorter<T> class. The framework of this routine is essentially the same as that of the StraightInsertionSorter<T> class.

   program35333
Program: BinaryInsertionSorter<T> Class DoSort Member Function Definition

Exactly, n-1 iterations of the outer loop are done (lines 11-26). In each iteration, a binary search search is done to determine the position at which to do the insertion (lines 13-23). In the tex2html_wrap_inline58387 iteration of the outer loop, the binary search considers array positions 0 to i (for tex2html_wrap_inline69979). The running time for the binary search in the tex2html_wrap_inline58387 iteration is tex2html_wrap_inline69983. 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_inline59179. Furthermore, since the algorithm only swaps adjacent array elements, the average running time is also tex2html_wrap_inline59179 (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_inline58387 iteration of the outer loop, the binary search requires tex2html_wrap_inline69995 comparisons, for tex2html_wrap_inline69979. Therefore, the total number of comparisons is

eqnarray35346

(This result follows directly from Theorem gif).

The number of comparisons required by the straight insertion sort is tex2html_wrap_inline59179 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 routine always does the binary search, its best case running time is tex2html_wrap_inline59897. 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_inline59179 tex2html_wrap_inline59179
binary insertion sort tex2html_wrap_inline59897 tex2html_wrap_inline59179 tex2html_wrap_inline59179
Table: Running Times for Insertion Sorting


next up previous contents index

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