1

I'm a bit stuck trying to understand the following script from a book:

values=(39 5 36 12 9 3 2 30 4 18 22 1 28 25)
numvalues=${#values[@]}

for (( i=0; i < numvalues; i++ )); do 
    lowest=$i

    for (( j=i; j < numvalues; j++ )); do
        if [ ${values[j]} -le ${values[$lowest]} ]; then
            lowest=$j
        fi
    done

    temp=${values[i]}
    values[i]=${values[lowest]}
    values[lowest]=$temp
done

for (( i=0; i < numvalues; i++ )); do
    echo -ne "${values[$i]}\t"
done

echo

The script is performing a selection sort on the numbers in the array, and is ultimately sorting them in correct numerical order. According to the book:

the outer i for loop is for looping over the entire array and pointing to the current 'head' (where we put any value we need to swap). The variable lowest is set to this index.

I understand this part, and I guess the value of lowest on the first iteration will be index 0, and the value 39.

What I am struggling to understand is how the inner j loop is working. The book says:

it compares the remaining elements with the value at lowest; if a value is less than lowest is set to the index of that element.

I can't get my head around how the value of j is any different to the value of i. To my mind if j=i, which is on first iteration 0, then j is also equal to 0. I guess this must change on the second and subsequent iterations. I know that the value of j must differ from the value of i, as this is what the [ ${values[j]} -le ${values[$lowest]} ] part of the script is calculating.

Does this work because of the j=i and subsequent j++ part of the inner for loop? If j=i, and on the second iteration if i=1, does this mean that j++ is equal to 2?

New Comment:

On thinking further about this script. I can see how j=i+1 would work in the inner loop. In the first iteration i would be 0 and j would be 1, so this would compare the values of the first and second element. On further iterations, i=1 and j=2, i=2 and j=3 etc….

However, in the script as it is written I can’t quite see how it works. On first iteration i=0 and j=0. So the first value in the array is compared with itself. Surely on second iteration i=1 and j=2, so this would compare the second and third values. What I can’t see is how index 0 was compared with index 1 ie. 39 compared against 5. Surely the second iteration skips this as it compares 5 against 36.

2

To my mind if j=i, which is on first iteration 0, then j is also equal to 0.

Correct, for each of the first iterations of the inner loop, j will be equal to i.

I guess this must change on the second and subsequent iterations.

Also correct (for the inner loop). For the first iteration of the inner loop, j will have whatever value i holds in that iteration of the outer loop.

I know that the value of j must differ from the value of i, as this is what the [ ${values[j]} -le ${values[$lowest]} ] part of the script is calculating.

From the second iteration (of the inner loop) onwards.

If j=i, and on the second iteration if i=1, does this mean that j++ is equal to 2?

Also correct, for the second iteration of the inner loop1.

Now, for each of the first iterations of the inner loop, i, j and lowest are all the same. Why? lowest was already set to i. j is set to i at the beginning of the iteration, and the test that follows will set lowest to j, which is i, because it is comparing the same elements. So, the first iteration of that inner loop is pointless, it could have started from i+1 without any problem. However, it is not an error, just unnecessary.

1Technically, j++ will be 1, not two, since ++ after the variable, called a post increment operator, increases the value after the variable has been evaluated for the expression. j will be 2 after the expression has been evaluated.

0

That inner loop for (( j=i; j < ... seems buggy, as by contrast "Algorithms" (4th edition, Sedgewick & Wayne) uses:

for (int j = i+1; j < ...

for their selection sort example.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.