Sort Kar do
array
↓
inc Sort Rama
Sorting
Algorithms
an =
[1 ,
0
,
1
,
2
,
9
,
3, 73
↓
5 -
1,0 , 1
,
2
,
3, 7
, 93
Contents
1. Bubble Sort
2. Selection Sort
3. Insertion Sort
4. Questions on Sorting
Ques: Check if array is sorted
an = 21 ,
0 ,
2
,
3, 4
,
3, 63 false
arr : E-1 ,
0 , 1 , 23 true
an = $1 , 1 ,
2
,
3 ,
7, 73
Bubble Sort >
- el also hai jusse array sort hota hai
arr = <3 ,
5 ,
1
,
4, 2 , 03
arr = 10 ,
1
,
2, 3 , 4 , 53
'n-1
passes honge
Bubble Sort
for (i 0 ton-2)S
for (i [ =
= 0 ton -
2)
i) &
I
2) S for (j 0 to n-2 -
for (j
=
ton
I
= 0 -
Im
b
-
3 3
3 1 =
4
-
2 + n
...
1
(n-152
-
n + n
-
-
i .
n o .
=
Bubble Sort (thoda better)
↓ an =
< 1
,
4
,
3 ,
4 , 53
before each
pass ,
we can
actually check if the
array
is sorted or not.
-
Bubble Sort (Optimised)
Itime comeexity
Best Case : O(n)
Aug .
Care : 0(n2]
Worst Lace : 0(ny
Bubble Sort (Reverse)
.
Q1 : Sort an
array
in descending order using bubble sort
M
.
Homework
Ques: Move all Zeros to end
arr =
2 1, 0
,
2 ,
3
,
0 , 4, 8, 0, 10
, 123
↓
av = 2 1 ,
2
,
3
,
4 , 8, 10 , 12 , 0 ,
0
, 03
Ques: Move all Zeros to end
i
arr =
2 1 , 2, 3 , 4 ,
8 ,
10
, 12
,
0, 0 , 03
j
Built-In
&
Sort /Merge Sort
↓
I
Tc =
O(nlogn)
AS .
. =
O(n)
Arrays sort(arr)
.
Collections , sort/list)
Selection Sort (Select smallest)
33 1-3 4 3 6 8 93
arr =
18 ,
4 ,
1 ,
9 .
- 3 ,
6
,
arr =
,
1 , ,
, , ,
33 1-3 1 4 5 6 8 93
1-3 6 arr = ,
= 4 1 9 8 ,
, , ,
, ,
arr , , ,
. ,
I
TC .
Th O
33
.
1- 3
.
6
.
= 1 1 9 8 ,
arr , , ,
. ,
Best : 0(n2 = n +n -
1+ n 2 -
... 2
Aug : 0(n2) n(n + 1)
arr =
1- 3 1 1 9 8 6
,
33 -
-
0(n2)
, ,
. ,
,
worst : 2
arr =
1- 3 ,
1 ,
4 ,
3 .
8 ,
6
,
93
Selection Sort (find largest first)
Homework
-
-
arr =
18 ,
4 ,
1 ,
9 .
- 3 ,
6
,
33
arr =
18 ,
4 ,
1 ,
3 .
- 3 ,
6
,
93
&
&
"
Ques: 2 Sum - Find a pair with given sum
target 9
27 0 103
=
4 3 2 8
avr =
, , , , , ,
(sort -
ocnlogn
[0 ,
2
,
3, 4, 7 ,
8, 10] -> Olu)
i j
oneogn + n) =
O(nlogn)
Ques: 2 Sum - Find a pair with given sum
av =
(7 ,
12 ,
26 ,
41 , 543 target = 50
j
i
Stability of Bubble & Selection Sort
avr g I
72
=
7, 34
& W
I
Selection Sont
bubble Sort
7, g
I 3 Y 72 g I 3 Y 727
unstable
Stable
Ques: Common Elements
a =
[3 ,
1 ,
2
,
1 , 1 , 4 ,
5
, 53 b :
16 ,
1 ,
1 ,
4 ,
4, 2 , 83
↓ Sort
I sort
>
-
a =
S1 ,
1 .
1, 2 ,
3
,
7 ,
5, 53 b= <1 ,
1
,
2
,
4
,
7
,
6
, 83
i j
ane = 31 ,
1 ,
2 , 73
HW: Union of 2 sorted Arrays
HW: Intersection of Arrays with Distinct
Ques: Kth smallest element
more similar to .
B S
>
-
.
Insertion Sort >
-
Adjacent Elements swapping
= (4173 9 10 S S
arr
arr = 50 11 3 Y 7 S 9)
j
there are 2
parts of away , sorted part & unsorted .
part
element sorted
Unsorted part Ka
penla part me sahi
jagah insert
Karna hai
Time Complexity of Insertion Sort
A
O(n) Array is
already sorted
Best Case
Average Case 0lnt
Worst Case 0(42) Array is sorted in des order
Auxiliary Space O(1)
i
awe =
4 123 Y s]
j
1 2 3 + y n
-
1 = m(1) -
swaps
= + + ...
2
Stability of Insertion Sort
arr = {4, 1,L 7, 3, 9, 1, 0, 8} 2
347 8 9
8 1
,
12
sort is stable sort
Insertion a
THANKYOU
Cuties