Como é realizada a ordenação de um vetor pelo método Bubble Sort ?
a) Ordenação é realizada com base na teoria dividir e conquistar.
b) É realizada em uma única direção, percorrendo o vetor diversas vezes até que o mesmo esteja ordenado.
c) A ordenação é realizada de maneira bidirecional, percorrendo e ordenando o vetor na ida e na volta.
d) A ordenação é realizada sempre da direita para a esquerda.
e) Nda.
Assinar:
Postar comentários (Atom)
2 comentários:
Resposta correta C
Errado.
O Bubble sort original percorre várias vezes o vetor na mesma direção: http://en.wikipedia.org/wiki/Bubble_sort
Step-by-step example
Let us take the array of numbers "5 1 4 2 8", and sort the array from lowest number to greatest number using bubble sort algorithm. In each step, elements written in bold are being compared.
First Pass:
( 5 1 4 2 8 ) ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps them.
( 1 5 4 2 8 ) ( 1 4 5 2 8 ), Swap since 5 > 4
( 1 4 5 2 8 ) ( 1 4 2 5 8 ), Swap since 5 > 2
( 1 4 2 5 8 ) ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.
Second Pass:
( 1 4 2 5 8 ) ( 1 4 2 5 8 )
( 1 4 2 5 8 ) ( 1 2 4 5 8 ), Swap since 4 > 2
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.
Third Pass:
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
Finally, the array is sorted, and the algorithm can terminate.
Postar um comentário