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