C++

SELECTION & INSERTION

SORT
Lecture-22

Raghav Garg
Today’s checklist

1) Sorting
2) Selection sort Algorithm
3) Time complexity and space complexity
4) Insertion sort Algorithm
5) Time complexity and space complexity
6) Stability of both
 Array size
Selection Sort Algorithm
-> i

↓ de
S 3 I Y 2 n
arr=

↓ ↓
Steps -

I 3 S 4 2 n
-1

se
·
Orange Away me
↓ ↓

min ele ko first 2 S Y 3 n-

2
I

ble he sath swap ↓d

I 2 3 Y S n-

3
·in-l total swaps
2 3 Y S
sorted · I
Selection sort Code and dry run Y
* I 23
i < 3
an 4 -
296
=
i 0, 1,2

-
2496

2496

-
2469

i=

0X & 3

min= EFEMAX Y-X IMAX YMAX 96

mindx =
-1. 4 X -XX-X & 3
Time and Space complexity
space complexity
Time complexity
·(1)
C
Best ase O(n7

Avg. Case 0(nY

Worst Case O(n2)

Time and Space complexity
1 2 3 Y
des

I 23 Y
Stability. If on Sat
132
5, S2

So. Is
3 S,

se
Sc

s,
stable

unstable
sort

atthe
Selection SortAlgorithm

↓ L
I 3 2
Si S
2

↓ ↓

I 52 Si 3 2

↓ d
I 2 S, 3 S2

dd

I 2 3 Si S2

I 2 3 5, Sc - stable
 Usecase s
- >
cost of swapping v

Selection Sort Algorithm

starting se'h' min de
↓ ↓
3 I of
out i

5, S
2
2

If size of away is
d ↓
small
I Sc 2 3 5,
L d

I 2 Sz 3 S,

↓d
12 3 52 Si

I 23 S2 S, unstable
Insertion Sort Algorithm -
unsorted
sorted &
I Y 2
S 3

I Y 2
3 S

135 Y 2

13 4s 2

1 2 3 4 S
Insertion Sort Algorithm 38 40424446

S - I 42

3 S 142

315 42

135 y2

I 34S2

I 3425

I 3 2 Y S

I 2 3 4 S (Sort)
Insertion Sort Algorithm
S - I Y 2
forlint i =1;i < n
=

-1;i +)[
+

Il
intj= i;
142
3 S
while (j1
if(avr[;) >, air (j-17) break;
315 42
if (ar [i] (s.-1])
<arr

135 y2 Swap (aw (i), [j-17);

awr

j --,
I 34S2
3
3
I 3425

I 32 "S

I 2 34 S
 n 4
=

Insertion sort Code and dry run

D 123
n-1 times
-
arr 452
=
I

3 Y 2 I

32 4 I

23 4 I

i x& B
=
Y
2 3 1 Y

j x0R,
=
B4X0
2 13 Y

1 2 3 Y
Insertion sort Code and dry run
O I 2 3

arr= I - 3 Y

I 2 3 Y

1 2 3 4

1 2 3 4

i 14B
=

j x23
=
Time and Space complexity
Worst Care -> O(n

Avg. Cale e O(nY

Best Case - 0 (n)

Stability of Insertion and Selection Sort
--
-
-

only adjacent swaps just like bubble sort

Stable Sorting Algorithm

4, 422 1

4, 2 Y= I

2 Y, Y2 I

2 Y, 1 Yz

2 1 Y, Y

12 4, 42 stability"
Ques : What will the array look like after the first
iteration of selection sort [2,3,1,6,4]
↑
a) [1,2,3,6,4] [132647
b) [1,3,2,4,6]
Y
c) [1,3,2,6,4]
d) [2,3,1,4,6]
Ques : Sort a String in decreasing order of values
associated after removal of values smaller than X.
-

L Repeat

Classwork
L

Reverse
THANK YOU