Entender função bubble sort de um array

[brunoandrad]

Ola pessoal,

Estou aprendendo C através do site: http://computer.howstuffworks.com/c10.htm

Não entendi como funciona o final da função.

for (x=0; x < MAX-1; x++)
    for (y=0; y < MAX-x-1; y++)
        if (a[y] > a[y+1])
        {
            t=a[y];
            a[y]=a[y+1];
            a[y+1]=t;
        }
/* print sorted array */
printf("--------------------\n");
for (i=0; i < MAX; i++)
printf("%d\n",a[i]);

No meu entendimento, ele não faria o for pois nunca entraria no if.

Porém quando executo, ele ordena corretamente... eu realmente não entendi como ele executa o if sendo que na minha visão:

a[y] jamais será maior que a[y+1]

 

Alguém consegue me explicar essa parte?

[Durub]

Por que a[y] jamais seria maior que a[y + 1]? y jamais será maior que (y + 1). Entretanto, a[y] pode muito bem ser maior que a[y + 1].

a[x] significa acessar o valor na posição x (as posições começam em zero) do array. Logo, a[0] acessa a primeira posição do array -- a posição zero.

Array do exercício:
 

int a[5];

a[0] = 12;
a[1] = 9;
a[2] = 14;
a[3] = 5;
a[4] = 1;

Suponha y = 0:
a[y] -> 12
a[y + 1] -> 9
Logo, a[y] > a[y + 1] quando y = 0. O mesmo é válido para y = 2 e y = 3.

Abraços.

[brunoandrad]

porque a[y] -> 12?

Não seria a[x] -> 12 ?

// MAX = 4

for (x=0; x < MAX-1; x++)
    for (y=0; y < MAX-x-1; y++)
        if (a[y] > a[y+1])

1a vez no for:

for(x=0; x < 4-1; 0++)

for (y=0; y < 4-0-1; 0++)

if (a[0] > a[0+1])

 

2a vez no for y:

for (y=1; y <  3; 1++)

if (a[1] > a[1+1])

 

3a vez no for y:

for (y=2; y<3; 2++)

if (a[2] > a[2+1])

 

Na minha cabeça o for seria executado assim.. não entendi como o a[y] teria o valor de 12. E mesmo que tivesse, o a[y+1] sempre seria maior, pois seria a[12+1]

 

Com certeza estou comendo bola em algum ponto... só não consigo achar onde.

[Durub]

a[x] pode ser 12, a[y] também pode ser 12, depende dos valores de x ou y. Quando x = 0, a[x] é 12. Quando y = 0, a[y] é 12.

Veja como o array é imprimido no código:

for (i=0; i < MAX; i++)
    printf("%d\n",a[i]);

O que significa (tive que deixar separado em um bloco de código devido a formatação do fórum)

a[i]

? Significa acessar a posição i do array e retornar o seu valor. É a mesma coisa com a[x] e a[y].

int a[5];

a[0] = 12;
a[1] = 9;
a[2] = 14;
a[3] = 5;
a[4] = 1;

// Imprime: "12 9 14 5 1"
printf("%d %d %d %d %d\n", a[0], a[1], a[2], a[3], a[4]);

// Também imprime: "12 9 14 5 1"
int y = 0;
printf("%d %d %d %d %d\n", a[y], a[y + 1], a[y + 2], a[y + 3], a[y + 4]);

/* Por quê?
a[y] = a[0] = 12
a[y + 1] = a[1] = 9
a[y + 2] = a[2] = 14
a[y + 3] = a[3] = 5
a[y + 4] = a[4] = 1 */

Quando y = 0:
a[y] > a[y + 1]
a[0] > a[0 + 1]
a[0] > a[1]
12 > 9 (verdadeiro, logo entra no if)

Parece, para mim, que a dificuldade está em entender qual o valor retornado por a[y + c], sendo c, nesse caso, 1.
a[y + c] não é a[y] + a[c], é a[(y + c)].

Abraços.

[brunoandrad]

Obrigado pela explicação.. comecei a entender.

 

Eu estava confundindo o y=0 do for com valor, e não que ele significa a posição do vetor, sendo que o valor seria a posição.

Agora entendi o if (a[y] > a[y+1])

Seria o valor na posição a[y] > que o valor na posição a[y+1]

No caso: a[12] > a[9]

Essa parte acho que ficou claro para mim... agora estou apanhando do restante, rs:

            {
                t=a[y];
                a[y]=a[y+1];
                a[y+1]=t;
            }

Seria isso?

    t=a[12]
    a[12]=a[9]
    a[9]=a[12]

 

Ficou as os valores na posição do vetor: a[0] = 9                a[1] = 12

 

Parece que agora compreendi... seria isso mesmo?