**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:**

- Start with the first element as the minimum (assuming it’s the minimum).
- Compare the minimum element with the rest of the elements in the array.
- If a smaller element is found, update the minimum to the new element.
- After completing one pass through the array, swap the minimum element with the first element.
- 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]

- Initial array: [89, 45, 68, 90, 29, 34, 17]
- 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]

- 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]

- 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]

- Fourth Pass:
- Minimum is initially 90 (at index 3).
- Swap 90 with the minimum (90).
- Updated array: [17, 29, 68, 90, 45, 34, 89]

- Fifth Pass:
- Minimum is initially 90 (at index 4).
- Swap 90 with the minimum (90).
- Updated array: [17, 29, 68, 45, 90, 34, 89]

- Sixth Pass:
- Minimum is initially 90 (at index 5).
- Swap 90 with the minimum (90).
- Updated array: [17, 29, 68, 45, 34, 90, 89]

- 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).