11/11/2020
selection sort
Selection sort is not stable
let's sort these array elements:
10 8 8' 2 5 element
-- -- -- -- --
0 1 2 3 4 index
Note that 8 comes before the 8' ... so if selection sort is stable,
when the array is sorted, 8 will still be before 8'
Steps:
1) find smallest item in array to go into index 0 ... this is 2 at index 3
swap [0] and [3], leaves this array
2 8 8' 10 5 element
-- -- -- -- --
0 1 2 3 4 index
2) find smallest item in array from index 1 up... this is 5 at index 4
swap [1] and [4], leaves this array
2 5 8' 10 8 element
-- -- -- -- --
0 1 2 3 4 index
3) find smallest item in array from index 2 up... find that 8' is smallest
meaning nothing remaining is larger
so no swap, leaves this unchanged array
2 5 8' 10 8 element
-- -- -- -- --
0 1 2 3 4 index
4) find smallest item in array from index 3 up... this is 8 at index 4
swap [3] and [4], leaves this array
2 5 8' 8 10 element
-- -- -- -- --
0 1 2 3 4 index
And finally note that now 8' is first and 8 is second,
so selection sort is unstable.