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

08 Dec 2023

본 문서에서는 Go 언어에서 제공되는 sort 패키지와 힙 정렬(HeapSort) 알고리즘에 대해 알아보겠습니다.

`sort` 패키지

Go 언어에서는 기본 라이브러리로 제공되는 sort 패키지를 사용하여 다양한 데이터 유형에 대한 정렬 기능을 제공합니다. 이 패키지는 일반적인 정렬 알고리즘 및 사용자 정의 정렬 함수를 제공하여 다양한 정렬 요구에 대응할 수 있습니다.

다음은 sort 패키지를 사용하여 슬라이스(Slice)를 정렬하는 간단한 예제 코드입니다.

package main

import (
    "fmt"
    "sort"
)

func main() {
    numbers := []int{4, 2, 5, 1, 3}
    sort.Ints(numbers)
    fmt.Println(numbers)
}

이 예제에서는 sort.Ints 함수를 사용하여 정수형 슬라이스를 오름차순으로 정렬하였습니다.

힙 정렬(HeapSort) 알고리즘

힙 정렬은 선택 정렬, 삽입 정렬, 합병 정렬과 같은 정렬 알고리즘 중 하나로, 평균 및 최악의 경우에 O(n log n)의 시간 복잡도를 갖습니다. 이 알고리즘은 힙 자료구조를 기반으로 구현되며, 요소들을 힙에 삽입하고 삭제함으로써 정렬을 수행합니다.

아래는 힙 정렬을 구현한 예제 코드입니다.

package main

import (
    "fmt"
)

func heapify(arr []int, n int, i int) {
    largest := i
    l := 2*i + 1
    r := 2*i + 2

    if l < n && arr[l] > arr[largest] {
        largest = l
    }

    if r < n && arr[r] > arr[largest] {
        largest = r
    }

    if largest != i {
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)
    }
}

func heapSort(arr []int) {
    n := len(arr)

    for i := n/2 - 1; i >= 0; i-- {
        heapify(arr, n, i)
    }

    for i := n-1; i > 0; i-- {
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)
    }
}

func main() {
    numbers := []int{4, 2, 5, 1, 3}
    heapSort(numbers)
    fmt.Println(numbers)
}

위의 예제 코드에서 heapify 함수는 주어진 배열을 힙 구조로 만들고, heapSort 함수는 힙 정렬을 실행합니다.

마무리

sort 패키지는 Go 언어에서 표준으로 제공되는 강력한 정렬 기능을 지원하며, 힙 정렬 알고리즘은 효율적으로 데이터를 정렬하는 데 사용될 수 있습니다. 이러한 도구와 알고리즘을 적절히 활용하여 데이터 정렬에 대한 요구사항을 충족시킬 수 있습니다.

sort 패키지

힙 정렬(HeapSort) 알고리즘

마무리

`sort` 패키지