C++

BUBBLE SORT
Lecture-21

Raghav Garg
Today’s checklist

1) Sorting
2) Bubble sort Algorithm
3) Time complexity and space complexity
4) Bubble sort optimization
5) Stable and unstable sort
6) I questions
What is sorting?
S 3 I U 2
arr=

order 2 34S
To sort:
put in
ascending
e
order
Increasing
Non-Decreasing
Sort in
the elements in
-
put
decreasing -> S U 3 2 I
order
order descending
Bubble sort algorithm
1st pass
-

S I y 32
aws -

13 4 3 2

145 3 2

143 S 2

w
3 2 S
14
Bubble sort algorithm
rd

no
3 pass
2 Pass
~v
v
I 3 2 Y S
3 2 S
I 4
~
~
I 3 2 U S
U 3 2 S
I
W W ~
3 Y S
~ I 2
Y 2 S
13
~ -
2 Y S
I 3
Bubble sort algorithm
nd
1stpass: 2 Pass:
-
-
V
2 I S
S Y 3 2 I Y 3
~

Y 2 I S
S 3 2 I 3
Y

3 2 Y I ⑤
32 I
Y 3
- ~

2 I Y S
S I 3
Y 32
V
2 I S
Y 3
Bubble sort algorithm
3rd pass: :
e
v W ~
~ 2 I 3 YS
2 I Y S
3
~ ~
-
W
2 E YS
3 I Y ⑤ 1
2

~ v W
3 Y S
2 I

i5
Formula -

n1) ->
St=
Observations:
-

the max
nth element goes to its
rightposition
·
In each pass

'n'elements, then we
require atmost'n-1 passes
·
If there are

to sort.

elements
adjacent if
Algorithm:
-
In each pass swap 2

arr(i]> arr (i+1]

Example
3 2 I
awe - Y 3
n 4
=

3 Y 2 I

3 2 4 I

T.C. 0(n)
+
v

3 21 Y

2nd pass 3rd pass Tn.0- (n-1)*(-1)

I I
243 U
23 Y

2 13 Y
1 2 3 Y

1 2 3 Y
2 13 Y
Time and Space complexity
i 0, 1,2,
=
. . .
n-2

i 0, 1
j 0,1,2,..n 2 n -
= -

3 n 2
j
n
0,1,2,
-
-

=
1,
=
. . .

-Y n 3
j
-

0, 1, 2..n
i 2,
=
=

: -> 2

i n
= -

2,j 0
=
- 1

T.n.0 -> 1 2
+
+
3+...n-1

=(n
+ 1) 1) - T.C. O(n)
-
=
Time and Space complexity
O(ni)
Time complexity ->

complexity 0(1)
space
+
Can we optimize it further ?
2nd pass
1stpass
34 I 2 34S
S I 2

I 3 "S
I S 2
3 Y 2

2 3 4 S
1
s 3Y
I 2

12 3 Y S
2 3 SY
I

2 3 4 S
Y S I
I 2 3

L
break;
Sorted
Can we optimize it further ?
Implexity:
Best Case:O(n)

Avg. Case:OlnY

Worst Case:O(n
 sorted
if is not
away, find
Given it
Ques: an or

aw: (1, 2, 3, 43 0(n)

bool true;
flag: //sorted

lint i 0;i 1;i + 3

if (aw[i] [i+1]) (

1
> an

fale
i

flag"
3

if (flag =
true)
=

- sorted

else - unsorted
Stable and Unstable sort
arr- 1 2 3 5, S
2

Conclusion - Bubble Sort is a stable sort

L 23 S. Sz - Stable
after sort

I 23 5, 5,- Unstable
Ques : How much maximum swaps are needed to
sort array of length 6 ?
ai= 6 S 4 3 2 1
->

d
total no.
of swap=
total no.
of operations

n 6
= i5
swaps
I =
Ques : Sort a String in decreasing order of values
associated after removal of values smaller than X.

strings:
"AzY2 Jmx";
x BD

Sta "242xx";
=

=22YXX
Sort
Ques : Push zeroes to end while maintaining the
relative order of other elements.
'Bubble Sort Ki Importance'
arr= [5, 0, 1, 2, 0,0,4,0,33
arr=[5, 1, 2, 4, 3,0,0,0,03
Summary Bubble Sort - T.C. O(n)
-

Inbuilt Sort - T.C. e

THANK YOU