bubblesort

Prévia do material em texto

��� ������� 	�
�����
�������
����������ff��fi�fl�ffi! � "� �$#%���&	
'
�(�&��ffi����ff�)�*�+
���,����*�-�&��
.�������+/�/ ,�0��)�1���
1 de 4 
 
1. Ordenação: Método das Bolhas (Bubble Sort) 
 
1.1. Ideia Básica 
 
Este processo de ordenação é o processo mais simples de entender, mais fácil de 
implementar, e talvez o método de ordenação mais conhecido. Contudo, este 
método não se trata de um algoritmo eficiente, ele é estudado principalmente para 
fins de desenvolvimento de raciocínio. 
O princípio básico deste método consiste na troca de valores entre posições 
consecutivas, fazendo com que os valores mais altos (ou mais baixos) salte
"borbulhem" para o fim do conjunto. 
 
1.2. Método 
 
Neste método, pretende -se ordenar os elementos de um array, que vão ser 
ordenados desde a primeira posição até à última posição, na qual em cada iteração 
da ordenação é calculado o maior/menor (maior elemento para ordenação por 
ordem decrescente, menor caso contrário) valor dos elementos que ainda faltam 
ordenar. O processo repete -se até que todos os elementos do array estejam 
ordenados. 
 
Para ordenar os seguintes dados por ordem crescente, processa-se do seguint
modo: 
10 8 6 2 16 4 18 11 14 12 
 
 Comparação dos dois elementos e trocar 
8 10 6 2 16 4 18 11 14 12 
 
 Comparação dos dois elementos e trocar 
 
8 6 10 2 16 4 18 11 14 12 
 
 Comparação dos dois elementos e trocar 
 
2�3 4�5�6�7 8�9�5�:�;�<�=�6�;�<�>�?�@�Aff5�B�C�D!E�E"3 <$F%5�6&8
G
7(>&4�D�?�4ff<)>*:+;�<�H�6�5*4-6&?�9.?�@�A�5+I�I H�J�4)71>�?
2 de 4 
 
 
O processo continua até alcançar o fim do array, omento em que inicia a próxim
iteração do processo de ordenação. 
 
No final da 1ª iteração o array fica do seguinte modo: 
 
8 6 2 10 4 16 11 14 12 18 
 
ficando o maior elemento em último lugar. Pode -se dizer que o elemento n.º 18 
saltou “borbulhou” para a s ua posição correcta. 
O processo volta a repetir-se deste o inicio, só que desta vez o processo pode parar 
antes do elemento n.º18 dado que este já se encontra no lugar correcto. 
 
Vamos continuar mais um passo no processo de ordenação: 
8 6 2 10 4 16 11 14 12 18 
 
 Comparação dos dois elementos e troca 
 
6 8 2 10 4 16 11 14 12 18 
 
Comparação dos dois elementos e troca 
 
6 2 8 10 4 16 11 14 12 18 
 
. . . 
O processo continua até que todo o array esteja ordenado. 
 
1.3. Algoritmo 
 
1. Percorrer todo o array des e o inicio até ao fim 
2. Verificar dois a dois todos os elementos e trocá-los se: 
“1º elemento for maior que 2º elemento” 
3. Voltar ao passo 1. se o array ainda não se encontrar ordenado. 
 
 
 
 
 
 
 
 
K�L M�N�O�P Q�R�N�S�T�U�V�O�T�U�W�X�Y�ZffN�[�\�]!^�^"L U$_%N�O&Q
`
P(W&M�]�X�MffU)W*S+T�U�a�O�N*M-O&X�R.X�Y�Z�N+b�b a�c�M)P1W�X
3 de 4 
 
 
1.4. Eficiência 
 
Tempos de Ordenação (sendo N o número de elementos a ordenar) 
• Melhor caso = N2 
• Média = N2 
• Pior caso = N2 
 
 
1.5. Implementação em C++ 
 
void BubbleSort(int array[], int num_elem) 
{ int aux; // Variável auxiliar para fazer a troca, caso necessário 
 for ( long int i=0; i <= num_elem -2; i++ ) 
 { 
 for ( long int j=0; j<= num_elem –2 -i; j++ ) 
 { 
 if ( array[j] > array[j+1] ) // Caso o elemento de uma posição meno 
 { // for maior que um elemento de uma posição 
 aux = array[j]; // maior, faz a troca. 
 array[ j] = array[j+1]; 
 array[j+1] = aux; 
 } // if 
 } // fo 
 } // fo 
} 
 
 
 
1.6. Exemplo 
 
Array com 10 elementos a ordenar por ordem crescente. 
10 8 6 2 16 4 18 11 14 12 
[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] 
 
1º passo de ordenação: 
Comparar: dados[0] > dados[1] e trocar se verdade 
8 10 6 2 16 4 18 11 14 12 
[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] 
 
 
 
 
 
d�e f�g�h�i j�k�g�l�m�n�o�h�m�n�p�q�r�sffg�t�u�v!w�w"e n$x%g�h&j
y
i(p&f�v�q�fffn)p*l+m�n�z�h�g*f-h&q�k.q�r�s�g+{�{ z�|�f)i1p�q
4 de 4 
 
 
2º passo de ordenação: 
Comparar: dados[1] > dados[2] e trocar se verdade 
8 6 10 2 16 4 18 11 14 12 
[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] 
 
3º passo de ordenação: 
Comparar: dados[2] > dados[3] e trocar se verdade 
8 6 2 10 16 4 18 11 14 12 
[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] 
 
4º passo de ordenação: 
Comparar: dados[3] > dados[4] e trocar se verdade 
8 6 2 10 16 4 18 11 14 12 
[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] 
 
 
Nota: 
O processo repete-se até que todos os elementos do array estejam ordenados. 
 
 
 
1.7. Resumo 
 
Método de ordenação extremamente lento, independente da ordem pela qual os 
elementos a ordenar se encontram.