A space-efficient quadratic sorting algorithms. [Time: Θ(n²), Space: O(1)]

Idea

The idea of selection sort is to iteratively select the smallest (or largest) item from the unsorted n items and swap to the first position. It takes O(k) swaps and Θ(k²) scans and comparisons for an array of k items.

Implementation

Below is an implementation of selection sort in golang.

selection_sort.gosource

package sorting

func SelectionSort(arr []int) {
	for i := 0; i < len(arr)-1; i++ {
		iMin := i
		for j := i + 1; j < len(arr); j++ {
			if arr[j] < arr[iMin] {
				iMin = j
			}
		}
		if iMin != i {
			arr[i], arr[iMin] = arr[iMin], arr[i]
		}
	}
}

References:

1. https://en.wikipedia.org/wiki/Selection_sort
2. https://github.com/billjh/algo/tree/master/sorting

---

#algorithms #sorting #golang

Friday, Feb 17 2017