BubbleSort

Bem-vindo ao universo da ordenação. Ele permite que experimente os algoritmos de ordenação existentes. A lista de "buildins" que pode usar nos seus algoritmos está disponível na documentação de referência do mundo ("Ajuda"->"Sobre este mundo").

Não é suficiente ordenar a array para passar nos exercícios. A sua solução deve seguir estritamente o comportamento esperado em cada exercício. Isto é reforçado a verificar que o seu algoritmo precisa da mesma quantidade de operações de escrita e leitura para ordenar a array.

Quando seu algoritmo divergge das expectativas, entender a diferença entre o seu código e a solução esperada pode ser muito difícil. Para ajudar neste processo, é possível explorar graficamente a história do seu algoritmo de ordenação. Alterne à visão Objetivo e use o menu contextual (clique com o botão direito) para alternar da visão do estado atual para a visão do histórico dele.

A visão do histórico é um pouco bagunçada à primeira vista, mas na verdade é bem simples: o tempo anda da esquerda para a direita neste gráfico e cada linha é uma célula da sua array. As linhas curvas que navegam entre linhas representam um certo valor de um dado. Quando duas linhas se cruzam, significa que dois valores foram alternados agora; uma bifurcação numa linha representa uma cópia de valor; quando um valor é magenta e seguido de uma interrogação (?), foi lido a usar getValue(); Se o valor é vermelho e seguido de uma exclamação (!), foi escrito com setValor().

Primeira tentativa no BubbleSort

O primeiro algoritmo de ordenação é o mais simples: Bubble sort consiste em progressivamente mover o menor elemento da array, como se fossem bolhas de ar a subir à superfície de um líquido. O algoritmo percorre a array e compara qualquer par de elementos adjacentes. Se dois elementos adjacentes estiverem fora de ordem, eles são alternados. Quando a array estiver completamente percorrida, a operação começa de novo do começo. Quando nenhum elemento for ordenado após uma passagem completa, significa que a array está completamente ordenada: e o algoritmo pode parar. Bubble sort é estudado por causa da simplicidade dele, mas quase nunca é usado na prática por causa do baixo desempenho dele (O(n^2) em média).

O pseudo-código do algoritmo BubbleSort é o seguinte:

faça: 
        Para cada i em [0,len-2]
          Se a célula i e i+1 devem ser alternadas, alterne
enquanto algo foi alternado na última passagem