Sorting - Part 1 | Selection Sort, Bubble Sort, Insertion Sort | Strivers A2Z DSA Course

Summary

This video lecture from the Strivers A to Z DSA course covers essential sorting techniques for data structures and algorithms, focusing on selection sort, bubble sort, and insertion sort. The presenter explains each algorithm step-by-step, provides pseudocode, and discusses their time complexities, emphasizing the importance of these skills for placement interviews.

Takeaways

• 📚 The video is a lecture from the 'Strivers A to Z DSA' course, which claims to be India's most in-depth course on Data Structures and Algorithms (DSA) with 456 modules.
• 🔍 The course is comprehensive and is recommended for those preparing for placements, as it covers a wide range of topics including sorting techniques which are often asked in interviews.
• 🔑 The lecture specifically covers three sorting algorithms: selection sort, bubble sort, and insertion sort, starting with selection sort as the first step.
• 💡 Selection sort is explained through a step-by-step process where the minimum element is selected and swapped to the beginning of the array, and this process is repeated until the array is sorted.
• 📝 Pseudo code is provided to help understand how to implement the selection sort algorithm in different programming languages like C++, Java, and Python.
• 🔄 The time complexity of selection sort is analyzed to be O(n^2) for the worst and average cases, but it can be optimized in the best case scenario where the array is already sorted.
• 🎯 The bubble sort algorithm is explained, which involves repeatedly stepping through the list, comparing adjacent elements, and swapping them if they are in the wrong order.
• 🛠️ The video provides an optimized version of the bubble sort algorithm that includes a 'did swap' flag to potentially break early if the array is already sorted, leading to a best-case time complexity of O(n).
• 📈 The insertion sort algorithm is also discussed, which builds the final sorted array one item at a time, with each new element being placed in its correct position from the sorted portion of the array.
• 🔍 The time complexity of insertion sort is explained as O(n^2) in the worst and average cases, but it can be O(n) in the best case when the array is already sorted.
• 🌐 The video also promotes a learning platform called 'Learn by' that offers data science and full stack development programs, with benefits like live classes, Capstone projects certified by IBM, and job assistance.

Q & A

What is the claim made by the speaker about the Strivers A to Z DSA course in India?

The speaker claims that the Strivers A to Z DSA course is the most in-depth course on Data Structures and Algorithms (DSA) in India, with 456 modules, which is more comprehensive than any other paid or free courses available in the market.

What are the sorting techniques covered in the 'Step 2' of the DSA course?

In 'Step 2' of the DSA course, the speaker covers important sorting techniques including selection sort, bubble sort, and insertion sort.

What is the primary purpose of the 'Learn by' platform mentioned in the script?

The 'Learn by' platform is an edtech platform that offers data science and full stack development programs, dedicated to professionals, providing live online classes, one-on-one mentorship, doubt sessions, and opportunities to work on industry-based Capstone projects certified by IBM.

How does the selection sort algorithm work according to the script?

The selection sort algorithm works by repeatedly finding the minimum element from the unsorted part of the array and swapping it with the element at the beginning of the unsorted part.

What is the time complexity of the selection sort algorithm?

The time complexity of the selection sort algorithm is O(n^2), which is the worst, average, and best-case scenario due to the nested loops that iterate through the array.

What is the key difference between the selection sort and bubble sort algorithms?

The key difference is that selection sort selects the minimum element and places it at the beginning, while bubble sort pushes the maximum element to the end through adjacent swaps.

How can the bubble sort algorithm be optimized to improve its time complexity?

The bubble sort algorithm can be optimized by introducing a flag that checks if any swaps have occurred in a pass. If no swaps occur, the algorithm can terminate early as the array is already sorted, leading to a best-case time complexity of O(n).

What is the basic concept of the insertion sort algorithm?

The basic concept of the insertion sort algorithm is to take each element and place it in its correct position within the array by comparing and shifting elements as necessary.

How does the speaker describe the process of shifting elements in the insertion sort algorithm?

The speaker describes the process as taking an element and comparing it with the elements on its left, shifting the larger elements to the right until the correct position is found for the element being inserted.

What is the time complexity of the insertion sort algorithm in the best case?

The best-case time complexity of the insertion sort algorithm is O(n), which occurs when the input array is already sorted, and no shifts are needed.

Outlines

00:00

📚 Introduction to DSA Course and Sorting Techniques

The speaker introduces an in-depth Data Structures and Algorithms (DSA) course, emphasizing its comprehensive nature with 456 modules. The course is positioned as a must-have for placement preparation. The focus then shifts to sorting techniques, which are crucial for placements. The first sorting algorithm discussed is selection sort, followed by others like bubble sort and insertion sort. The speaker also promotes an educational platform called 'Learn by', which offers data science and full stack development programs, live classes, and opportunities to work on industry-based projects certified by IBM.

05:01

🔍 Detailed Explanation of Selection Sort Algorithm

The paragraph delves into the selection sort algorithm, explaining its process of selecting the minimum element from an unsorted array and swapping it with the first element. The speaker illustrates the steps of the algorithm with an example, showing how each element is compared and swapped to its correct position. The explanation includes a pseudocode representation and a discussion on the algorithm's implementation in different programming languages. The paragraph concludes with a step-by-step breakdown of how the array is sorted using selection sort.

10:03

💡 Observations and Pseudocode for Selection Sort

This section continues the discussion on selection sort, focusing on the observation of the algorithm's process. The speaker outlines the steps involved in finding the minimum element and swapping it with the first element of the unsorted portion of the array. The explanation includes a detailed pseudocode that demonstrates how to implement selection sort, emphasizing the importance of observing the array and swapping elements to achieve a sorted sequence.

15:04

📈 Time Complexity Analysis of Selection Sort

The speaker analyzes the time complexity of the selection sort algorithm, explaining that it has a time complexity of O(n^2) in the worst and average cases. The analysis is based on the summation of the first n natural numbers, which approximates to n(n+1)/2. The speaker also mentions that the best-case scenario, although not typically considered for selection sort, would be O(n) if the array is already sorted.

20:07

🔄 Understanding Bubble Sort Algorithm

The paragraph introduces the bubble sort algorithm, explaining its process of pushing the maximum element to the end through adjacent swaps. The speaker uses an example to illustrate how the algorithm works, showing how elements are compared and swapped to move the largest element to its correct position at the end of the array. The explanation includes a step-by-step breakdown of the algorithm's process and a discussion on its implementation.

25:07

🔄 Optimizing Bubble Sort with Early Termination

This section discusses an optimization for the bubble sort algorithm. The speaker introduces a method to break out of the sorting loop early if no swaps are made during a pass, indicating that the array is already sorted. This optimization can reduce the time complexity to O(n) in the best case, although the average and worst-case complexities remain O(n^2). The speaker emphasizes the importance of understanding the algorithm's behavior in different scenarios.

30:08

🚀 Introduction to Insertion Sort Algorithm

The speaker introduces the insertion sort algorithm, explaining its process of taking each element and placing it in its correct position in the sorted portion of the array. The explanation includes a detailed example of how the algorithm works, showing how elements are compared and shifted to their correct positions. The speaker also discusses the algorithm's implementation and provides a step-by-step guide on how to perform insertion sort.

35:12

🔍 Detailed Walkthrough of Insertion Sort

This paragraph provides a detailed walkthrough of the insertion sort algorithm, focusing on how each element is compared with the elements to its left and shifted accordingly. The speaker illustrates the process with examples, showing how elements are moved left until they are in the correct order. The explanation includes a discussion on the algorithm's implementation and the conditions under which elements are swapped.

40:13

📉 Time Complexity Analysis of Insertion Sort

The speaker analyzes the time complexity of the insertion sort algorithm, explaining that it has a worst-case and average-case time complexity of O(n^2) due to the number of comparisons and shifts required. However, in the best case, when the array is already sorted, the time complexity is O(n) as no swaps are needed. The speaker emphasizes the importance of understanding the algorithm's performance in different scenarios.

👋 Conclusion and Call to Action

The speaker concludes the video by summarizing the key points discussed about the sorting algorithms and encourages viewers to like, comment, and subscribe for more content. The speaker also invites viewers to follow them on Instagram, Twitter, and LinkedIn, with links provided in the video description. The call to action includes a prompt for viewers to share their learnings using a specific hashtag.

Keywords

💡DSA Course

The 'DSA Course' refers to a Data Structures and Algorithms course, which is a fundamental educational program for anyone looking to strengthen their understanding of programming constructs and problem-solving techniques. In the video's context, it is described as India's most in-depth course, boasting 456 modules, suggesting a comprehensive curriculum that covers a wide range of topics within the subject.

💡Sorting Techniques

Sorting techniques are algorithms used to rearrange a list of items into a certain order, typically ascending or descending. The script discusses several sorting methods, emphasizing their importance in the context of data structures and algorithms, and mentions that they are often a subject of interest in placement interviews for software development roles.

💡Selection Sort

Selection sort is a specific sorting algorithm that works by repeatedly finding the minimum element from the unsorted part of the list and putting it at the beginning. The video script provides a detailed explanation of how selection sort operates, including the process of finding minimum elements and swapping them into the correct positions.

💡Insertion Sort

Insertion sort is another sorting algorithm that builds the final sorted array one item at a time. It is mentioned in the script as one of the algorithms that interviewees might be asked to explain or code during placement interviews. The script explains the process of insertion sort, where each new element is placed in its correct position in a sorted section of the array.

💡Bubble Sort

Bubble sort is depicted in the video as a simple sorting algorithm that works by repeatedly swapping adjacent elements if they are in the wrong order. The script describes the process of bubble sort, highlighting how it pushes the maximum element to the end of the array with each pass through the list.

💡Algorithm Implementation

The term 'algorithm implementation' refers to the process of writing code that performs a specific algorithm's task. The video script includes discussions on how to translate the conceptual understanding of sorting algorithms into actual code, using pseudocode and programming language examples.

💡Time Complexity

Time complexity is a measure of how long an algorithm takes in terms of the amount of input. The script analyzes the time complexity of the selection sort, bubble sort, and insertion sort algorithms, explaining that these algorithms have a time complexity of O(n^2) in their worst and average cases, but can be optimized for better performance.

💡Optimization

In the context of the video, optimization refers to the process of improving an algorithm to make it more efficient. The script suggests that bubble sort can be optimized by introducing a flag to detect if any swaps have occurred during a pass; if not, the algorithm can terminate early, as the array is already sorted.

💡Pseudocode

Pseudocode is an informal high-level description of an algorithm, which is used for planning out code before actual implementation. The script provides pseudocode for the sorting algorithms discussed, serving as a bridge between the conceptual understanding of the algorithms and their actual coding.

💡Runtime Error

A runtime error is an error that occurs during the execution of a program. The script cautions about the potential for runtime errors when implementing algorithms, specifically mentioning that attempting to access an array index that does not exist can cause such an error.

💡Career Counseling

Career counseling is a service that helps individuals to identify their skills, interests, and goals to make informed career decisions. The video script mentions a free one-on-one career counseling session as part of the offerings from a learning platform, suggesting that it can be beneficial for viewers to understand their career paths better.

Highlights

Introduction to the comprehensive Strivers A to Z DSA course, which is India's most in-depth course on Data Structures and Algorithms with 456 modules.

Emphasis on the importance of learning sorting techniques for placements, with potential interview questions on algorithms like insertion sort.

Promotion of LearnBase, an attic platform offering data science and full stack development programs with live online classes and industry-based Capstone projects certified by IBM.

Discussion on the benefits of LearnBase's one-on-one mentorship, doubt sessions, and project innovation labs across India.

Explanation of the selection sort algorithm, including its steps and the concept of selecting minimum elements and swapping them to the beginning of an array.

Illustration of the selection sort process with a step-by-step example using an array of numbers.

Introduction to the concept of pseudo code as a tool for understanding and implementing algorithms like selection sort.

Observation of the selection sort algorithm's time complexity, which is O(n^2) for the worst and average cases.

Introduction to the bubble sort algorithm, highlighting its method of pushing the maximum element to the end through adjacent swaps.

Description of the bubble sort process, including how it compares and potentially swaps adjacent elements to sort the array.

Analysis of bubble sort's time complexity, which is also O(n^2) in the worst and average cases, but can be optimized for best-case scenarios.

Optimization technique for bubble sort, which includes breaking out of the loop if no swaps are made, indicating the array is already sorted.

Introduction to the insertion sort algorithm, which builds the final sorted array one item at a time by comparing and inserting elements in their correct position.

Explanation of the insertion sort process, demonstrating how elements are shifted to their correct positions within the sorted portion of the array.

Writing of pseudo code for the insertion sort algorithm, outlining the steps for shifting elements and swapping them into place.

Analysis of insertion sort's time complexity, which is O(n^2) in the worst case but can be O(n) in the best case for an already sorted array.

Encouragement for viewers to engage with the content by liking, commenting, and subscribing for more learning opportunities.

Transcripts

hey everyone welcome back to the channel

I hope you guys are doing extremely well

so this will be another lecture from the

Strivers A to Z DSA course just in case

yeah for the first time here this course

is India's most yes most in-depth course

on DS algo why do I see that the course

has 456 modules

you can go to the market buy any of the

paid courses check out any of the free

courses none of those courses on DS algo

will have poor 56 problems or modules

solved so this is definitely by far one

of the most comprehensive course on DS

algo and this is the only thing that you

will be requiring if you are preparing

for placements so in the previous videos

we have covered the step one and now we

will be going to step two the step two

states you have to learn important

sorting techniques in order to start

your journey with Ds algo sorting is

something which you have to know even if

you're going for placements they might

ask you sorting algorithms and the

Sorting one which is Step 2.1 we have

three algorithms selection sort bubble

shot insertion sort so if you are

appearing for placements they might ask

you hey can you please tell me the code

for insertion sort and you have to tell

them right and sorting two will be based

on recursion so we'll be covering that

in the next lecture so without waiting

let's start with selections on so before

moving at in the video let me tell you

about learn base so learn by is an attic

platform that offers you data science

and full stack development programs

dedicated to professionals only so at

lonely you will be getting 100 live

online classes where you can interact

with the faculties directly and get your

doubt Result One Is to one one thing I

didn't like about learn by is you'll be

getting an opportunity to work on

industry-based Capstone projects which

will be certified by IBM so you're going

to get a global accreditation which will

be beneficial whenever you present that

project anywhere that's gonna be very

very helpful you also get in one is to

one personal mentorship and you also get

a one is to one daily doubt session

where you can actually get all your

doubts resolved also they have project

innovation Labs across the country in

Kolkata Pune Bangalore Hyderabad and a

lot of other places so you can go over

there and create your projects in the

offline mode as well so once you enroll

for any of the courses your three years

of subscription so you can have all the

learning modules and all the videos for

three years in this program you'll also

be getting 100 job assistance by their

dedicated placement cell and in the past

people have got hikes up to 250 percent

and they are partnered with more than

250 companies like ey Intel sap and a

lot others land-based Albanese have also

got placed in top companies like Amazon

T Cell Cap Gemini Etc so what are you

waiting for there's a link in the

description click it and get your free

one is to one career counseling session

the question what is selection sort does

the name recommends

selection

what do you select we select minimums

levels as the name recommends what do

you select we select minimums so as the

name recommends select minimums so what

you will do is you look at the entire

array and you will say who is the

minimum and it states 9 is the minimum

so you'll take that 9 and you'll place

it here

perfect

I place the 9 here and if this line is

the minimum and you're placing it at the

first place

where will 13 go 13 says okay no issues

I will go to your place because 9 has to

come at first and now I'll write the

remaining guys over here

that's how you do it so that is the step

one of the algorithm step one States get

the minimum from the entire

and you've got the minimum they place it

at the first whoever is at the first

goes to that minimum

select minimums and swap is what the

algorithm is all about so this is step

one remember this this is step one what

is step two let's see so the step two

states okay I know the first I know the

extreme smallest guy

is at the first

Nash we should select the next minimum

we know one thing if the minimum is over

here

this array is sorted which portion of

the array is not sorted that is this

let's find the minimum can I say in this

13 is the minimum so if 13 is the

minimum I know 9 will stay where nine is

13 is the minimum 13 will come at the

first place it will and if 13 comes here

where will 46 go 46 will go to 13. the

46 goes here and the rest remains as it

is

perfect tip to done let's do step three

so can I say

after two steps I got the first two

minimums and

this portion of the array sorted I can

now we are left with this portion

what to do get the next minimum what's

the next minimum 20

as usual 9 30 stays 20 comes in if 20 is

coming in here where will 24 Go 24 will

go to 20. so take it to there and 50 to

46 days

step three is completed let's do step

four

at step four can you say that

this portion of the array is sorted you

can which portion is not this one so in

this which is this minimum 24 place it 9

13 20 24 52 goes at its place 46 let's

do the step five

so can I say at step four this is sorted

and this is unsorted who is the minimum

46

so 9 13 20 24

sorry 46 will come here

and 52 will go here now

at step five if this is done

do you need to look like do you need to

sort one element one element will always

be solved so apparently can I say the

entire array is sorted at step five one

two three four five six six elements but

actually took five steps to sort the

entire array what I did was get the

minimum and swap it and swap it then

what I did was get the minimum and swap

it then what I did was get the minimum

and swap it so get the minimum and swap

is the algorithm now the question comes

okay we've understood the algorithm but

how do I implement this in code I'll be

writing the pseudo code so that you can

write it in C plus plus as well as in

Java as well as in Python so in order to

implement algorithms you have to have

something like observing power let's

start observing for the first

observation

in the entire array very very important

in the entire array we figured out the

minimum can I say we figured out the

minimum and whichever index the minimum

appeared whichever index the minimum

appeared I swapped it with the first guy

zero then

that's what I did that's why 13 is here

and 9 is here

so 0 to 5 is what I find next

I took this which is from index 1 to

index 5.

and I got the minimum which is 13. and I

swapped it with 46 thereby I got

I went from 1 to 5 and the swapping

happened

with one

and the minimum minimum minutes

next

in this

I got the minimum and the swapping

happened

from two so can I say

first time

trap happened

at index 0

and minimum index

next time swap happened at index one

and minimum index

and this minimum index is from the array

0 to n minus 1. this minimum index is

from the array 1 to n minus 1. next time

can I say swapping happened at index 2

because

till that 0 and 1 are sorted and minimum

Index this time is from 2 to n minus 1.

so can I generalize this and can I see

this will go like 0 1 2

till what

are you doing for the last guy are you

trapping the last head is just still

here you got 46 and you swapped can I

see you go till n minus 2 at index y n

minus 2 at index why because the last

index is n minus 1 in arrays so can I

say okay stopping is happening 0 1 2 and

I'll go till n minus 2. so thereby can I

write this as like this a pseudo code

okay

zero first time it will go 0 next time

one next time two next time three and it

goes on till n minus 2 and I plus plus

can I see this the first

and whenever I is 0

I find the minimum from 0 to n minus 1.

whenever is I is 1 I find it from 1 to n

minus 1 whenever I is 2

I find it from 2 to n minus 1 so can I

say I need to find the minimum guy

minimum so we know one thing I will be 0

1 2 and there has to be an internal Loop

why because you have to find the minimum

in this range minimum in this range

minimum in this range so the internal

Loop Can You observe something from 2 to

n minus 1 to write the internal Loop

what are you waiting for write the

internal Loop so can I say the internal

Loop will be from J equal to I

till J lesser than n

minus 1 because that is the last index

and Del J plus plus

and you need to find the minimum I know

the internal loop as well I know the

internal loop as well

now what is the next thing you have to

do

in this range

in this range you have to find the

minimum how do you do it very simple can

I say initially I will keep the mini

just imagine just imagine since your

array is from 0 to n minus 1 I will say

okay while we start let's consider this

guy to be these small

while we start for this let's consider

this guy to be meaningful while we start

for this let's consider this guy to be

minimum I will say hey my minimum

appears at index I itself at index I

whoever is the first guy let's assume is

the minimum I'm like okay

then I'm saying if array of J

is smaller than array of whatever

minimum index you are considering

what does this mean

when am I treating when am I treating

element by element I'm saying hey limit

are you smaller than what I considered

if you are can I say minimum okay you

are smaller so my minimum appears at the

jth index not at this guy I updated so

can I say once you have I treated can I

say once if I treated in the entire

thing you will get the minimum index

stored at the mini variable you will you

will write so

once this is completed what did we do

let's go back to the algo what did we do

so if you are iterating over here what

will happen let's see minimum initially

is

zeroth Index right the minimum is zero

what happened let's see in iteration

we are taking 13. it's like 13 lesser

than

30 because minimum is 0 what happens

array of 0 lesser than array of mini

because mini is zero it's not there so

it doesn't work next it goes here array

of 1 lesser than array of meaning

it's like 46 lesser than 13 no next time

24 less than 30 next time 52 less than

30 no next time 20 less than 30 no next

time 9 less than 13 so the mini gets

updated to five so you know at the fifth

index the mini is what did you do

you took the mini index and you took

those ith index and you swap and you

swap so you can just do a swap

you can just do a strap

wrap up whoever wherever is the mini

whatever is the value

with

the first guy because if you have to

take that mini and place it at the first

first we'll go to that mini index so

this app is also done

simple as that so by the way how do you

swap two numbers it's very simple

imagine uh I have array of I and I have

array of mini okay

these are the two numbers that I have to

swap imagine this is 15 and this is 12.

so what I'll do is I will take a

temporary variable that's another third

variable that I will take and I'll say

array of mini to go there so what will

array of mini uh what will temporary

have as of now 12 because area of mini

is 12 and that was put in to the

temporary now what I will do is I'll say

array of mini

can you replace yourself to array of I

so what will be the value of array of

mini reload B12 this value will go here

and this will become 15 right now I will

say array of I a array of I can you take

the value of array of mini but it is

replaced to 15. this is where since you

stored in the temporary that works and

it's a temporary can you get it the

temporary will get it and this will

become 12. tap lead cost so this is the

strap that you have to write

is the pseudocode of track function so

if I had to code it up imagine I have

given the N I take it as the input then

I take this array of N and then I go

across and I say this

so this is basically nothing but the

array input that I'm taking now I have

to write the selection sort so maybe I

can say selection I'll just pass it into

the function I'll pass it let's write

the selections on so void selection and

this will be sort and I'll say let's

take the array let's say the N so I'm

passing this

and I'm assuming this will do it and

post this what I'll do is for I and I

equal to 0 I lesser than n i plus plus

can I print the array values to C if

they are sorted or not okay let's see if

they are sorted or not

and what we can do is we can take the

same example that we took it has six

numbers 13 46 24

52 20 and 9. so took the same example

over here let's quickly write the code

so whatever pseudo code I did right that

I've converted into code now over here

and if I go across and run this

particular task you will see that this

particular array is sorted over here in

the output.txt

so you have understood the selection

sort algorithm in depth it's time to

analyze the time complexity of this

particular algorithm let's see can I see

for the first time when the loop gets

inside

this particular Loop runs for n times

exactly yes

next time when it gets in then this

actually runs so one lesson it's it runs

from one to n minus one so can I say it

runs for n minus 1. next time when it

gets in it runs for one lesson so it's

like n minus 2. next time when it gets

in transfer one lesson

n minus 3 so so on it kind of runs for

till last last that we run for this is

still here that's for two types so this

is kind of kind of if I just try to take

it to some near

formula stuff can I say it's something

like one

plus two plus three plus dot dot till n

which is nothing but the summation of

the first n natural numbers which is n

into n plus 1 by 2 can I say this I can

so if I can say this what is this

n Square

plus n by

2

can I say this is how it looks like and

if you remember the time complexity

Remember the Time complexity lecture we

did we ignore

smaller things because n by 2 in

comparison to n square is very small and

we ignore constant thereby I can say

that the time complexity is near about

bigo of N squared and this is the best

this is the worst and this is the

average time complexity for this

particular algorithm so we can see that

we have completed selection sort

successfully now it's time to understand

bubble shot

bubble chart so when we talk about

Bubble shot you have to remember it

pushes the maximum to the left and

opposite to the selections because

selection chart was taking the minimum

at the front if you remember

pushes the maximum to the last or does

it do it by adjacent traffic addition

swapping is the key over here

how does the algorithm work let's

understand

first two elements Compares are they in

the sorted order

13 and 46 they are because 13 is smaller

than 46. do not do anything go to the

next two are they the sorted order 46

before 24 no

trap it

okay

24

46 perfect let's go to the next

46 52 are they in the sorted order yeah

they are

why will you do anything

next 50 to 20 are they in the sorted

order no 20 should be before take 20

yeah take 50 to here

so 20 52

let's go to the next 50 to 19.

are they in the sorted no so take care

take care

so let's do nine and then 52. so can I

say

after

adjacent swaps

like this like this like this like this

like this one complete round of adjacent

swap checkings Do You observe something

the max 52 is at the last the max 52 is

at the last done so the max 52 is at the

last

what should be your next step

this portion of the array is kind of

sorted so I need to work on this perform

the same algorithm again let's do it 13

24 is it okay it is

246 is it okay yes 46 20

no no no no no trap 46 here take 20 here

let's swap it

20

46 let's go to the next

46 9 are they no no take

46 here

9 46 do you compare the last two there's

no point

because 52 is already in the socket

version

there's no need do you only do it till

here can I say no

in this particular array 46 was the

maximum and it's at the last so thereby

after two steps the last two are in the

correct orders so Step One is done step

two is done let's do the step three so

this is done this is done let's do the

step three step three means this portion

should be making sure that the maximum

is over here h2n 1324 are they they are

24 20. no no no stop it

20 24 next 24 9 no no stop it

done

in this 24 was the maximum it's at the

last

step three done

step four can I say step three means

last three elements done

this is left 1320 correct

29 no pops up

9 20. can I say for this 20 was the

largest and it said the last so thereby

post step four

this is done next step five

or step five

this

let's do a combination no

pap

913 for this portion 13 was the maximum

and it's at the last so for this portion

13 was the maximum and it's at the last

so thereby

this portion is sorted post step five

do you need to do for a single element

you do not thereby the entire array is

sorted if you see so EV uh so you have

understood the algorithm but now the key

factor comes in which is implementing

this to code

because that is where the key lies

let's try to do that

what are we doing observation is the key

0 1 2 3 4 5. we're going till

the first step we went everywhere and we

did

add disen company

the for the first time we kind of went

till 0 till n minus 1 and we did

adjacent facts if if it was not in the

order next time

we went like zero to

n minus 2 because the last was shot next

time we went from 0 to

n minus 3. next time we went to 0 to

n minus 4 and I said this is what we are

doing and the next time zero to n minus

5 and so on can I say I will just do

till 0 to 1 not L 0 to 0 because one

element will not matter

if you carefully observe

first Loop should run from here too next

Loop should run from here to here so

kinda

can I say I can probably keep the value

of I from n minus 1 till I can I keep I

can if I do it I equal to n minus 1 I

greater than 1 and I minus 1 this is

what I have

and internally I can always run the loop

from J equal to 0 till J lesser than I

and J plus plus

is it similar is it similar observe

0 to n minus 1

0 to n minus 1 for the first time next

time I is n minus 2 so 0 to 1 minus 2

next time I is n minus 3 so 0 to n minus

3 so

I have made sure the looping is done

what is the next thing that you are

doing the next thing is pretty simple

you take up two elements and you compare

you take up two elements you compare so

when you're looping from zero to n minus

1

it's kind of

this is J so you're comparing J with G

plus one and if they're not then you are

swapped right so you're kind of

comparing what are you comparing

if a of J is kind of greater than J plus

1 it's not in the correct order then

you're saying swap then you're saying

swap both of them

a key thing to notice over a very key

important thing

if you are going from here to here

that is wrong because for 52 it will

have no one to compare

do you actually go from here to here

because of 46

gets compared with J plus 1 which is

this

you actually Loop till here so what you

can do is

you can go over here and say instead of

going till

I exactly I will go till I minus 1

because if I go till here

if I go this will compare this will

compare this will compare this will

compare and 4652 will be compared

because I'm doing J Plus 1. I'm taking

the next index I don't need to go to

so you can just go till one lesson

and if you do not do that what will

happen for 52 it will look for the next

index which is not present and if you

are accessing an index which is not

present it will throw a runtime error

remember this if you are accessing an

index which is not present it will say

runtime I did not

children name

that's why it's very important to run

your Loops perfectly that's when you

strap and once you have done this

all steps at the end of the day the

array will be sorted so what we will do

is now we will write void bubble sort I

will do the same thing array

and n and instead of calling the

selection sort we will say okay so I

will just quickly go and write the same

pseudo code

if you remember this was kind of array

of G

if greater than array of J plus 1

when you swap

and in order to swap I've already taught

you how to

do that shopping you do this

and then you say okay

array of G plus 1 can use to array of J

and in Array of J can you take the value

of the rfj which is J plus 1 which is

stored in temporary once you have done

this entire thing the array will be

sorted I'll just go and erase this

output.txt and now go across and say to

run it and see if the bubble shot is

actually producing it it is it is

producing so if I have to analyze the

time complexity can you analyze the time

complexity for me for this particular

case it's quite similar to The Selection

sort first time the algorithm kind of

runs for n then for n minus 1 then for n

minus 2 then for n minus 3 so kind of

it's similar to selection sort where I

say it's n plus n minus 1 plus n minus 2

plus so on the last is 2.

it's something if you just add a 1 to it

it's similar to some of n natural

numbers again n into n plus 1 by 2 which

is n Square by 2 plus n by 2 smaller

constants

dissolved so the complexity is bigo of N

squared can it be optimized that's right

yes it can be it can be optimized this

is the worst complexity

this is the worst complexity and you can

also call it as the average complexity

in most of the cases this will become

most of it

but imagine if I give you an array which

is something like 2 3 5 15 and 20. if I

give you an array link it'll be like

Trevor this is sorted yeah it is sorted

so do you run the loop for n Square do

you go across every time every time

so

what is the algorithm

correct order no subs

correct order no sweats correct order no

swaps correct order no scrap array dude

if everything is in the correct order

and you're not performing a swap if

everything is in the correct order what

does it signify the array is in the

ascending order if everything is in the

correct order

added is in the ascending order so the

first

check

you did not find

a swap to be done because everything was

in the correct order so can I say if I

do not do any swaps but do not do any

swaps

that's when I stop I do not perform

so

it's kind of if no subs done

I don't need to go

if on the first check no swap is done I

don't need to go for this for this for

this for this let me stop so the loop at

the best case will run for bego of n if

we do some optimizations let's go and do

some optimization can I say

if I say indeed did swap

equal to 0 and over here if I just can

say did swap equal to 1 which means if

any

if at any moment a swap happens

then it's okay but if did swap at any

time is

there was no strap then I break out I

will not go if the array is sorted it

will just check for the first time and

it will break

post it

right this also runs

I'll prove you uh this one

I'll prove you this one so I'll give you

an example see

six five four three two one now what

I'll do is I will just go ahead and

print this how many times the array runs

okay and plus

and I'll just give it

and you can see how many times it runs

now terminal and I'll go to run task

this is a descending order and it runs

for five tips because the size is six it

runs so five but if I just change it to

something like one two three four five

six and I'll see how many times the

first for Loop will you see

uh delete one

just a minute

okay let's run it

run it

did you see something it never came to

this because it it did break over here

so it just ran for the first did not

Swap and broke so can I see

can I say the best time complexity will

be nothing but Big O of n so the time

complexity for the best of bubble shot

is we go often this might be asked in an

interview you have to critically tell

them the use case you have to explain

them in the dryer and tell them the

worst and the average might be n square

but if the array is sorted I will break

up and I will end up getting a linear

time complexity because the array is

already solved the bubble shot is done

now let's move on to the next one that

is the insertion sort algorithm so

talking about insertion sort you need to

remember one thing it always takes an

element

and places it in its correct position

takes an element

and places it in its correction let's

start yeah

the algorithm starts with looking at the

first element as an array and you will

say that if this much is the array the

element 14

in a size 1 array is at the correct

if I look at this much

and I ask you is 9 at the correct

position it'll be like no nine

apparently should have been here and 14

should have been here so this is what

you do

you go to the next element and you ask

on the left side where nine should

happen

and that is where you take

so you basically do it like this 9 40.

perfect

so

then you go ahead to this one and you

ask is 15 at the correct position or a

size 3 and you say

then you go ahead and say is 12 at the

correct position for a size four I say

no apparently 12 should have been here

14 should have been here 15 should have

been

so do you see a pattern it's like 14

will come here and 15 will come

everyone right shifts by one and 12 kind

of goes in its correct bottle

so what you can do is

you can take 12 and you can say Okay 12

15. 15 will come here 12 will go here

then you can say 12 14 so you can 12

year and you can pass 14 year you can go

to the left and slap tap till it can be

swapped till it can be served so if you

do like this 12 goes here it's like 12

and 15. then 12 14. so 12 goes here and

14 comes so go to the left till it can

be can 12 be swapped with 9 no because

that will distort the order but just go

still here simple

so what will happen

it'll be like 12 14

15 perfect next is six if you look at 6

where ideally should be 6 in this array

it should be here 9 should be here 12

should be here 14 should be here 15

should be here so can I do this can I

take this six here but I have to I have

to write shift every one by one how do

you do it you take six you take 15. and

you say Okay trap yourself what happens

is six goes here 15 goes here next you

take six fourteen fourteen comes here

and 6 goes here next you dig six twelve

twelve comes here 6 goes here next you

take six and nine six goes here nine

comes here

if I have to do it it's like 6 15 not in

the correct order let's wrap it 15 comes

here and 6 goes here fourteen six no six

comes here 14 goes 6 12 no 12 comes here

6 goes six nine no nine comes here 6

goes

perfect it's like 6 9 12 14 15. so if I

have to write it by raising it's like 6

9 12 14 15. perfect I just went on to

the left till it could have been drop

shot trap right next

eight in this particular array where

does it will go where will it go in this

particular array where will it go ask

yourself

the answer to that is 8 will go here

so if 8 has to go here 9 has to go here

12 has to go here 14 has to go here 15

has to go here so again what do you do 8

15 they say okay

it goes yeah 15 so left

can 814 can eight go till 14 yes 14

comes here 8 goes here can it go more

left yes it can eight goes here 12 goes

here can it go more left yes 9 goes yeah

it goes here is it in the correct order

yes how do you know it because when you

compared it with six it was not compared

and understood six eight nine twelve

fourteen fifteen

6 8 9 12 14 15 remember this

six eight nine twelve fourteen fifty

next

13 is the next guy that you are

comparing can I say 13. ideally over

here should have been here so do it

again

13 goes here 15 comes here 13 goes here

14 comes here can I do a 13 12 no

stop can I say post the last the array

is sorted why because you picked up

every element and you did put it into

its character

so how did it work I picked up one

first time I picked up the first guy

next time I picked up the second next

time the third next time the four next

and the fifth next time the sixth next

time the seven picked up every guy I'm

running from index 0 to n minus one

that's for sure

that's something for sure I'm running

from 0 to n minus 1.

and what am I doing

what am I doing

every guy I'm looking at the left are

you greater are you greater Swap and

till I can do it like for 13 I could do

till here till it is possible on the

left

so I'll be like okay

maybe JSI and I can keep while J greater

than 0 and I can say and and okay left J

minus 1. because the last that you can

compare is still here

is still here that's the last you can

compare so imagine this was not 13 I'll

give you an example

if this was like 14

15 and this is 7. so the seven would

have last gone here

or imagine this was five for an example

it's just five what would have happened

five would have gone

like

till here

and then five would have got compared

with six by standing here by standing

here would have compared it on the left

that's why you don't go till zero

because right before zero you do the

last comparison that's why and that's

why J minus one the last comparison if

it is greater than a of j e if it is

greater

that means can you please swap

so I'm not writing the swap you know how

to write you say a of J minus 1 and a of

G that's what you say

right and that's when it ends and you

can just do a j minus minus

oh yeah because what am I doing is I'm

taking the element and I'm saying left

left small left small okay and go left

again come back left small trap again

goal F small go the moment it's not

small stop and go to the next guy

White

now time to write insertion soft right

so avoid insertion sort int array

and int n so as usual we can just do

this as insertion Source okay and I'll

quickly write this book

[Music]

until here you know the pseudo code y g

greater than 0 y not greater than equal

to imagine if J goes equal to Z

is J minus 1 like when J is 0 J minus 1

will be minus

runtime that's all right so over here

you can go ahead and swap it and the

temporary equal to

array of a minus 1 and an array of J

minus 1 is array of J and then you can

go ahead and say array of J is equal to

Temporary and once you've swapped let's

go move left so J minus minus let's go

ahead and quickly run this and see if

this is sorting this particular thing

yeah it is sorting done simple if we

analyze the time complexity

what will be the time complexity imagine

for a

reversed array like something like five

four three two one what's up

for the first time five no swaps

next time it comes to four

and does this one it's like four five

next time it comes to three that's a

complete like three goes here then three

goes here next Summit so it's like three

four five two one next time it comes to

two two goes here two goes here two goes

here the two kind of goes here it's like

two three four five one next time it

comes to one one goes here one goes here

one goes here one goes here so it's like

one two three four five

it's kind of going

extreme left to the to the extreme left

this Loop for the first time

run for zero times when it was at five

when it was at point when it went to

four it stopped one place

next one it was a tree it swapped two

places next when it was at two it

trapped three pieces next it was when it

was at one it went left four places it's

kind of a game going into the similar

direction of summation of natural

numbers which is n cross at n plus one

by two makes it near above the time

complexity of n square if you remember

the time complexity class so I can say

the kind of worst case is n Square the

average case is also n square but what

about the best case imagine I give you

something like one two three four five

one two three four five and I go back to

the code and I go back to the code

so imagine I give you a completely

sorted

and I go back to the code and let's see

how many times this Loop runs

go to the terminal and try to print it

this Loop will not run a single day

because for one there's no one on the

left or two there's no one on the left

three is already in its correct position

4 is already in its correct position

five is already in its correct position

six is already so this

putting them into the correct position

never happens so apparently only this

Loop runs or check

it's a big off that's a big go offend

the best case for this is nothing but B

go of n complexity because

there is no straps that happen everyone

is at its correct order just go to

everyone that is what the time is taken

for in case of insertion sort so so with

this I can tick mark insertion sort and

it is completed uh the time is 5 29 yes

because I do take a lot of retakes while

recording because I want it to be

perfect like a lot of times I teach two

or three times so please uh please for

this effort if you understood everything

do consider hitting that like button and

to follow our ritual please do comment

understood if you understood everything

and if you have doubts you can

definitely put that into the comment

section I'll be replying to them and if

you're new to our Channel what are you

waiting for hit that subscribe button

and follow Strivers A to Z DSA course

share your learnings with the hashtag

and yes if you haven't followed me on

Instagram Twitter LinkedIn all the links

will be in the description make sure you

follow me with this I'll be wrapping up

this video let's read in some other

video till then

[Music]