>> [Música tocando]
DOUG LLOYD: Tudo bem, então bubble sort é um algoritmo
você pode usar para classificar um conjunto de elementos.
Vamos dar uma olhada em como ele funciona.
>> Assim, a idéia básica por trás bubble sort é este.
Nós geralmente querem mover superior elementos valorizados geralmente para a direita,
e diminuir elementos valorizados em geral para a esquerda, como seria de esperar.
Queremos que as coisas mais baixas para estar em o início, e as coisas mais elevadas
ser no final.
>> Como vamos fazer isso?
Bem no código pseudocódigo, poderíamos dizer, vamos
definir um contador de swap para um valor diferente de zero.
Vamos ver por que fazemos isso em um segundo.
E, depois, repetir o seguinte processo até que o contador de swap é 0,
ou até que não fazemos swaps em tudo.
>> Reinicie o contador de swap para 0 se não é já 0.
Em seguida, olhar para cada par adjacente de elementos.
Se esses dois elementos são não em ordem, trocá-los,
e adicionar 1 para o contador de swap.
Se você está pensando em isso antes de visualizá-la,
notar que este irá mover mais baixo elementos valiosos para a esquerda
e elementos para a direita valorizado superior, efetivamente fazendo o que nós queremos fazer,
que é mover esses grupos de elementos em que maneira.
Vamos visualizar como este pode parecer usando a nossa gama
que foi utilizado para testar estes algoritmos.
Nós temos uma matriz unsorted aqui novamente, indicado por todos os elementos
sendo a vermelho.
E eu definir o meu contador de swap para um valor diferente de zero.
Eu escolhi arbitrariamente 1-- negativo não é 0.
Queremos repetir este processo até que o contador de swap é 0.
É por isso que eu definir a minha troca contador para um valor diferente de zero,
porque caso contrário o contador de swap seria 0.
Nós nem sequer começar a processo do algoritmo.
Então, novamente, os passos é-- redefinir o contador de swap
a 0, em seguida, olhar para cada lado par, e se eles estão fora de ordem,
trocá-los, e adicionar 1 para o contador swap.
Então, vamos começar esse processo.
Então a primeira coisa que fazemos é vamos definir o contador de swap a 0,
e, depois, começar a olhar em cada par adjacente.
>> Assim que começamos a olhar para 5 e 2.
Nós vemos que eles estão fora de ordem e para que trocá-los.
E nós adicionamos 1 ao contador swap.
Portanto, agora o nosso contador de swap é um, e 2 e 5 foram trocados.
Agora vamos repetir o processo novamente.
>> Nós olhamos para a próxima par adjacente, 5 e 1-- eles são também fora de ordem,
assim que nós trocá-los e adicionar 1 para o balcão swap.
Então, olhamos para 5 e 3.
Eles estão fora de ordem, por isso, trocar eles e nós adicionamos 1 ao contador swap.
Então, olhamos para 5 e 6.
Eles estão em ordem, por isso, na verdade, não precisa trocar qualquer coisa neste momento.
Então, olhamos para 6 e 4.
Eles também estão fora de ordem, por isso, trocar eles e nós adicionamos 1 ao contador swap.
>> Agora, observe o que aconteceu.
Nós movemos 6 todo o caminho até o fim.
Então, na seleção tipo, se você tiver visto que o vídeo, o que fizemos foi
acabamos mudando a menores elementos em construção
a matriz classificada essencialmente da esquerda para a direita, menor para o maior.
No caso de bubble sort, se estamos seguindo este algoritmo em particular,
nós estamos indo realmente para ser a construção de a matriz classificada da direita
para a esquerda, maior para a menor.
Temos efetivamente borbulhar 6, a O maior valor, todo o caminho até ao fim.
>> E assim podemos agora declarar que que é ordenada,
e no futuro iterations-- passando a matriz novamente--
não temos de considerar 6 anymore.
Nós só temos que considerar os elementos não triados
quando nós estamos olhando para pares adjacentes.
Então, temos que terminar uma passar por bubble sort.
Então agora vamos voltar para a questão, repetir até que o contador de swap é 0.
Bem, o contador de swap é 4, então vamos
para continuar a repetir esse processo novamente.
>> Nós estamos indo para redefinir o contador de swap a 0, e olhar para cada par adjacente.
Então, vamos começar com dois e eles são 1-- fora de ordem, de modo que trocá-los
e nós adicionamos 1 ao contador swap.
2 e 3, eles estão em ordem.
Nós não precisamos fazer nada.
3 e 5 estão em ordem.
Nós não precisamos fazer nada lá.
>> 5 e 4, eles estão fora de ordem, e por isso,
precisa trocá-los e adicionar 1 para o balcão swap.
E agora nós movemo 5, o segundo maior elemento,
para o fim da porção não triados.
Então agora podemos chamar isso parte da porção classificada.
>> Agora você está olhando para o tela e provavelmente pode dizer,
como pode I, que a matriz é classificada no momento.
Mas não podemos provar isso ainda.
Não temos uma garantia que está classificado.
Mas é aí que o swap contador vai entrar em jogo.
>> Então, nós completamos um passe.
O contador de swap é de 2.
Então, nós estamos indo para repetir este processo novo,
repetir até que o contador de swap é 0.
Reinicie o contador de swap a 0.
Então, vamos redefini-la.
>> Agora olhe para cada par adjacente.
Isso é em ordem, 1 e 2.
2 e 3 estão em ordem.
3 e 4 estão em ordem.
Portanto, neste ponto, observe nós completamos olhando para cada par adjacente,
mas o contador de swap ainda é 0.
>> Se não temos de mudar quaisquer elementos, em seguida, eles
devem estar em ordem, por virtude deste processo.
E assim uma eficiência de tipos, que os cientistas da computação que amamos,
está agora podemos declarar toda a matriz deve
são ordenados, porque não ter que trocar todos os elementos.
Isso é muito bom.
>> Então, qual é o pior caso cenário com bubble sort?
No pior caso, a matriz é a fim completamente inversa,
e por isso temos de bolha cada dos grandes elementos todos
a maneira através da matriz.
E nós também temos que efetivamente bolha todos os pequenos elementos de volta
em toda a extensão da matriz, também.
Assim, cada um dos elementos n tem de se mover entre todos os outros elementos n.
Então esse é o pior cenário possível.
No melhor dos casos cenário, porém, este é
ligeiramente diferente da seleção de classificação.
A matriz é já classificadas quando vamos.
Não temos de fazer qualquer swaps sobre a primeira passagem.
Por isso, pode ter que olhar pelo menos elementos, certo?
Nós não temos que repetir este processar um certo número de vezes.
>> Então, o que isso significa?
Então, qual é o pior cenário para bubble sort, eo que é
o melhor cenário para bubble sort?
Você acho que isso?
No pior dos casos você tem que fazer uma iteração em todos os elementos n vezes n.
Assim, o pior caso é n ao quadrado.
>> Se a matriz é perfeitamente ordenada, porém, você só
tem que olhar para cada os elementos de uma vez.
E se o contador de permuta ainda é 0, você pode dizer que esta matriz é classificada.
E assim, no melhor dos casos, isto é realmente melhor do que a seleção
sort-- é omega de n.
>> Eu sou Doug Lloyd.
Este é CS50.