Selection Sort Algorithm

Quick reference

	Complexity
Worst case time
Best case time
Average case time
Space

Strengths:

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

Weaknesses:

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

Scanning through [8, 2, 3, 7, 9, 1, 4], the smallest element is 1.

... and move it to the front.

Swapping 1 with the first element (8), we have [1, 3, 2, 7, 9, 8, 4].

Now, the first item is sorted, and the rest of the list is unsorted.

In [1, 3, 2, 7, 9, 8, 4], [1] is sorted and [3, 2, 7, 9, 8, 4] is unsorted.

Repeat! We'll look through all the unsorted items, find the smallest one, and swap it with the first unsorted item.

[1] is sorted and [3, 2, 7, 9, 8, 4] is unsorted. Scanning through the unsorted items [3, 2, 7, 9, 8, 4], 2 is the smallest. Swapping 2 with the first unsorted item, 3, we have [1, 2] as the sorted portion and [3, 7, 9, 8, 4] as the unsorted portion.

We can do this for the next-smallest item

[1, 2] is sorted and [3, 7, 9, 8, 4] is unsorted. Scanning through the unsorted items [3, 7, 9, 8, 4], 3 is the smallest. It's already the first unsorted item, so we don't have to move it. [1, 2, 3] is the sorted portion and [7, 9, 8, 4] is the unsorted portion.

And so on:

[1, 2, 3] is sorted and [7, 9, 8, 4] is unsorted. Scanning through the unsorted items [7, 9, 8, 4], 4 is the smallest. Swapping 4 with the first unsorted item, 7, we have [1, 2, 3, 4] as the sorted portion and [9, 8, 7] as the unsorted portion.

[1, 2, 3, 4] is sorted and [9, 8, 7] is unsorted. Scanning through the unsorted items [9, 8, 7], 7 is the smallest. Swapping 7 with the first unsorted item, 9, we have [1, 2, 3, 4, 7] as the sorted portion and [8, 9] as the unsorted portion.

[1, 2, 3, 4, 7] is sorted and [8, 9] is unsorted. Scanning through the unsorted items [8, 9], 8 is the smallest. 8 is already the first unsorted item, so we don't need to move it. [1, 2, 3, 4, 7, 8] is the sorted portion and [9] is the unsorted portion.

Scanning through the unsorted items [9], 9 is the smallest (and only) item. It's already the first unsorted item, so we don't need to move it. The whole list is sorted: [1, 2, 3, 4, 7, 8, 9].

And, we're done!

The final sorted list: [1, 2, 3, 4, 7, 8, 9].

Implementation

Here's how we'd code it up:

def selection_sort(the_list): for i in xrange(len(the_list)): # Run through the unsorted elements in the input, finding # the smallest one. smallest_index = i for j in xrange(i + 1, len(the_list)): if the_list[j] < the_list[smallest_index]: smallest_index = j # Move the smallest element to the front of the unsorted portion # of the input (swapping with whatever's already there). the_list[i], the_list[smallest_index] = the_list[smallest_index], the_list[i]

Complexity

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 got

n + (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.

Interview coming up?

Get the free 7-day email crash course. You'll learn how to think algorithmically, so you can break down tricky coding interview questions.

No prior computer science training necessary—we'll get you up to speed quickly, skipping all the overly academic stuff.

No spam. One-click unsubscribe whenever.

You're in! Head over to your email inbox right now to read day one!