sri ramanuja seva

In this post, we shall see:

• What is the Selection Sort algorithm? What is the basic idea behind it?
• Look at an example to see it in practice
• Analyze the running time of the algorithm

Selection Sort Algorithm

• Simple, intuitive algorithm
• Task: Sort an array of n elements in ascending (that is, non-descending) order.
• Basic idea:
  • Build the sorted array element-by-element, starting from the smallest element.
  • How to do that?
    • Step 1 (or Pass 1):
      • Select minimum element in the array.
      • This element should be at Position 1 (since this is the smallest element in the array).
      • Put it at Position 1 (that is, swap it with the element at Position 1).
      • So, now, the smallest element is at Position 1, which is what we want.
    • Step 2 (or Pass 2):
      • Consider the subarray from Position 2 to Position n. This is unsorted. Select the smallest element in this subarray.
      • This element should be at Position 2.
      • Swap it with the element at Position 2.
      • So, now, the 2 smallest elements of the array are at their correct positions (Positions 1 and 2). [And the remaining array, from Position 3 onwards, is still unsorted.]
    • Step 3:
      • Consider the unsorted portion of the array [Position 3 to Position n].
      • Select the smallest element in this subarray.
      • Swap it with the element at Position 3.
      • So, now, the 3 smallest elements of the array, are in their correct positions [Positions 1 through 3].
    • Keep continuing this way until all n elements of the array are in their correct positions in sorted order.
    • (n-1) passes will be required for this. At the end of (n-1) passes, the (n-1) smallest elements of the array would be in their correct position in sorted order, which automatically means that all n elements are sorted.

What is the running time (or time complexity) of Selection Sort?

• We make (n-1) passes in all. In each pass, we find the smallest element in the unsorted portion of the array, and bring it to the beginning of the unsorted portion.
• Finding the minimum element in an array of k elements takes (k-1) comparisons.
• Bringing that element to the front of the unsorted portion (swapping it with the element at the beginning of the unsorted subarry) takes O(1) time.
  
• Pass 1: (n-1) comparisons [to find min element] + O(1) [for swapping]
• Pass 2: (n-2) comparisons [to find min element] + O(1) [for swapping]
  
• Note that the size of the unsorted subarray reduces by 1 in each pass. Hence, the number of comparisons to find the min element in the unsorted subarray also keeps reducing.
  
• There are (n-1) passes in all.
  • Hence, total number of comparisons (over all passes) : (n-1) + (n-2) + … + 1, which is n(n-1)/2, which is O(n^2).
  • Time for swapping: O(1) in each pass. Hence, over all passes, it is O(n).
    
• Hence, combined time for comparisons and swaps: O(n^2) + O(n), which is O(n^2).
• That is, time complexity of Selection Sort algorithm is O(n^2).

---

In this post, we saw:

• A short explanation of the idea behind selection sort algorithm
• Example to see it in practice
• Analyzed the time complexity of our algorithm

---

For other posts on algorithms, you can see here: How to find minimum value in an array.