// Swap the int at j with the int at min array[j] = array[min]; array[min] = array[j];
Is this replacement going to work?
No. After the first statement both array[j]
and array[min]
hold the same value.
The value previously at array[j]
has been lost.
Revise the program so that the array is initialized with as many random integers as the user specifies (as suggested in the exercises.) Don't print out the array when there are more than 100 elements.
On my (fairly old) computer it takes about 306 seconds to sort an array of 500 thousand ints. This is a long time. Why is sorting so slow?
Look at the central part of the algorithm:
for ( int j=0; j<array.length-1; j++ ) { int min = j; for ( int k=j+1; k<array.length; k++ ) if ( array[k] < array[min] ) min = k; // Swap the int at j with the int at min int temp = array[j]; array[j] = array[min]; array[min] = temp; }
Say that there are N
ints in the array.
(In other words, array.length == N
).
Then the code can be simplified:
for ( int j=0; j<N-1; j++ ) { int min = j; for ( int k=j+1; k<N; k++ ) if ( array[k] < array[min] ) min = k; // Swap ... }
How many times does the outer loop (for j
) execute its body?
N-1 times, for j = 0, 1, 2, 3, ..., N-2
The first time the outer loop executes (with j=0
), how many times does the inner loop (for k) execute its body?
N-1 times, for k=1, 2, 3, 4, ... , N-1
The second time the outer loop executes (with j=1
), how many times does the inner loop execute?
N-2 times, for k=2, 3, 4, ... , N-1
The third time the outer loop executes (with j=2
), how many times does the inner loop execute?
N-3 times, for k=3, 4, ... , N-1
. . . . . . . .
The last time the outer loop executes (with j=N-2
), how many times does the inner loop execute?
1 time, for k=N-1
Here is a table that shows this
j | 0 | 1 | 2 | 3 | ... | N-3 | N-2 |
---|---|---|---|---|---|---|---|
executions of inner loop | N-1 | N-2 | N-3 | N-4 | ... | 2 | 1 |
So the total number of times the body of the inner loop is executed is
(N-1) + (N-2) + (N-3) + (N-4) + ... + 3 + 2 + 1
The total running time of the sorting method is proportional to this sum.
Recall the formula for the sum of the first M integers:
1 + 2 + 3 + 4 + 5 + ... + M = M*(M+1)/2
Using this formula, simplify our sum:
(N-1) + (N-2) + (N-3) + (N-4) + ... + 3 + 2 + 1