Selection Sort - 선택 정렬

제자리 정렬이라고도 합니다.

최소값을 배열의 가장 앞자리와 교체합니다.

 

https://en.wikipedia.org/wiki/Selection_sort

Selection sort - Wikipedia

 

Go로 구현한 코드입니다.

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
package main
import "fmt"
func main() {
    arr := [10]int{9, 1, 2, 8, 6, 7, 5, 3, 0, 4}
    fmt.Println("Initial array is:", arr)
    fmt.Println("")
    var min int
    for i := 0; i < len(arr)-1; i++ {
        min = i
        for j := i + 1; j < len(arr); j++ {
            if arr[min] > arr[j] {
                min = j
            }
        }
        
        arr[i], arr[min] = arr[min], arr[i]
    }
    fmt.Println("Sorted array:    ", arr)
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

각 코드에 대한 설명을 주석으로 달았습니다.

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
package main
import "fmt"
func main() {
    // 길이가 10인 int 형식의 배열을 만들고 0부터 9까지의 숫자를 정렬하지 않고 담습니다.
    arr := [10]int{9, 1, 2, 8, 6, 7, 5, 3, 0, 4}
    fmt.Println("Initial array is:", arr)
    fmt.Println("")
    // 정렬에 사용할 min과 tmp 변수를 선언합니다.
    var min int
    // 배열의 길이만큼 loop를 진행합니다. 이때 i는 min 변수에 대입해 배열의 자리(index)를 의미하게 됩니다.
    for i := 0; i < len(arr)-1; i++ {
        min = i
        // 두 번째 loop는 min으로 지정한 배열의 자리 이후부터 마자막까지 loop를 진행합니다.
        // min(index)의 값이 0이라면 j는 1부터 9까지가 됩니다.
        // min(index)의 값이 1이라면 j는 2부터 9까지가 됩니다.
        // min(index)의 값이 2라면 j는 3부터 9까지가 됩니다.
        for j := i + 1; j < len(arr); j++ {
            // min의 값과 min 이후부터 마지막 자리까지의 값을 비교합니다.
            // arr[min] > arr[j]일 경우 오름차순 정렬이 됩니다.
            // arr[min] < arr[j]일 경우 내림차순 정렬이 됩니다.
            if arr[min] > arr[j] {
                // 만약 min이후부터 마지막 자리 중 min 값보다 작은 값이 있다면 해당 자릿값을 min에 대입합니다.
                // 가장 작은값의 자리번호(index)를 min에 대입합니다.
                min = j
            }
        }
        // i번 자릿값과 가장 작은 자릿값 min을 서로 교체합니다.
        arr[i], arr[min] = arr[min], arr[i]
    }
    fmt.Println("Sorted array:    ", arr)
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

selection sort로 검색해 찾은 go 코드도 비슷하네요.

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
package main
import (
    "fmt"
)
func selectionSort(array []int) {
    for i := 0; i < len(array)-1; i++ {
        min := i
        for j := i + 1; j < len(array); j++ {
            if array[j] < array[min] {
                min = j
            }
        }
        array[i], array[min] = array[min], array[i]
    }
}
func main() {
    array := []int{5, 8, 4, 1, 7, 2, 3, 6}
    fmt.Println("Unsorted array: ", array)
    selectionSort(array)
    fmt.Println("Sorted array: ", array)
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

버블 정렬보다는 조금 더 빠르다고 합니다.

코드도 버블 정렬보다는 간결해 보입니다.