관리 메뉴

don't stop believing

Selection Sort - 선택 정렬 본문

Golang/Basic

Selection Sort - 선택 정렬

Tongchun 2019. 4. 19. 18:04

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

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

 

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

 

Selection sort - Wikipedia

In computer science, selection sort is a sorting algorithm, specifically an in-place comparison sort. It has O(n2) time complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted

en.wikipedia.org

 

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

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

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

 

'Golang > Basic' 카테고리의 다른 글

Gnome Sort - 난쟁이 정렬  (0) 2019.04.25
Cocktail Sort - 칵테일 정렬  (0) 2019.04.22
Merge Sort - 병합 정렬  (0) 2019.04.20
Selection Sort - 선택 정렬  (0) 2019.04.19
Bubble Sort - 버블 정렬  (0) 2019.04.18
Golang << 와 >> 연산자 (그리고 메모리 사이즈 계산)  (0) 2019.02.28
0 Comments
댓글쓰기 폼