Bubble sort

this is a simple ppt of bubble sorting in c language...

3. Sorting
•Sorting takes an unordered collection and
makes it an ordered one.
512354277 101
1 2 3 4 5 6
5 12 35 42 77 101
1 2 3 4 5 6

4. Exchange/Bubble Sort:
It uses simple algorithm. It sorts by comparing each pair
of adjacent items and swapping them in the order. This
will be repeated until no swaps are needed. The
algorithm got its name from the way smaller elements
"bubble" to the top of the list.
It is not that much efficient, when a list is having more
than a few elements. Among simple sorting algorithms,
algorithms like insertion sort are usually considered as
more efficient.
Bubble sort is little slower compared to other sorting
techniques but it is easy because it deals with only two
elements at a time.

5. "Bubbling Up" the Largest Element
•Traverse a collection of elements
–Move from the front to the end
–“Bubble” the largest value to the end using
pair-wise comparisons and swapping
512354277 101
1 2 3 4 5 6

6. "Bubbling Up" the Largest Element
•Traverse a collection of elements
–Move from the front to the end
–“Bubble” the largest value to the end using
pair-wise comparisons and swapping
512354277 101
1 2 3 4 5 6
Swap
42 77

7. "Bubbling Up" the Largest Element
•Traverse a collection of elements
–Move from the front to the end
–“Bubble” the largest value to the end using
pair-wise comparisons and swapping
512357742 101
1 2 3 4 5 6
Swap
35 77

8. "Bubbling Up" the Largest Element
•Traverse a collection of elements
–Move from the front to the end
–“Bubble” the largest value to the end using
pair-wise comparisons and swapping
512773542 101
1 2 3 4 5 6
Swap
12 77

9. "Bubbling Up" the Largest Element
•Traverse a collection of elements
–Move from the front to the end
–“Bubble” the largest value to the end using
pair-wise comparisons and swapping
577123542 101
1 2 3 4 5 6
No need to swap

10. "Bubbling Up" the Largest Element
•Traverse a collection of elements
–Move from the front to the end
–“Bubble” the largest value to the end using
pair-wise comparisons and swapping
577123542 101
1 2 3 4 5 6
Swap
5 101

11. "Bubbling Up" the Largest Element
•Traverse a collection of elements
–Move from the front to the end
–“Bubble” the largest value to the end using
pair-wise comparisons and swapping
77123542 5
1 2 3 4 5 6
101
Largest value correctly placed

12. Bubble Sort
1.In each pass, we compare adjacent elements and swap them if they are
out of order until the end of the list. By doing so, the 1
st
pass ends up
“bubbling up” the largest element to the last position on the list
2. The 2nd pass bubbles up the 2
nd
largest, and so on until, after N-1
passes, the list is sorted.
Example:
Pass 1 89 | 45 68 90 29 34 17 Pass 2 45 | 68 89 29 34 17
45 89 | 68 90 29 34 17 45 68 | 89 29 34 17
68 89 | 90 29 34 17 68 89 | 29 34 17
89 90 | 29 34 17 29 89 | 34 17

29 90 | 34 17 34 89 | 17
34 90 | 17 17 89
17 90
45 68 89 29 34 17 90 45 68 29 34 17 89
largest 2
nd
largest

13. The “Bubble Up” Algorithm
index <- 1
last_compare_at <- n – 1
loop
exitif(index > last_compare_at)
if(A[index] > A[index + 1]) then
Swap(A[index], A[index + 1])
endif
index <- index + 1
endloop

14. No, Swap isn’t built in.
Procedure Swap(a, b isoftype in/out Num)
t isoftype Num
t <- a
a <- b
b <- t
endprocedure // Swap
LB

15. Items of Interest
•Notice that only the largest value is
correctly placed
•All other values are still out of order
•So we need to repeat this process
77123542 5
1 2 3 4 5 6
101
Largest value correctly placed

16. Repeat “Bubble Up” How Many Times?
•If we have N elements…
•And if each time we bubble an element,
we place it in its correct location…
•Then we repeat the “bubble up”
process N – 1 times.
•This guarantees we’ll correctly
place all N elements.

17. “Bubbling” All the Elements
77123542 5
1 2 3 4 5 6
101
5421235 77
1 2 3 4 5 6
101
42 5 3512 77
1 2 3 4 5 6
101
42 35 512 77
1 2 3 4 5 6
101
42 35 12 5 77
1 2 3 4 5 6
101
N

-

1

18. Reducing the Number of Comparisons
12 35 42 77 101
1 2 3 4 5 6
5
77123542 5
1 2 3 4 5 6
101
5421235 77
1 2 3 4 5 6
101
42 5 3512 77
1 2 3 4 5 6
101
42 35 512 77
1 2 3 4 5 6
101

19. Reducing the Number of Comparisons
•On the N
th
“bubble up”, we only need to
do MAX-N comparisons.
•For example:
–This is the 4
th
“bubble up”
–MAX is 6
–Thus we have 2 comparisons to do
42 5 3512 77
1 2 3 4 5 6
101

20. Putting It All Together

21. N is … // Size of Array
Arr_Type definesa Array[1..N] of Num
Procedure Swap(n1, n2 isoftype in/out Num)
temp isoftype Num
temp <- n1
n1 <- n2
n2 <- temp
endprocedure // Swap

22. procedure Bubblesort(A isoftype in/out Arr_Type)
to_do, index isoftype Num
to_do <- N – 1
loop
exitif(to_do = 0)
index <- 1
loop
exitif(index > to_do)
if(A[index] > A[index + 1]) then
Swap(A[index], A[index + 1])
endif
index <- index + 1
endloop
to_do <- to_do - 1
endloop
endprocedure // Bubblesort
I
n
n
e
r

l
o
o
p
O
u
t
e
r

l
o
o
p

24. Summary
•“Bubble Up” algorithm will move largest
value to its correct location (to the right)
•Repeat “Bubble Up” until all elements are
correctly placed:
–Maximum of N-1 times
•We reduce the number of elements we
compare each time one is correctly placed

25. Thank You