Vencedor
Operações
Concluídos

  • Comparados
  • Marcados (mínimo, pivô ou chave)
  • Trocados ou movidos
  • No lugar
Posição Algoritmo Comparações ou leituras Trocas ou movimentos Operações

Mais sobre algoritmos de ordenação

Corrida de ordenações

Qual é o algoritmo de ordenação mais rápido? Depende da lista. A Corrida de ordenações executa os oito algoritmos de ordenação ao mesmo tempo na mesma lista, uma pista para cada um, e conta cada comparação, leitura, troca e movimento como uma operação. As pistas avançam à medida que as contagens sobem, por isso pode ver os algoritmos eficientes terminar enquanto os lentos ainda estão a trocar, e ver a ordem mudar quando a lista está quase ordenada ou invertida. Prima Reproduzir para ver os oito algoritmos de ordenação a competir na mesma lista, ou Avançar e Recuar para ir uma operação de cada vez. Arraste a barra de passos para saltar para qualquer ponto. Cada comparação, leitura, troca ou movimento conta como uma operação, e cada pista avança à medida que sobe a sua própria contagem, por isso o algoritmo que precisa de menos operações termina primeiro. Escolha quantas barras e como começam, ou escreva os seus próprios números. Com o quadro selecionado, as setas avançam e recuam, a barra de espaço reproduz e pausa, e Home e End saltam para o início e o fim.

Como funciona

  1. Escolha o número de barras e a ordem inicial: aleatória, quase ordenada, invertida ou com poucos valores distintos. Ou escreva os seus próprios números.
  2. Prima Reproduzir e veja as oito pistas. Avançar e Recuar movem uma operação de cada vez; a barra de passos salta para qualquer ponto da corrida.
  3. Compare a tabela de resultados e depois experimente uma lista quase ordenada e uma invertida para ver a classificação mudar.

Como funciona a corrida

Os oito algoritmos recebem a mesma lista. Cada comparação de dois valores, cada dígito ou valor lido pela ordenação radix e pela ordenação por contagem, e cada troca ou movimento conta como uma operação. Em cada momento da corrida, cada pista mostra até onde o seu algoritmo chegou com esse número de operações. Um algoritmo que precisa de menos operações chega mais cedo ao fim. A tabela de resultados mostra as comparações, as trocas ou movimentos e o total de cada algoritmo.

O que os resultados mostram

Com 40 valores aleatórios, a ordenação por contagem precisa de cerca de 120 operações, a ordenação radix de cerca de 240, o quicksort de cerca de 260 e o merge sort de cerca de 380. Segue-se a ordenação por heap com cerca de 490, enquanto a ordenação por seleção e a ordenação por inserção precisam de cerca de 820 e o bubble sort de mais de 1100. Numa lista quase ordenada, a ordenação por inserção ganha com cerca de 50, e o bubble sort fica em segundo. Numa lista invertida, o bubble sort e a ordenação por inserção precisam ambos de 1560. A ordenação por contagem e a ordenação radix ganham tantas vezes porque estes valores são números inteiros pequenos; noutros dados, nem sequer se podem usar.

Perguntas frequentes

Qual é o algoritmo de ordenação mais rápido?

Depende dos dados. Para números inteiros pequenos, a ordenação por contagem e a ordenação radix precisam de menos operações. Para dados gerais, o quicksort e o merge sort são os mais rápidos em listas aleatórias, e a ordenação por inserção é a mais rápida em listas quase ordenadas. O bubble sort e a ordenação por seleção são lentos, exceto nas listas mais pequenas.

O que conta como uma operação?

Cada comparação de dois valores, cada dígito ou valor lido pela ordenação radix e pela ordenação por contagem, e cada troca ou movimento de um valor. É um modelo simples: os tempos reais também dependem do acesso à memória e do custo de cada operação.

Porque é que a ordenação por contagem e a ordenação radix ganham tantas vezes?

Porque nunca comparam valores. Aproveitam o facto de os valores serem números inteiros pequenos, por isso o seu trabalho cresce com n mais a amplitude dos valores, e não com n log n. Em dados que não são inteiros pequenos, não se aplicam.

Porque é que a ordenação por inserção ganha numa lista quase ordenada?

Porque o seu trabalho é o número de valores mais o número de pares fora de ordem. Uma lista quase ordenada tem muito poucos desses pares, por isso cada valor só se move uma ou duas posições.

Os meus números são enviados para algum lado?

Não. A corrida decorre no seu navegador, e as suas últimas definições ficam guardadas no armazenamento local deste navegador.

Pronto para experimentar?

Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.

Ir para o editor