Java Reference
In-Depth Information
4.
Look at the graph in
Figure 1
. What mathematical shape does it
resemble?
14.3 Analyzing the Performance of the Selection Sort
Algorithm
Let us count the number of operations that the program must carry out to sort an array
with the selection sort algorithm. We don't actually know how many machine
operations are generated for each Java instruction or which of those instructions are
more time-consuming than others, but we can make a simplification. We will simply
count how often an array element is visited. Each visit requires about the same
amount of work by other operations, such as incrementing subscripts and comparing
values.
Let n be the size of the array. First, we must find the smallest of n numbers. To
achieve that, we must visit n array elements. Then we swap the elements, which takes
two visits. (You may argue that there is a certain probability that we don't need to
swap the values. That is true, and one can refine the computation to reflect that
observation. As we will soon see, doing so would not affect the overall conclusion.)
In the next step, we need to visit only nɨ1 elements to find the minimum. In the
following step, nɨ2 elements are visited to find the minimum. The last step visits
two elements to find the minimum. Each step requires two visits to swap the
elements. Therefore, the total number of visits is
n +2 +(n ɨ1) +2 + ș +2 +2 =n +(n ɨ1) + ș +2 +(n ɨ1) 2
=2 + ș +(n ɨ1) +n +(n ɨ1) 2
n(n +1)
2
=
ɨ1 +(n ɨ1) 2
because
1 +2 + ș +(n ɨ1) +n =
n(n +1)
2
After multiplying out and collecting terms of n, we find that the number of visits is
