|Worst case time|
|Best case time|
|Average case time|
- Intuitive. Ever packed a suitcase, putting in large items before smaller ones? That's selection sort!
- Space efficient. Selection sort only requires a constant amount of additional space ().
- Slow. Selection sort takes time, even if the input is already sorted. That's too slow to be used on super-big data sets.
How It Works
Selection sort works by selecting the smallest element from an unsorted list and moving it to the front.
Here's how it'd work on this list:
We'll scan through all the items (from left to right) to find the smallest one ...
... and move it to the front.
Now, the first item is sorted, and the rest of the list is unsorted.
Repeat! We'll look through all the unsorted items, find the smallest one, and swap it with the first unsorted item.
We can do this for the next-smallest item
And so on:
And, we're done!
Here's how we'd code it up:
Selection sort takes time and space.
The main time cost comes from scanning through the list to find the next smallest item. We do that n times. The first time, we'll be looking at n elements, the next time it'll be n - 1 elements, and so on, until we're left with just one element.
Adding all those up, we've gotn + (n - 1) + (n - 2) + \ldots + 2 + 1
That's the triangular series, which is .
Even if the input is already sorted, selection sort still involves scanning all the unsorted elements repeatedly to find the next-smallest. So, unlike insertion sort, it'll stay , even in the best case.
Selection sort doesn't rely on any extra lists, so it's space.