Selection Sort - 선택 정렬

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

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

 

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

Selection sort - Wikipedia

 

Go로 구현한 코드입니다.

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)
}

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

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)
}

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

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)
}

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

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