sorting-algorithms/selection_sort.go at main · aq1l/sorting-algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
package main

import "time"

func SelectionSort(arr []int, metric *Metrics) time.Duration {
	n := len(arr)
	start := time.Now()

	for i := 0; i < n-1; i++ {
		minI := i
		for j := i + 1; j < n; j++ {
			metric.Comparison++
			if arr[j] < arr[minI] {
				minI = j
			}
		}

		metric.Swaps++
		arr[i], arr[minI] = arr[minI], arr[i]
	}

	return time.Since(start)
}

func SelectionSortOptimized(arr []int, metric *Metrics) time.Duration {
	n := len(arr)
	start := time.Now()
	isSorted := true

	for i := 0; i < n-1; i++ {
		minI := i
		for j := i + 1; j < n; j++ {
			metric.Comparison++
			if arr[j] < arr[minI] {
				minI = j
				isSorted = false
			}
		}

		metric.Comparison++
		if minI != i {
			metric.Swaps++
			arr[i], arr[minI] = arr[minI], arr[i]
		}

		metric.Comparison++
		if isSorted {
			break
		}
	}

	return time.Since(start)
}