3.15 Selection Sort

1. Selection Sort

During traversal, find the largest value and put it in the appropriate position after the traversal. Compared with bubble sort, it reduces the number of swaps.

2. Characteristics

• Stability: unstable
• In-place sorting
• Time complexity: O(n²)
• Space complexity: O(1)

3. Process

4. Implementation

//O(N²)
func SelectionSort(data []model.Comparable) {
	// data[0...i) is sorted; data[i...n) is unsorted
	// After each outer loop, data[i] is in its sorted position
	for i := 0; i < len(data); i++ {
		minIndex := i
		// Find the minimum value in arr[i...n)
		for j := i + 1; j < len(data); j++ {
			if data[j].CompareTo(data[minIndex]) < 0 {
				minIndex = j
			}
		}
		util.Swap(data, minIndex, i)
	}
}

4.1. Test

func TestSelectionSort(t *testing.T) {
	e1 := model.NewElement(1)
	e2 := model.NewElement(2)
	e3 := model.NewElement(3)
	data := []model.Comparable{e2, e1, e3}
	fmt.Println(data)

	SelectionSort(data)
	fmt.Println(data)
}

5. References

• Sorting Algorithm Stability - Baidu Baike