[go] Sort 패키지와 BucketSort 알고리즘

08 Dec 2023

Go 언어의 sort 패키지는 데이터 슬라이스를 정렬하는데 유용한 함수들을 제공합니다. 여기서는 sort 패키지를 사용하여 BucketSort 알고리즘을 구현하는 방법에 대해 알아보겠습니다.

BucketSort 알고리즘

BucketSort 알고리즘은 일정한 범위의 입력 데이터를 각각의 버킷(구간)에 할당하고, 각 버킷을 정렬한 뒤 순서대로 합치는 정렬 알고리즘입니다. 전체적인 동작은 다음과 같습니다.

입력값을 일정한 기준에 따라 버킷(구간)에 분배합니다.
각 버킷 내부에서는 선택한 정렬 알고리즘을 사용하여 정렬합니다.
각 버킷의 정렬된 결과를 합쳐 최종 결과를 얻습니다.

Go에서의 BucketSort 구현

다음은 Go 언어에서 BucketSort 알고리즘을 구현하는 예제 코드입니다.

package main

import (
	"fmt"
	"sort"
)

func bucketSort(arr []float64, bucketSize int) []float64 {
	if len(arr) == 0 {
		return arr
	}

	minVal, maxVal := arr[0], arr[0]
	for _, val := range arr {
		if val < minVal {
			minVal = val
		} else if val > maxVal {
			maxVal = val
		}
	}

	bucketCount := int((maxVal-minVal)/float64(bucketSize)) + 1
	buckets := make([][]float64, bucketCount)

	for _, val := range arr {
		bucketIndex := int((val - minVal) / float64(bucketSize))
		buckets[bucketIndex] = append(buckets[bucketIndex], val)
	}

	var result []float64
	for i := 0; i < bucketCount; i++ {
		sort.Float64s(buckets[i])
		result = append(result, buckets[i]...)
	}

	return result
}

func main() {
	arr := []float64{0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51}
	bucketSize := 5
	sortedArr := bucketSort(arr, bucketSize)
	fmt.Println("Sorted array:", sortedArr)
}

위 코드에서 bucketSort 함수는 주어진 슬라이스를 버킷 정렬하는 함수입니다. Go 언어의 sort 패키지를 사용하여 각 버킷을 정렬하고, 정렬된 결과를 합쳐 최종적인 정렬된 슬라이스를 반환합니다.

BucketSort 알고리즘을 구현하는 방법과 Go 언어에서의 실제 구현 예제를 통해 BucketSort 알고리즘의 동작과 Go 언어의 sort 패키지 활용에 대해 알아보았습니다.

참고 문헌:

https://en.wikipedia.org/wiki/Bucket_sort
https://golang.org/pkg/sort/