Selection sort

Music!

Let’s say that I’m sorting music

_images/8.png

I go from choosing the most played songs all the way down to the least. I start off with my original list and then append all of that (in ordered form) to this new list.

_images/9.png

As we do this over and over again, every single time, this overall process ends up taking O(n*n) or O(n*2) time

Selection sort is quite neat, but not really that fast. Quicksort is a lot fast, it only takes O(n log n) time!

Code

 1def findSmallest(arr):
 2    smallest = arr[0]
 3    smallest_index = 0
 4    for i in range(1, len(arr)):
 5         if arr[i] < smallest:
 6             smallest = arr[i]
 7             smallest_index = i
 8    return smallest_index
 9def selectionSort(arr):
10    newArr = []
11    for i in range(len(arr)):
12         smallest = findSmallest(arr)
13         newArr.append(arr.pop(smallest))
14    return newArr

>>> print selectionSort([5, 3, 6, 2, 10])
[2, 3, 5, 6, 10]