# W2203 Selection Sort

Within these castle walls be forged Mavens of Computer Science ...
— Merlin, The Coder

## Algorithm

Selection Sort starts off by selecting the first element in the array, comparing that element with other remaining elements in the array, and if a smaller element is found, both elements are swapped, bringing the smallest element at index 0. This same process is repeated with the element in the following indices.

• Iterate over the array
• Find the smallest element in the array, assigning that element to "i".
• Swap "i" with the first index in the array, assigning that index to "j".
• Find the next smallest element in the array, assigning that element to "i".
• Swap "i" with the "j + 1" index in the array, adding one to "j".
• Repeat until the array is sorted.

### Swap

You can use the same swap function as in bubble sort and selection sort because you only need to be able to swap two elements at a time.

### Performance Considerations

Given an array with 8 elements, this algorithm would have to run 8 times on the first swap, 7 times on the second swap, since that is how many unsorted elements are remaining, 6 times on the third swap, and so on, until the array is sorted. This array would run a total of 36 times.

Similar to Bubble Sort, Selection Sort would not be a suitable choice to process large amounts of data due to its long run time. Selection Sort can be good at checking if arrays are already sorted. It can also be used if memory is limited since Selection Sort does not wait to swap elements .

### Example

Here is an example with an array of 5 elements:

```Array: [20, 12, 10, 5, 2] | Initial

// The algorithm first finds the smallest element: 2. Since 2 < 20, both would be swapped, bringing 2 to the first index.

Array: [2, 12, 10, 5, 20] | Total loops ran before 1st swap: 5
|
// The algorithm finds the next smallest element: 5. Since 5 < 12, both would be swapped, bringing 5 to the second index.

Array: [2, 5, 10, 12, 20] | Total loops ran before 2nd swap: 9
|
// The algorithm finds the next smallest element: 10. Since 10 !< 10, no swap would occur.

Array: [2, 5, 10, 12, 20] | Total loops ran before 3rd swap: 12
|
// The algorithm finds the next smallest element: 12. Since 12 !< 12, no swap would occur.

Array: [2, 5, 10, 12, 20] | Total loops ran before 4rd swap: 14
|
// The algorithm finds the next smallest element: 20. Since 20 !< 20, no swap would occur.
// The array is now fully sorted
```

## Quiz

1 Selection Sort places unsorted elements at its place in each iteration.

 True False

2 Selection sort is practical for most problems.

 True False

3 Selection sort is most practical if:

 Elements are in nearly sorted order Elements are already sorted in reverse order Doubles (floating point types) are used rather than integers The set of elements is very large

4 Selection Sort repeatedly looks for and swaps the highest remaining number.

 False True

5 An element that must move toward the beginning of the list can move faster than one step per pass.

 True False

6 Elements move toward the beginning of the list very quickly.

 True False

7 Consider the list: 695, 999, -375, -488, 888, 877
After the first swap, the list will be:

 695, 999, -375, -488, 888, 877 -488, -375, 888, 695, 999, 877 -488, -375, 999, 695, 888, 877 -488, 999, -375, 695, 888, 877

8 Consider the list: 695, 999, -375, -488, 888, 877
After the second swap, the list will be:

 -488, 999, -375, 695, 888, 877 -488, 999, -375, 695, 999, 877 -488, -375, 888, 695, 999, 877 -488, -375, 999, 695, 888, 877

9 Consider the list: 695, 999, -375, -488, 888, 877
After the third swap, the list will be:

 -488, -375, 695, 999, 888, 877 -488, 999, -375, 695, 999, 877 -488, -375, 999, 695, 888, 877 -488, 999, -375, 695, 888, 877

10 Consider the list: 695, 999, -375, -488, 888, 877
After the first pass, the list will be:

 -488, 999, -375, 695, 888, 877 -488, -375, 888, 695, 999, 877 695, 999, -375, -488, 888, 877 -488, -375, 999, 695, 888, 877

11 Consider the list: 695, 999, -375, -488, 888, 877
After the second pass, the list will be:

 -488, -375, 999, 695, 888, 877 -488, 999, -375, 695, 999, 877 -488, 999, -375, 695, 888, 877 -488, -375, 888, 695, 999, 877

12 Consider the list: 695, 999, -375, -488, 888, 877
How many passes are required before the algorithm terminates?

 Five Three Two Four

## References

Selection Sort (Wikipedia)