recategorized by
8,464 views
18 votes
18 votes
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.
recategorized by

2 Answers

Best answer
35 votes
35 votes

$1^{\text{st}}$ Pass:  $37 \ 52 \ 12 \ 11 \ 25  \ 92$

$2^{\text{nd}}$ Pass: $37 \ 12 \ 11 \ 25 \ 52 \ 92$

$3^{\text{rd}}$ Pass: $12 \ 11 \ 25 \ 37 \ 52 \ 92$

$4^{\text{th}}$ Pass: $11 \ 12 \ 25 \ 37 \ 52 \ 92$

$5^{\text{th}}$ Pass: $11 \ 12 \ 25 \ 37 \ 52 \ 92$

Why $5^{\text{th}}$ pass? In $4^{\text{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.

edited by
0 votes
0 votes

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

5th pass is done to check whether the elements are sorted or not. 6th pass would had been redundant and not the 5th pass. 

Related questions

21 votes
21 votes
2 answers
1
Kathleen asked Oct 8, 2014
4,953 views
Merge sort uses:Divide and conquer strategyBacktracking approachHeuristic searchGreedy approach
16 votes
16 votes
1 answer
2
Kathleen asked Oct 8, 2014
5,044 views
How many minimum spanning trees does the following graph have? Draw them. (Weights are assigned to edges).
35 votes
35 votes
6 answers
3
Kathleen asked Oct 8, 2014
47,634 views
For merging two sorted lists of sizes $m$ and $n$ into a sorted list of size $m+n$, we require comparisons of$O(m)$$O(n)$$O(m+n)$$O(\log m + \log n)$
21 votes
21 votes
1 answer
4
Kathleen asked Oct 8, 2014
3,909 views
In the following Pascal program segment, what is the value of X after the execution of the program segment?X := -10; Y := 20; If X Y then if X < 0 then X := abs(X) else ...