Compreendendo o script bash

Question

Estou um pouco preso tentando entender o seguinte script de um livro:

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

O script está realizando uma classificação de seleção nos números da matriz e, por fim, os classifica em ordem numérica correta. De acordo com o livro:

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.

Eu entendo essa parte, e acho que o valor mais baixo na primeira iteração será o índice 0 e o valor 39.

O que eu estou tentando entender é como o loop j interno está funcionando. O livro diz:

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.

Não consigo entender como o valor de j é diferente do valor de i . Em minha opinião, se j=i , que está na primeira iteração 0, então j também é igual a 0. Acho que isso deve mudar na segunda e nas iterações subsequentes. Eu sei que o valor de j deve diferir do valor de i , pois é isso que a parte [ ${values[j]} -le ${values[$lowest]} ] do script está calculando.

Isso funciona devido à parte j=i e subseqüente j++ do loop for interno? Se j=i e, na segunda iteração, se i=1 , isso significa que j++ é igual a 2?

Novo comentário:

Em pensar mais sobre esse script. Eu posso ver como j = i + 1 funcionaria no loop interno. Na primeira iteração eu seria 0 ej seria 1, então isso compararia os valores do primeiro e do segundo elemento. Em outras iterações, i = 1 e j = 2, i = 2 e j = 3 etc….

No entanto, no script como está escrito, não consigo ver como funciona. Na primeira iteração i = 0 e j = 0. Portanto, o primeiro valor da matriz é comparado a ele mesmo. Seguramente na segunda iteração i = 1 ej = 2, então isto compararia o segundo e terceiro valores. O que não consigo ver é como o índice 0 foi comparado com o índice 1, ou seja. 39 comparado com 5. Certamente a segunda iteração pula isso, pois compara 5 contra 36.

    

Answer 1

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

Correto, para cada uma das primeiras iterações do loop interno, j será igual a i .

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

Também correto (para o loop interno). Para a primeira iteração do loop interno, j terá qualquer valor que i detenha nessa iteração do loop externo.

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.

Da segunda iteração (do loop interno) em diante.

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

Também correto, para a segunda iteração do laço interno ¹ .

Agora, para cada uma das primeiras iterações do loop interno, i , j e lowest são todos iguais. Por quê? lowest já estava definido como i . j está definido como i no início da iteração e o teste a seguir definirá lowest a j , que é i , porque está comparando os mesmos elementos. Portanto, a primeira iteração desse loop interno é inútil, poderia ter sido iniciada a partir de i+1 sem nenhum problema. No entanto, não é um erro, apenas desnecessário.

^{1 Tecnicamente, j++ será 1 , não dois, pois ++ após a variável, chamada de operador pós incremento , aumenta o valor após a variável ter sido avaliado para a expressão. j será 2 após a expressão foi avaliada.}

    

Answer 2

Esse loop interno for (( j=i; j < ... parece com erros, já que, por contraste, "Algorithms" (4ª edição, Sedgewick & Wayne) usa:

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

para o exemplo de classificação de seleção.