736 views
Consider the following sequence of numbers:$$92, 37, 52, 12, 11, 25$$ Use Bubble sort to arrange the sequence in ascending order. Give the sequence at the end of each of the first five passes.

edited | 736 views
+4
$Remark:$
1. Bubble up the largest element to the end.
2. Array will be divided into two sorted and unsorted part.
3. If no swap happens in any of the pass, then terminate the procedure, and output all the elements.
4. Bubble sort is adaptive, stable and in-place algorithm.
+3

According to Cormen, moving smallest element to beginning

1st Pass:  11, 92, 37, 52, 12, 25

2nd Pass: 11, 12, 92, 37, 52, 25

3rd Pass: 11, 12, 25, 92, 37, 52

4th Pass: 11, 12, 25, 37, 92, 52

5th Pass: 11 12 25 37 52 92

$1$st Pass:  $37 \ 52 \ 12 \ 11 \ 25 \ 92$

$2$nd Pass: $37 \ 12 \ 11 \ 25 \ 52 \ 92$

$3$rd Pass: $12 \ 11 \ 25 \ 37 \ 52 \ 92$

$4$th Pass: $11 \ 12 \ 25 \ 37 \ 52 \ 92$

$5$th Pass: $11 \ 12 \ 25 \ 37 \ 52 \ 92$

Why 5 th pass ? In 4 th pass, the array is already sorted, but the algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.

by Boss (19.9k points)
edited
0
Since 5 th pass is redundant, we can set a flag in such a way that we will come out of outer for loop after 4 passes ... in that cases only 4 passes ...
+2
How come? In 5th pass you will get to know there are no new swaps and hence the list must be sorted. If there would have been a 6th pass, it would be redundant.
+1 vote

1st Pass:  37 52 12 11 25 92

2nd Pass: 37 12 11 25 52 92

3rd Pass: 12 11 25 37 52 92

4th Pass: 11 12 25 37 52 92

5th Pass: 11 12 25 37 52 92

by Boss (12.1k points)