0:03 hello friends in this video
0:05 we are going to learn about selection sort
0:06 sort
0:09 there are many sorting algorithms like
0:10 quick sort
0:12 tim sort or merge sort which are
0:15 actually more popular and efficient
0:17 selection sort is not suitable for large
0:18 data sets
0:22 as it has average performance selection
0:23 sort is an
0:26 in-place comparison based algorithm it
0:28 divides the list into two parts
0:31 the sorted part on the left an unsorted
0:33 part on the right
0:35 it works by repeatedly finding the
0:37 minimum element from the
0:39 unsorted part and putting it in the
0:41 sorted part
0:43 let's see what it means by taking an
0:44 example list of
0:47 unsorted numbers the list is divided
0:48 into two parts
0:51 sorted part on the left and the unsorted
0:53 part on the right
0:55 initially there are no elements in the
0:56 sorted side
1:00 and whole list is in the unsorted side
1:02 now i am also listing the position of
1:04 each of the element
1:08 since in arrays the index starts from 0
1:10 i am giving the position number starting
1:11 from 0.
1:13 if you are not familiar with array indexes
1:14 indexes
1:17 my suggestion is to view our video on
1:18 arrays first
1:21 coming back to selection sort the way it works
1:22 works
1:25 is that it first assumes that the first
1:27 number of unsorted array
1:30 is the minimum number we are using min
1:32 variable to showcase
1:36 it and first time it has index 0.
1:38 then it starts comparing it with every
1:41 element in the array in sequence
1:44 if it finds a number which is less than it
1:44 it
1:48 like 6 it updates min to this new index number
1:49 number
1:51 it then starts comparing following
1:54 numbers with this new min number
1:57 it finds 2 which is lower than 6
2:00 then it again updates the min index
2:01 number to 4
2:04 and starts comparing the next number
2:05 with 2.
2:07 when it finishes comparing all the
2:09 elements in the list
2:12 it then swaps the first number with the
2:13 lowest number 2
2:16 which it found in unsorted array at
2:18 index 4.
2:21 this completes the first pass now the
2:23 sorted array has one number
2:26 and unsorted has remaining five
2:29 now in the next pass it starts by
2:30 assuming the first
2:33 element in unsorted array is the lowest
2:36 it then starts from the next number and
2:38 goes down the list one by one
2:41 comparing till it finds a lower number
2:44 here six is the lowest so at the end of
2:45 the pass
2:48 six will move into the sorted array now
2:51 it will go through the next pass
2:54 there are now two elements in sorted and
2:57 four in unsorted it will again start by
3:00 assuming the first member of unsorted list
3:00 list
3:04 is the lowest so element at index 2
3:07 which is 23 is set as lowest
3:10 then it will compare it with the next element
3:10 element
3:13 8 is smaller so it will now note down
3:15 the min value as
3:18 3 and compare the remaining list element with
3:18 with
3:22 8. once it reaches the end of the list
3:25 min value 8 will be swapped with 23
3:28 and it will be moved to sorted array now
3:30 it will go through the next pass
3:33 where again element at index 3 which is
3:35 23 is the lowest
3:39 23 is compared with 11. since
3:42 11 is lower it will set min to its
3:46 index next it will compare with 14.
3:50 since 11 is lower min will remain 4
3:54 at the end of the pass the min value 11
3:58 is swapped with 23. now in the next pass
4:01 23 is compared with 14. 14
4:03 is smaller so min is set to that position
4:05 position
4:07 since we have also reached end of the list
4:08 list
4:11 we swap the two numbers we do not need
4:14 to run any pass for the last number
4:17 as it is already sorted there are a few
4:19 key points to note from here
4:22 first is that the list is divided into
4:23 two parts
4:27 sorted and unsorted in every pass
4:30 only one lowest number of unsorted list
4:33 is added to the sorted list also in
4:35 every pass
4:38 the first unsorted number is swapped
4:40 with the lowest number in the unsorted list
4:41 list
4:44 another important thing to note is that
4:45 in a pass
4:48 when a lower number is found it just
4:48 notes the
4:52 index in min and continues comparing it
4:55 till it reaches the end of the list so a
4:56 swap is made
4:59 only after it reaches the end of the list
5:00 list
5:03 now you would have noted that in every pass
5:03 pass
5:06 the unsorted list gets shorter by 1
5:10 means if unsorted list is n then it requires
5:11 requires
5:14 n minus 1 comparisons to be made till it
5:14 reaches the
5:18 end of the list also you must have noted
5:21 that for 6 numbers it required us to do
5:22 5 passes
5:25 as the last number automatically gets
5:27 into the sorted position
5:30 so if we have n numbers we will need to do
5:30 do
5:34 n minus 1 passes to get a sorted array
5:36 now let's see how we will write the
5:39 pseudo code for it first we will take an
5:43 array of size n in variable named list
5:46 when we look at our example we saw that
5:47 if you have n
5:50 elements then you will run n minus 1
5:51 passes on it
5:54 so this will be our first loop to run
5:55 the passes
5:59 for i from 0 to n minus 1
6:02 now for each pass you need to set the
6:03 min to the index
6:06 of the first unsorted list then you have
6:07 to run
6:10 a comparison from next element till end
6:11 of the array
6:14 this will be our nested loop where we
6:16 will run our loop from
6:19 j is equal to i plus 1 to j less than
6:22 n now we will compare each element
6:26 with the min element if the element is
6:27 less than the min
6:30 element then we will just copy the index
6:30 of this
6:34 element in min if not then we move to
6:36 comparing the next element till the end
6:38 of the list
6:41 now once the pass is over that's when we
6:42 do the swap
6:44 of the first element of unsorted array
6:45 with the min
6:48 element we found in the unsorted array
6:52 once done we again start the next pass
6:55 by incrementing i by one so effectively
6:57 starting the unsorted array
7:01 with next element in the array and so on
7:03 now let's convert the sudo code to java code
7:04 code
7:06 i am assuming we are getting the array
7:08 as a function parameter
7:10 but you can write the main and take it
7:12 from user as well
7:14 first we will write the outer loop which
7:16 will run our pass
7:19 from 0 to n minus 1 then we will assign
7:20 the min to the first
7:24 index of unsorted array then the loop
7:25 will run
7:27 from the next element of unsorted array till
7:28 till
7:31 end so j will run from i plus 1 to
7:34 n now we will compare the next element
7:35 with the min
7:38 value if the value is smaller
7:41 we just set the min to that index value
7:44 we continue the search till end of the array
7:45 array
7:48 once we have completed the pass then we
7:49 will write the swap routine
7:52 which will swap the first value of
7:53 unsorted array
7:56 with the value at min index we use a
7:58 temp variable here
8:01 to do the swap once the pass is complete
8:04 i is incremented and sets the start of
8:06 unsorted array
8:09 to next element again the first element
8:10 of unsorted array
8:14 is set as min and internal loop runs
8:17 to find the next lowest element this
8:18 process continues
8:22 till the whole array is sorted
8:24 i hope you were able to understand
8:25 selection sort
8:27 if you still have any doubts you can
8:29 reach out to us
8:32 at simplycoding.in thank you
Chrome Extension