Data Structures-Selection sort

Selection sort

Selection sort is an in-place sorting algorithm. It divides the list into two parts, putting the sorted part on the left side, and the unsorted part on the right side.

How does selection sort work?

1. For example, we can take the following array: 14, 33, 27, 35, 10, 19, 42, 44.
2. We compare the first element with the entire list, and find the element smaller than the first element. In this case, it will be 10.
3. After iteration, the smallest element comes first. The list will be: 10, 33, 27, 35, 14, 19, 42, 44.
4. Then it is compared with the second element, i.e. 33. 14 is the second smallest number. Therefore, the list is: 10, 14, 27, 35, 33, 19, 42, 44.
5. The process continues till all the elements are sorted. In the end, the list will be: 10, 14, 19, 27, 33, 35, 42, 44.

Algorithm

Pseudocode:

procedure selection sort 
   list: array of items
   n: size of list

   for i = 1 to n - 1
   /* set current element as minimum*/
      min = i    
  
      /* check the element to be minimum */

      for j = i+1 to n 
         if list[j] < list[min] then
            min = j;
         end if
      end for

      /* swap the minimum element with the current element*/
      if indexMin != i  then
         swap list[min] and list[i]
      end if
   end for
 
end procedure

Reference

Selection sort