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

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

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

## What's next?

If you're ready to start applying these concepts to some problems, check out our mock coding interview questions.

They mimic a real interview by offering hints when you're stuck or you're missing an optimization.

. . .