The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+11 votes
510 views
Consider the following sequence of numbers:

$$92, 37, 52, 12, 11, 25$$

Use bubblesort to arrange the sequence in ascending order. Give the sequence at the end of each of the first five passes.
asked in Algorithms by Veteran (59.7k points)
edited by | 510 views
+2
$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.
+1

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

2 Answers

+17 votes
Best answer

$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.

answered by Boss (19.9k points)
edited by
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

answered by Boss (11.7k points)

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

43,964 questions
49,518 answers
162,487 comments
65,759 users