How SelectionSort works

SelectionSort is a sorting method, which works in-place, here no new array is created for the sorting. SelectionSort works in bestcase, averagecase and worstcase, with an overhead of $O(n^2)$.

SelectionSort always searches for the minimum from its current position. When the minimum is found, the current element is swapped with the minimum. After the swap, SelectionSort moves one element to the right. We thus have an array that is divided into sorted and unsorted. This procedure is now performed on the whole array.

A small example, illustrates how SelectionSort works.

The implementation here is similar to InsertionSort, again I implemented the process in Python.

#!/usr/bin/env python
import random

class SelectionSort(object):

	def __init__(self):
		None

	def sort(self, array):
		for outer_round in range(0, len(array)):
			pos_smallest = outer_round
			for inner_round in range(outer_round + 1, len(array)):
				if(array[inner_round] <= array[pos_smallest]):
					pos_smallest = inner_round

			x = array[outer_round]
			array[outer_round] = array[pos_smallest]
			array[pos_smallest] = x
		return array

if __name__ == "__main__":
	array = []
	for i in range(0, 100000):
		array.append(random.randint(0, 100))


	ss = SelectionSort()
	print "unsorted" , array
	print "sorted", ss.sort(array)

We consider the two For loops. The outer loop wanders over our array to be sorted. The inner one looks for our minimum, starting from our current position outer_round +1.

Why current position + 1 ? Because we don't want to compare our current element with itself. If our minimum is found, after the search the current element, is simply swapped with the minimum. So the minimum is at the right position in the array.

Small funfact as with InsertionSort: SelectionSort = InsertionSort.