Por que a classificação por seleção é mais rápida do que a classificação por bolha?

Todas as complexidades fornecidas são verdadeiras, independentemente de como são fornecidas em notação Big O , portanto, todos os valores aditivos e constantes são omitidos.

Para responder à sua pergunta, precisamos d para se concentrar em uma análise detalhada desses dois algoritmos. Essa análise pode ser feita manualmente ou encontrada em muitos livros. Usarei os resultados da Arte da programação de computadores de Knuth .

Número médio de comparações:

• Classificação de bolhas : $ \ frac {1} {2} (N ^ 2-N \ ln N – (\ gamma + \ ln2 -1) N) + \ mathcal O (\ sqrt N) $
• Classificação por inserção : $ \ frac {1} {4} (N ^ 2-N) + N – H_N $
• Classificação de seleção : $ (N + 1) H_N – 2N $

Agora, se você plotar essas funções, obterá algo assim:

Como você pode ver, a classificação por bolhas é muito pior à medida que o número de elementos aumenta, embora ambos os métodos de classificação tenham a mesma assintótica complexidade.

Esta análise é baseada na suposição de que a entrada é aleatória – o que pode não ser verdade o tempo todo. No entanto, antes de começarmos a classificação, podemos permutar aleatoriamente a sequência de entrada (usando qualquer método) para obter o caso médio.

Omiti a análise de complexidade do tempo porque depende da implementação, mas métodos semelhantes podem ser usados.

Comentários

• Eu tenho um problema com ” podemos permutar aleatoriamente a sequência de entrada para obter um caso médio “. Por que isso pode ser feito mais rápido do que o tempo necessário para classificar?
• Você pode permutar qualquer sequência de números que levará $ N $ tempo, onde $ N $ é o comprimento da sequência. É ‘ óbvio que qualquer algoritmo de classificação baseado em comparação deve ter pelo menos $ \ mathcal O (N \ log N) $ complexidade, então mesmo se você adicionar $ N $ a ele ‘ A complexidade ‘ não será alterada. De qualquer forma, estamos falando de comparação e não de tempo, a complexidade do tempo depende da implementação e da máquina em execução, como mencionei na resposta.
• Acho que estava com sono, você tem razão, a sequência pode ser permutada no tempo linear .
• Como $ H_N = \ Theta (log N) $, o seu limite de comparação está correto para a classificação por seleção? Parece que você ‘ está implicando que faz comparações O (n log n) em média.
• Gamma = 0,577216 é Euler-Mascheroni ‘ s constante. O capítulo relevante é ” A Arte da Programação ” vol 3 seção 5.2.2 pg. 109 e 129. Como você plotou o caso de classificação por bolha exatamente, especialmente o termo O (sqrt (N))? Você apenas o negligenciou?

O custo assintótico, ou $ \ mathcal O $ -notation, descreve o comportamento limitante de uma função conforme seu argumento tende ao infinito, ou seja, sua taxa de crescimento.

A própria função, por exemplo o número de comparações e / ou trocas pode ser diferente para dois algoritmos com o mesmo custo assintótico, desde que cresçam com a mesma taxa.

Mais especificamente, a classificação por bolha requer, em média, $ n / 4 $ swaps por entrada (cada entrada é movida elemento a elemento de sua posição inicial para sua posição final, e cada swap envolve duas entradas), enquanto a classificação por Seleção requer apenas $ 1 $ (uma vez que o mínimo / máximo foi encontrado, ele é trocado uma vez ao final da matriz).

Em termos de número de comparações, a classificação por bolha requer $ k \ vezes n $ comparações, onde $ k $ é a distância máxima entre a posição inicial de uma entrada e sua posição final, que geralmente é maior que $ n / 2 $ para valores iniciais uniformemente distribuídos. A ordenação por seleção, entretanto, sempre requer comparações $ (n-1) \ times (n-2) / 2 $.

Em resumo, o limite assintótico dá uma boa ideia de como os custos de um algoritmo crescem em relação ao tamanho da entrada, mas não diz nada sobre o desempenho relativo de diferentes algoritmos dentro do mesmo conjunto.

Comentários

• esta é até uma resposta muito boa
• qual livro você prefere?
• @GrijeshChauhan: Livros são uma questão de gosto, portanto, aceite qualquer recomendação com cautela. Eu pessoalmente gosto de Cormen, Leiserson e Rivest ‘ s ” Introdução aos algoritmos “, que oferece uma boa visão geral sobre vários tópicos, e Knuth ‘ s ” A arte da programação de computador ” série se você precisar de mais / todos os detalhes sobre qualquer tópico específico. Você pode querer verificar se a pergunta sobre os livros já foi feita aqui antes ou poste essa pergunta se não ‘ t.
• Para mim, terceiro parágrafo em sua resposta é a resposta real. Não os gráficos para entradas grandes, fornecidas em outra resposta.

A classificação por bolha usa mais tempos de troca, enquanto a classificação por seleção evita isso.

Ao usar a seleção de classificação, ela troca n vezes no máximo. mas ao usar a classificação por bolha, ela troca quase n*(n-1). E, obviamente, o tempo de leitura é menor do que o tempo de escrita, mesmo na memória. O tempo de comparação e outro tempo de execução podem ser ignorados. Portanto, os tempos de troca são o gargalo crítico do problema.

Comentários

• Acho que a outra resposta de Bartek é mais razoável, mas posso ‘ t votar ou comentário … Aliás, ainda acho que o tempo de escrita afeta mais e espero que ele possa levar isso em consideração se vir isso e concordar.
• Você não pode simplesmente ignorar o número de comparações, pois há casos de uso em que o tempo gasto para comparar dois itens pode exceder em muito o tempo gasto para trocar dois itens. Considere uma lista vinculada de strings extremamente longas (digamos, 100 mil caracteres cada). Ler cada string levaria muito mais tempo do que fazer a reatribuição de ponteiros.
• @IrvinLim Acho que você pode estar certo, mas posso ter que ver os dados estatísticos antes de mudar de ideia.