Java Reference
In-Depth Information
}
We get the events properly sorted and displayed on the output console:
2005/4/1
2005/4/3
2005/4/15
2005/5/27
2008/6/1
6.4.3 Complexity of selection sorting
Let us now focus on the time complexity of performing a selection sort on
an array of n elements. We shall count only the basic primitive operations
GreatherThan and swap as constant operations, ignoring all other instructions
(for example, increment the loop index, etc). The worst-case scenario of
selection sort is to sort an input array that is sorted using the reverse order:
16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
1, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2
1, 2, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3
...
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16
Indeed, we need to find the minimum of all sub-arrays in the outer loop. This
is done by swapping the current minimum with the current element whenever
the comparison predicate GreaterThan is true . For reverse order sorted arrays,
it takes 2( n +1
i ) primitive operations at stage i since the GreaterThan is
always evaluated to true so that we need to perform the swapping. Thus the
overall worst-case complexity is i =1 2( n +1
i )=2 i =1 i = n ( n + 1), which
is of the order of n 2 . Selection sort has quadratic complexity.
This can be checked experimentally by explicitly counting the number of
operations for sorting the reverse ordered array:
Program 6.9
Experimentally calculating the worst-case complexity of
selection sorting
class SelectionSortComplexity
static int nboperations ;
static boolean GreaterThan( int a, int b)
{ nboperations++; return (a > b) ; }
static void swap ( int [ ]
array , int i, int j)
{ nboperations++;
int tmp=array [ i ]; array [ i]=array [ j ]; array [ j]=tmp; }
public static void main( String [ ]
args )
{
 
Search WWH ::




Custom Search