sorting Selection


In computer science, a selection sort is a sorting algorithm, specifically an in-place comparison sort. It has O(n2) time complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity, and it has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited.

The below image shows how the selection sort works-

enter image description here

Below pseudo code helps in creating a program(in any language) or understanding selection sort.

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

Advantages :

  • it’s too simple to understand
  • it performs well on a small list
  • no additional temporary storage is required beyond what is needed to hold the original list

Image Reference: RMIT University