Slides in this set

Slide 1

Preview of page 1

Bubble Sort Example
9 2
6 6 9
9 2 11
12 9
11 3
12 1297
123 12
7
The bubble sort compares the numbers in pairs from left to right
exchanging when necessary.
TheInend
theof
third
the list
comparison,
has been the reached
9 is not
so larger
this is than
the end
the of
12the
so first
no pass. The 12
Now
Herethe
thenext
firstpair
number
of numbers
is compared
are compared.
to the second
Againandthe
as9itisis
the
larger
at the
exchange
end
The
The 12of
12 isthe
isis made.
list must
greater
larger
greaterthanWe
than
than be
the move
thethe
the
113
9 largest
7soon
so to compare
they
they number
are the
in the
areexchanged.
exchangednext
exchanged. listpair
and without
so is now in the
larger
they are
and exchanged.
so this pair is also exchanged.
correct
any position.
change toWe thenow
list. start a new pass from left to right.
Comparisons: 2
1
7
6
5
4
3 Swaps: 2
1
6
5
4
3…read more

Slide 2

Preview of page 2

Bubble Sort Example
First Pass
6 2 9 11 9 3 7 12
Second Pass
6 6
2 2 9 9
11 3
1197
113 11
7 12
The Notice
end ofthat
thethis
list has
timebeen
we doreached
not havesoto
this
compare
is the end
the of
last
thetwo
first pass. The 12
at the
numbers
end ofasthewelist
know
mustthe
be12
the
islargest
in position.
number This
in pass
the list
therefore
and so isonly
now in the
correct
requires
position.
6 comparisons.
We now start a new pass from left to right.
Comparisons: 11
70
1
9
8
13
12 Swaps: 7
60
1
9
8…read more

Slide 3

Preview of page 3

Bubble Sort Example
First Pass
6 2 9 11 9 3 7 12
Second Pass
2 6 9 9 3 7 11 12
Third Pass
2 6 9 3
9 7
3 9
9 7 11 12
The 11 and 12 are in the correct positions. The next pass therefore
only requires 5 comparisons.
Comparisons: 15
13
14
18
17
16 Swaps: 12
10
11…read more

Slide 4

Preview of page 4

Bubble Sort Example
First Pass
6 2 9 11 9 3 7 12
Second Pass
2 6 9 9 3 7 11 12
Third Pass
2 6 9 3 7 9 11 12
Fourth Pass
2 6 3
9 7
3 9
9 7 9 11 12
Each pass requires fewer comparisons. This time only 4 are needed.
Comparisons: 19
18
22
21
20 Swaps: 13
12
14…read more

Slide 5

Preview of page 5

Bubble Sort Example
First Pass
6 2 9 11 9 3 7 12
Second Pass
2 6 9 9 3 7 11 12
Third Pass
2 6 9 3 7 9 11 12
Fourth Pass
2 6 3 7 9 9 11 12
Fifth Pass
2 3
6 6
3 7 9 9 11 12
The list is now sorted but the algorithm does not "know" this until it
completes a pass with no exchanges.
Comparisons: 23
22
25
24 Swaps: 15
14…read more

Slide 6

Preview of page 6

Bubble Sort Example
First Pass
6 2 9 11 9 3 7 12
Second Pass
2 6 9 9 3 7 11 12
Third Pass
2 6 9 3 7 9 11 12
Fourth Pass
In this pass no exchanges have been made so the algorithm "knows"
2 6 3 7 9 9 11 12
that the list is sorted. It can therefore save time by not doing the final
pass. With other lists this check could save much more work.
Fifth Pass
2 3 6 7 9 9 11 12
Sixth Pass
2 3 6 7 9 9 11 12
Comparisons: 26
25
27 Swaps: 15…read more

Slide 7

Preview of page 7
Preview of page 7

Comments

No comments have yet been made

Similar Further Maths resources:

See all Further Maths resources »