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

Implementation

Program gif defines the StraightInsertionSorter class. The StraightInsertionSorter extends the AbstractSorter class defined in Program gif. It simply provides an implementation for the no-arg Sort method.

   program35036
Program: StraightInsertionSorter class Sort method.

In order to determine the running time of the Sort method, we need to determine the number of iterations of the inner loop (lines 6-10). The number of iterations of the inner loop in the tex2html_wrap_inline57621 iteration of the outer loop depends on the positions of the values in the array. In the best case, the value in position i of the array is larger than that in position i-1 and zero iterations of the inner loop are done. In this case, the running time for insertion sort is O(n). Notice that the best case performance occurs when we sort an array that is already sorted!

In the worst case, i iterations of the inner loop are required in the tex2html_wrap_inline57621 iteration of the outer loop. This occurs when the value in position i of the array is smaller than the values at positions 0 through i-1. Therefore, the worst case arises when we sort an array in which the elements are initially sorted in reverse. In this case the running time for insertion sort is tex2html_wrap_inline58403.


next up previous contents index

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