Write an algorithm for Selection sort trace its working for the given elements and also analyze its efficiency.

In this post we are discussing about Write an algorithm for Selection sort trace its working for the given elements and also analyze its efficiency.

function selectionSort (array) {
   for( var i=0; i< array.length ; i++ ){
       var min = i;
       for(var j=i+1 ; j< array.length ; j++){
           if( array[j] < array[min]){
              min=j;
            }
        }
       if(i!=min){
          var temp=array[i];
          array[i] = array[min];
          array[min] = temp;
       }
     }
    return array
}

Selection Sort Algorithm:

1. Start with the first element as the minimum (assuming it’s the minimum).
2. Compare the minimum element with the rest of the elements in the array.
3. If a smaller element is found, update the minimum to the new element.
4. After completing one pass through the array, swap the minimum element with the first element.
5. Repeat steps 1 to 4 for the remaining unsorted portion of the array until the entire array is sorted.

Step-by-Step Trace:

Given array: [89, 45, 68, 90, 29, 34, 17]

1. Initial array: [89, 45, 68, 90, 29, 34, 17]
2. First Pass:
   • Minimum is initially 89 (at index 0).
   • Compare with 45, 45 is smaller, so update minimum to 45.
   • Continue comparing with 68, 68 is not smaller.
   • Continue comparing with 90, 90 is not smaller.
   • Continue comparing with 29, 29 is smaller, so update minimum to 29.
   • Continue comparing with 34, 34 is not smaller.
   • Continue comparing with 17, 17 is smaller, so update minimum to 17.
   • Swap 89 with the minimum (17).
   • Updated array: [17, 45, 68, 90, 29, 34, 89]
3. Second Pass:
   • Minimum is initially 45 (at index 1).
   • Compare with 68, 68 is not smaller.
   • Continue comparing with 90, 90 is not smaller.
   • Continue comparing with 29, 29 is smaller, so update minimum to 29.
   • Continue comparing with 34, 34 is not smaller.
   • Swap 45 with the minimum (29).
   • Updated array: [17, 29, 68, 90, 45, 34, 89]
4. Third Pass:
   • Minimum is initially 68 (at index 2).
   • Continue comparing with 90, 90 is not smaller.
   • Swap 68 with the minimum (68).
   • Updated array: [17, 29, 68, 90, 45, 34, 89]
5. Fourth Pass:
   • Minimum is initially 90 (at index 3).
   • Swap 90 with the minimum (90).
   • Updated array: [17, 29, 68, 90, 45, 34, 89]
6. Fifth Pass:
   • Minimum is initially 90 (at index 4).
   • Swap 90 with the minimum (90).
   • Updated array: [17, 29, 68, 45, 90, 34, 89]
7. Sixth Pass:
   • Minimum is initially 90 (at index 5).
   • Swap 90 with the minimum (90).
   • Updated array: [17, 29, 68, 45, 34, 90, 89]
8. Seventh Pass:
   • Minimum is initially 90 (at index 6).
   • Swap 90 with the minimum (90).
   • Updated array: [17, 29, 68, 45, 34, 89, 90]

Efficiency Analysis:

• Time Complexity: Selection Sort has a worst-case, average-case, and best-case time complexity of O(n^2), where ‘n’ is the number of elements in the array. In this case, it required 7 passes for an array of 7 elements, resulting in a total of (7 * 6) / 2 = 21 comparisons and swaps.
• Space Complexity: The space complexity is O(1) because Selection Sort only requires a constant amount of extra memory for temporary variables (like the ‘minimum’ variable and loop counters).