우크라이나어 하는 개발자

정렬은 데이터를 특정한 조건에 따라 일정한 순서가 되도록 다시 배열하는 일이다.

Golang의 sort.Sort는 비교 정렬이자 불안정 정렬이다. (sort.Stable 안정 정렬을 지원한다.) 개발자는 두 데이터를 비교해 어느 데이터가 먼저 와야 하는지 알려주는 부분을 작성하면 된다. sort.Sort를 이용하기 위해서는 Len, Less, Swap 함수가 구조체 슬라이스에 정의돼야 한다. 물론 int, string, float64 슬라이스는 sort.Ints, sort.Strings, sort.Float64s 함수로 정렬한다.

golang.org/pkg/sort/#Interface

type Interface interface {
    // Len is the number of elements in the collection.
    Len() int

    // Less reports whether the element with index i
    // must sort before the element with index j.
    //
    // If both Less(i, j) and Less(j, i) are false,
    // then the elements at index i and j are considered equal.
    // Sort may place equal elements in any order in the final result,
    // while Stable preserves the original input order of equal elements.
    //
    // Less must describe a transitive ordering:
    //  - if both Less(i, j) and Less(j, k) are true, then Less(i, k) must be true as well.
    //  - if both Less(i, j) and Less(j, k) are false, then Less(i, k) must be false as well.
    //
    // Note that floating-point comparison (the < operator on float32 or float64 values)
    // is not a transitive ordering when not-a-number (NaN) values are involved.
    // See Float64Slice.Less for a correct implementation for floating-point values.
    Less(i, j int) bool

    // Swap swaps the elements with indexes i and j.
    Swap(i, j int)
}

int string float64 슬라이스 정렬

play.golang.org/p/VuZVzEyoFk

package main

import (
	"fmt"
	"sort"
)

func main() {
	integers := []int{10, 5, 8, 7, 1, 3, 2, 4, 6, 9}
	names := []string{"James", "Bob", "Jinsu", "Wanhee", "Amy", "Suzy"}
	floats := []float64{2.36, 1.45, 8.12, 1.12, 6.03, 9.99, 10.12, 2.03, 4.53, 7.16}

	sort.Ints(integers)
	sort.Strings(names)
	sort.Float64s(floats)

	fmt.Println(integers)
	fmt.Println(names)
	fmt.Println(floats)

	// Output:
	// [1 2 3 4 5 6 7 8 9 10]
	// [Amy Bob James Jinsu Suzy Wanhee]
	// [1.12 1.45 2.03 2.36 4.53 6.03 7.16 8.12 9.99 10.12]
}

구조체 정렬

play.golang.org/p/SzYWBPgrTIS

package main

import (
	"fmt"
	"sort"
)

type Book struct {
	name  string
	price int
}

type Bookshelf []Book

func (bs Bookshelf) Len() int {
	return len(bs)
}
func (bs Bookshelf) Swap(i, j int) {
	bs[i], bs[j] = bs[j], bs[i]
}
func (bs Bookshelf) Less(i, j int) bool {
	return bs[i].price < bs[j].price
}

func main() {
	books := []Book{
		{name: "Discovery Go", price: 18000},
		{name: "Database System", price: 35000},
		{name: "Docker and Kubernetes", price: 29000},
		{name: "Object Oriented Programming", price: 17000}}
	sort.Sort(Bookshelf(books))
	fmt.Println(books)

	// Output:
	// [{Object Oriented Programming 17000} {Discovery Go 18000} {Docker and Kubernetes 29000} {Database System 35000}]
	// Less 가 bs[i].price > bs[j].price 이면 내림차순 정렬
}

 문자열 정렬

오름차순 정렬이고 두 단어가 "word", "WORD"인 경우 대문자로 이루어진 단어가 뒤로 온다. 

play.golang.org/p/dbvWOrqusw6

package main

import (
	"fmt"
	"sort"
	"strings"
)

type Word string

type Dictionary []Word

func (d Dictionary) Len() int {
	return len(d)
}
func (d Dictionary) Swap(i, j int) {
	d[i], d[j] = d[j], d[i]
}
func (d Dictionary) Less(i, j int) bool {
	return strings.ToLower(string(d[i])) < strings.ToLower(string(d[j])) ||
		(strings.ToLower(string(d[i])) == strings.ToLower(string(d[j])) && d[i] > d[j])
}

func main() {
	words := []Word{"book", "BOOK", "cup", "account", "tree", "ukraine", "Skill", "silver", "Sell"}
	sort.Sort(Dictionary(words))
	fmt.Println(words)

	// Output:
	// [account book BOOK cup Sell silver Skill tree ukraine]
}

 sort 인터페이스 함수 정의가 귀찮다면 sort.Slice

play.golang.org/p/0Va3DDo83Tf

package main

import (
	"fmt"
	"sort"
)

func main() {
	nums := []int{5, 6, 9, 8, 7, 4, 5, 63, 1, 4, 8, 6, 5, 5, 89}

	lessFunc := func(i, j int) bool {
		return nums[i] < nums[j]
	}
	sort.Slice(nums, lessFunc)

	fmt.Println(nums)
	// Output:
	// [1 4 4 5 5 5 5 6 6 7 8 8 9 63 89]
}

func sort.Slice(slice interface{}, less func(i int, j int) bool)

sort.Slice 첫 번째 인수에 슬라이스, 두 번째 인수에 이전에 정의한 Less 함수를 넣으면 된다.

sort.Sort 특징

Golang에서 사용되는 정렬은 퀵 정렬을 사용합니다. 최악의 복잡도를 피하기 위해 피벗 3개 중 가운데를 선택하는 중위법을 사용합니다. 퀵 정렬의 깊이가 너무 깊어지면 힙 정렬을 사용하고 퀵 정렬 도중 데이터가 7개 이하가 되면 삽입 정렬을 사용합니다. 삽입 정렬은 데이터가 적으면 효과적입니다.

go.googlesource.com/go/+/go1.16/src/sort/sort.go

func quickSort(data Interface, a, b, maxDepth int) {
	for b-a > 12 { // Use ShellSort for slices <= 12 elements
		if maxDepth == 0 {
			heapSort(data, a, b)
			return
		}
		maxDepth--
		mlo, mhi := doPivot(data, a, b)
		// Avoiding recursion on the larger subproblem guarantees
		// a stack depth of at most lg(b-a).
		if mlo-a < b-mhi {
			quickSort(data, a, mlo, maxDepth)
			a = mhi // i.e., quickSort(data, mhi, b)
		} else {
			quickSort(data, mhi, b, maxDepth)
			b = mlo // i.e., quickSort(data, a, mlo)
		}
	}
	if b-a > 1 {
		// Do ShellSort pass with gap 6
		// It could be written in this simplified form cause b-a <= 12
		for i := a + 6; i < b; i++ {
			if data.Less(i, i-6) {
				data.Swap(i, i-6)
			}
		}
		insertionSort(data, a, b)
	}
}

Reference

- sort.Sort 소스코드

go.googlesource.com/go/+/go1.16/src/sort/sort.go

- Discovery Go, 엄재현 지음 2016

www.kyobobook.co.kr/product/detailViewKor.laf?ejkGb=KOR&mallGb=KOR&barcode=9788968482687&orderClick=LAG&Kc=