15th April, 2017

Selection sort in Python

A selection sort algorithm in Python 3.5.

This is a simple script that sorts lists (of arbitrary lengths) of unsorted numbers from lowest to highest. https://en.wikipedia.org/wiki/Selection_sort.

Selection sort is a very simple sorting algorithm that works by iterating over all elements in an unsorted list and finding the smallest value for each iteration - the smallest value is then pushed to the beginning of the list. This process continues until all elements have been selected and moved to their correct position at the beginning of the list. Sorting elements in this way means all elements are sorted in order - the smallest elements are sorted first, and largest elements are sorted last.

The worst-case performance and complexity of the selection sort algorithm can be described by the following Big O notation equation: O(n^2).
Selection sort is generally much faster compared to bubble sort and performs far less comparison. Selection sort works well with small to medium sized lists and is able to maintain good performance.

Speed tests

I have tested this selection sort algorithm to time how long it takes to sort 100, 1000, and 10,000 unsorted random numbers between 0 and 1000.
Each test was run 3 times (to find the average) using a 2016 MacBook air with a 1.6GHz CPU and 4GB of RAM.
All results are recorded in milliseconds, and averages are rounded to 1 decimal place.

100 elements:
    test 1: 1ms
    test 2: 1ms
    test 3: 2ms
    average: 1.3ms
1,000 elements:
    test 1: 95ms
    test 2: 81ms
    test 3: 106ms
    average: 94ms
10,000 elements:
    test 1: 9,875ms
    test 2: 10,049ms
    test 3: 9,969ms
    average: 9,964.3ms

Source code

def sort(list):
    # initialize offset as 0
    offset = 0
    # while the offset is less than the length of he unsorted list
    while offset < len(list):
        # assume the smallest element in the current list is at position 0
        smallest = 0
        # for every element in the list starting at offset n
        for pos, value in enumerate(list[offset:]):
            # if the current element is less than the current smallest element
            if value < list[offset + smallest]:
                # the new smallest element is at the current position of value
                smallest = pos
        # swap values
        list[offset], list[offset + smallest] = list[offset + smallest], list[offset]
        # increment the offset to ignore sorted elements at the beginning of the list
        offset +=1
    # return sorted list
    return list

print(sort([9, 8, 7, 6, 5, 4, 3, 2, 1, 0]))

Example usage

print(sort([9, 8, 7, 6, 5, 4, 3, 2, 1, 0]))
# Returns [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Thank you for reading.


Leave a comment

Invalid or missing field(s).
Comment sent successfully, please wait for it to be approved.

This post has no comments