Selection Sort

Parisa Jalili Marandi
A free video tutorial from Parisa Jalili Marandi
Engineer/Researcher
3.7 instructor rating • 1 course • 6,927 students

Learn more from the full course

Data Structures and Algorithms (C# code in GitHub)

Search, Sort, Binary Heaps, Binary Trees, Nary Trees (paired with C# implementations in an open source GitHub repo)

06:33:35 of on-demand video • Updated August 2019

  • Sort algorithms (bubble, insertion, selection, quick, merge, heap, radix), Search algorithms (linear, hash-table, binary, ternary, jump, exponential, fibonacci), Binary Search Trees, AVL trees, Red-Black trees, B-Trees, B+Trees, Min Binary Heap, Max Binary Heap, Min-Max Binary Heap
English [Auto] In this lecture we are going to learn about selection sort selections or sorts at least of size n in N minus one iterations at each iteration ie. The algorithm looks at index i of the least it first fires the minimum value in the least from index I plus one to the end of the list. And if this minimum value is smaller than the value at index ie it swaps then the logic behind is that at each iteration the final location of one element is determined. This element is the minimum of all the remaining elements. Now we will use an example to learn this algorithm practically at first iteration which is iteration 0. We look at index 0 in which 100 is stored. Then we find the minimum in the remaining part of the least for this case. This value is 1 Next since a line is a smaller than 100 and in a sort of the least should definitely appear before 100. We swap these two values at this iteration. We have finalized the location of value 1 in the final sort at least at Iteration 1. We look at index 1 the value here is 2. Next we find the minimum of the least in the remaining part which is 3 and since 3 is not smaller than 2. We don't swap that at this iteration. The final index of 2 in the final sort of the least is determined to be 1 at iteration to relook at indexed to the value here is 3. Next we live to find the minimum value in the remaining part of the list. This value is 10 and since 10 is not smaller than entry similar to Iteration 1 We do not swap these two values and 3 remains at index 2. In other words the final index of 3 in the final sorted list will be 2. Also notice of the values in index 0 2 2 are already sorted 1 2 3 add iteration 3 we look at indexed 3 the value here is 100 Next we find the minimum value in the remaining part of the list. This minimum value is 10 since 10 is a smaller than 100. Next we swap these two values we have now finalized day next of 10 in the final list. Also notice how the values in index 0 to 23 are sorted 1 2 three and 10 at Iteration 4 we look at index for the value here is 56. Next we find the minimum in the remaining part of the list. This value is to evolve and since twelve is a smaller than 56 we swap them at iteration 5. You look at index 5 the value here is 78. Now we find the minimum in the remaining part of the list. This value is 15 and since 15 is a smaller than 78 we swapped out notice of the values in the leftmost part of the least up to and including in next five are sorted at iteration six we look at index six. The value here is two hundred and nine. Now we find the minimum in the remaining unsorted part of the list. This value is twenty one as twenty one is a smaller than two hundred nine and in a sort of the least it should appear before 209. We swap them at his residence seven relocating next seven. The value here is 46. Now we need to find the minimum in the remaining unsorted part of the list. This value is 50 1 and since 46 itself is a smaller than this minimum value we do not swap that and forty six is already finalized at index seven at iteration 8. We look at index 8 the value here is 209. Now we find the minimum at the remaining unsorted part of the list. This value is 51 and since 51 is a smaller than 209 we swap them at iteration 9. We look at indexed 9. The value here is one hundred and the minimum value in the remaining unsorted part of the list is 56 since 56 is a smaller than 100. We must swap that. Now we have extended distorted part of the list to be up to and including indexed 9 at iteration 10. We look at index down the value here is one. Next we find the minimum in the remaining part of the list. This value is 78 and is a smaller than 100. So we swapped them and our final iteration iteration eleven. We look at index eleven the value here is one hundred. The remaining part of the list only contains two hundred nine and since two hundred nine is bigger than 100. There is no need to swap these two as you see now our list is competently sorted at the end of this last iteration. Before proceeding to the next lecture take a few moments to make sure you have competently understood selection sort.