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.
array of array of
random decreasing
data data values
(causes avg case (causes worst case
insert times insert times)
+----------------+---------------------------+---------------------------------+
| | | |
| N inserts | fast heap constr | O(NlogN) heap constr |
| to construct | because on average | slowest |
| the heap | an insert is O(1) | longest heap construction |
| | so heap constr is O(N) | time |
+----------------+---------------------------+---------------------------------+
| | | |
| Magic build | O(N) heap constr | O(N) heap constr |
| to construct | | |
| the heap | | |
| | | |
+----------------+---------------------------+---------------------------------+