Sorting - Part 1 | Selection Sort, Bubble Sort, Insertion Sort | Strivers A2Z DSA Course
Summary
TLDRThis 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
📚 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.
🔍 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.
💡 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.
📈 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.
🔄 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.
🔄 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.
🚀 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.
🔍 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.
📉 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.
Mindmap
Keywords
💡DSA Course
💡Sorting Techniques
💡Selection Sort
💡Insertion Sort
💡Bubble Sort
💡Algorithm Implementation
💡Time Complexity
💡Optimization
💡Pseudocode
💡Runtime Error
💡Career Counseling
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]
5.0 / 5 (0 votes)