Golang でクイックソートを書いてみる

Golang の勉強がてら、どれくらい楽に書けるかという確認を兼ねてクイックソートを書いてみた。 ナイーブな実装なので実用性はないけど。

package main

import (
    "fmt"
    "time"
    "math/rand"
)

func sort(values []int) (ret []int) {
    // 要素数が 1 以下の配列はそれ以上細分化してソートする必要がない
    if len(values) < 2 {
        return values
    }

    // 配列の先頭をピボット (基準値) に選ぶ
    pivot := values[0]

    // ピボットを基準にして値の大小で配列をふたつに分割する
    left := []int{}
    right := []int{}
    for _, v := range values[1:] {
        if v > pivot {
            right = append(right, v)
        } else {
            left = append(left, v)
        }
    }

    // 分割した配列をそれぞれ再帰的にソートする
    left = sort(left)
    right = sort(right)

    /*
    left(小さい) + pivot(基準値) + right(大きい) の順番で配列を組み立てる
    ここが実際のソート処理
    */
    ret = append(left, pivot)
    ret = append(ret, right...)

    return
}

func main() {
    // UNIX 時間をシードにして乱数生成器を用意する
    t := time.Now().Unix()
    s := rand.NewSource(t)
    r := rand.New(s)

    // ランダムな値の入った配列を作る
    N := 10
    values := make([]int, N)
    for i := 0; i < N; i++ {
        values[i] = r.Intn(N)
    }

    // ソートして結果を出力する
    sortedValues := sort(values)
    fmt.Println(sortedValues)
}

実行結果は次の通り。

$ go run quicksort.go
[0 0 1 3 3 4 5 8 8 9]

スクリプト言語ほどではないにせよ、それなりに書きやすいかな。

おまけ

Python 版

#!/usr/bin/env python
# -*- coding: utf-8 -*-


def sort(values):
    if len(values) < 2:
        return values

    pivot = values[0]

    left = []
    right = []
    for i in values[1:]:
        if i < pivot:
            left.append(i)
        else:
            right.append(i)

    left = sort(left)
    right = sort(right)

    return left + [pivot] + right


def main():
    import random
    N = 10
    values = [random.randint(0, N) for _ in range(N)]
    sorted_list = sort(values)
    print(sorted_list)


if __name__ == '__main__':
    main()