// Swap the int at j with the int at min 
      array[j] = array[min];
      array[min] = array[j];

Running time

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.

1 + 2 + 3 + 4 + 5 + ... + M = M*(M+1)/2

(N-1) + (N-2) + (N-3) + (N-4) + ... + 3 + 2 + 1