Por que a classificação de seleção é mais rápida que a de bolhas?

28

Está escrito na Wikipedia que "... o tipo de seleção quase sempre supera o tipo de bolha e o tipo de gnomo". Alguém pode me explicar por que o tipo de seleção é considerado mais rápido que o de bolhas, mesmo que ambos:

  1. Pior complexidade do tempo : O(n2)

  2. Número de comparações : O(n2)

  3. Melhor complexidade de tempo :

    • Tipo de bolha: O(n)
    • Tipo de seleção: O(n2)
  4. Complexidade média do tempo do caso :

    • Tipo de bolha: O(n2)
    • Tipo de seleção: O(n2)
RYO
fonte

Respostas:

32

Todas as complexidades que você forneceu são verdadeiras, porém são fornecidas na notação Big O ; portanto, todos os valores e constantes aditivos são omitidos.

Para responder sua pergunta, precisamos nos 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:

  • Tipo de bolha : 12(N2NlnN(γ+ln21)N)+O(N)
  • Tipo de inserção : 14(N2N)+NHN
  • Tipo de seleção : (N+1 1)HN-2N

Agora, se você traçar essas funções, obterá algo como isto: enredo plot2

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

Essa 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 classificar, podemos permutar aleatoriamente a sequência de entrada (usando qualquer método) para obter o caso médio.

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

Bartosz Przybylski
fonte
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 que o tempo necessário para classificar?
Sasho Nikolov 07/07
11
NNO(NregistroN)N
Acho que estava com sono, você está certo, a sequência pode ser permutada em tempo linear.
Sasho Nikolov 08/07/2013
HN=Θ(euogN)
Gama = 0,577216 é a constante de Euler-Mascheroni. O capítulo relevante é "The Art of Programming" vol 3, seção 5.2.2 pág. 109 e 129. Como você plotou a caixa de classificação de bolhas exatamente especialmente o termo O (sqrt (N))? Você acabou de negligenciar?
mxmlnkn
11

O

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

n/41 1

k×nkn/2(n-1 1)×(n-2)/2 comparações.

Em resumo, o limite assintótico fornece uma boa idéia de como os custos de um algoritmo aumentam com relação ao tamanho da entrada, mas não diz nada sobre o desempenho relativo de algoritmos diferentes no mesmo conjunto.

Pedro
fonte
11
isso é ainda muito boa resposta
Grijesh Chauhan
qual livro você prefere?
Grijesh Chauhan
@GrijeshChauhan: Os livros são uma questão de gosto, então faça qualquer recomendação com um pouco de sal. Pessoalmente, gosto de "Introduction to Algorithms", de Cormen, Leiserson e Rivest, que fornece uma boa visão geral de vários tópicos, e da série "The Art of Computer Programming" de Knuth, se você precisar de mais / todos os detalhes sobre qualquer tópico específico. Convém verificar se a questão dos livros já foi feita aqui antes ou postá-la, se não tiver.
Pedro
Para mim, o terceiro parágrafo da sua resposta é a resposta real. Não são os gráficos para entradas grandes, dados em outra resposta.
overexchange
3

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 seleção, alterna os ntempos no máximo. mas ao usar o tipo de bolha, ele troca quase n*(n-1). E, obviamente, o tempo de leitura é menor que o tempo de gravação, 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.

simonmysun
fonte
Acho que a outra resposta de Bartek é mais razoável, mas não posso votar ou comentar ... BTW ainda acho que o tempo de escrita afeta mais e espero que ele possa levar isso em consideração se vir isso e concordar.
simonmysun
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 sequências extremamente longas (digamos 100k caracteres cada). A leitura de cada sequência levaria muito mais tempo do que a reatribuição do ponteiro.
Irvin Lim
@ IrvinLim Acho que você pode estar certo, mas talvez eu precise ver os dados estatísticos antes de mudar de idéia.
simonmysun