YouTube Transcript:
Learn Selection Sort
Skip watching entire videos - get the full transcript, search for keywords, and copy with one click.
Share:
Video Transcript
Available languages:
View:
hello friends in this video
we are going to learn about selection sort
sort
there are many sorting algorithms like
quick sort
tim sort or merge sort which are
actually more popular and efficient
selection sort is not suitable for large
data sets
as it has average performance selection
sort is an
in-place comparison based algorithm it
divides the list into two parts
the sorted part on the left an unsorted
part on the right
it works by repeatedly finding the
minimum element from the
unsorted part and putting it in the
sorted part
let's see what it means by taking an
example list of
unsorted numbers the list is divided
into two parts
sorted part on the left and the unsorted
part on the right
initially there are no elements in the
sorted side
and whole list is in the unsorted side
now i am also listing the position of
each of the element
since in arrays the index starts from 0
i am giving the position number starting
from 0.
if you are not familiar with array indexes
indexes
my suggestion is to view our video on
arrays first
coming back to selection sort the way it works
works
is that it first assumes that the first
number of unsorted array
is the minimum number we are using min
variable to showcase
it and first time it has index 0.
then it starts comparing it with every
element in the array in sequence
if it finds a number which is less than it
it
like 6 it updates min to this new index number
number
it then starts comparing following
numbers with this new min number
it finds 2 which is lower than 6
then it again updates the min index
number to 4
and starts comparing the next number
with 2.
when it finishes comparing all the
elements in the list
it then swaps the first number with the
lowest number 2
which it found in unsorted array at
index 4.
this completes the first pass now the
sorted array has one number
and unsorted has remaining five
now in the next pass it starts by
assuming the first
element in unsorted array is the lowest
it then starts from the next number and
goes down the list one by one
comparing till it finds a lower number
here six is the lowest so at the end of
the pass
six will move into the sorted array now
it will go through the next pass
there are now two elements in sorted and
four in unsorted it will again start by
assuming the first member of unsorted list
list
is the lowest so element at index 2
which is 23 is set as lowest
then it will compare it with the next element
element
8 is smaller so it will now note down
the min value as
3 and compare the remaining list element with
with
8. once it reaches the end of the list
min value 8 will be swapped with 23
and it will be moved to sorted array now
it will go through the next pass
where again element at index 3 which is
23 is the lowest
23 is compared with 11. since
11 is lower it will set min to its
index next it will compare with 14.
since 11 is lower min will remain 4
at the end of the pass the min value 11
is swapped with 23. now in the next pass
23 is compared with 14. 14
is smaller so min is set to that position
position
since we have also reached end of the list
list
we swap the two numbers we do not need
to run any pass for the last number
as it is already sorted there are a few
key points to note from here
first is that the list is divided into
two parts
sorted and unsorted in every pass
only one lowest number of unsorted list
is added to the sorted list also in
every pass
the first unsorted number is swapped
with the lowest number in the unsorted list
list
another important thing to note is that
in a pass
when a lower number is found it just
notes the
index in min and continues comparing it
till it reaches the end of the list so a
swap is made
only after it reaches the end of the list
list
now you would have noted that in every pass
pass
the unsorted list gets shorter by 1
means if unsorted list is n then it requires
requires
n minus 1 comparisons to be made till it
reaches the
end of the list also you must have noted
that for 6 numbers it required us to do
5 passes
as the last number automatically gets
into the sorted position
so if we have n numbers we will need to do
do
n minus 1 passes to get a sorted array
now let's see how we will write the
pseudo code for it first we will take an
array of size n in variable named list
when we look at our example we saw that
if you have n
elements then you will run n minus 1
passes on it
so this will be our first loop to run
the passes
for i from 0 to n minus 1
now for each pass you need to set the
min to the index
of the first unsorted list then you have
to run
a comparison from next element till end
of the array
this will be our nested loop where we
will run our loop from
j is equal to i plus 1 to j less than
n now we will compare each element
with the min element if the element is
less than the min
element then we will just copy the index
of this
element in min if not then we move to
comparing the next element till the end
of the list
now once the pass is over that's when we
do the swap
of the first element of unsorted array
with the min
element we found in the unsorted array
once done we again start the next pass
by incrementing i by one so effectively
starting the unsorted array
with next element in the array and so on
now let's convert the sudo code to java code
code
i am assuming we are getting the array
as a function parameter
but you can write the main and take it
from user as well
first we will write the outer loop which
will run our pass
from 0 to n minus 1 then we will assign
the min to the first
index of unsorted array then the loop
will run
from the next element of unsorted array till
till
end so j will run from i plus 1 to
n now we will compare the next element
with the min
value if the value is smaller
we just set the min to that index value
we continue the search till end of the array
array
once we have completed the pass then we
will write the swap routine
which will swap the first value of
unsorted array
with the value at min index we use a
temp variable here
to do the swap once the pass is complete
i is incremented and sets the start of
unsorted array
to next element again the first element
of unsorted array
is set as min and internal loop runs
to find the next lowest element this
process continues
till the whole array is sorted
i hope you were able to understand
selection sort
if you still have any doubts you can
reach out to us
at simplycoding.in thank you
Click on any text or timestamp to jump to that moment in the video
Share:
Most transcripts ready in under 5 seconds
One-Click Copy125+ LanguagesSearch ContentJump to Timestamps
Paste YouTube URL
Enter any YouTube video link to get the full transcript
Transcript Extraction Form
Most transcripts ready in under 5 seconds
Get Our Chrome Extension
Get transcripts instantly without leaving YouTube. Install our Chrome extension for one-click access to any video's transcript directly on the watch page.
Works with YouTube, Coursera, Udemy and more educational platforms
Get Instant Transcripts: Just Edit the Domain in Your Address Bar!
YouTube
←
→
↻
https://www.youtube.com/watch?v=UF8uR6Z6KLc
YoutubeToText
←
→
↻
https://youtubetotext.net/watch?v=UF8uR6Z6KLc