Goでのアルゴリズムクイックリファレンス第2版(クイックソート)

Goに慣れるためとアルゴリズムの復習の為に週1ぐらいで更新していきます。アルゴリズムクイックリファレンス 第2版を読んで各種アルゴリズムをGoで実装して行きます。

前回: Goでのアルゴリズムクイックリファレンス第2版(4.3 ヒープソート)

今回はクイックソートです。

• アルゴリズム
  • ピボットを選択
  • ピボットより小さい数を前方、大きい数を後方に移動
  • 二分割された各々のデータをソート

package main

import (
    "fmt"
    "math/rand"
)

func quickSort(a *[]int, left int, right int) {
    var pivot int

    if right > left {
        pivot = partition(a, left, right)
        quickSort(a, left, pivot-1)
        quickSort(a, pivot+1, right)
    }
}

func partition(a *[]int, left int, right int) int {
    tmp_left := left
    pivotItem := (*a)[left]
    for left < right {
        for (*a)[left] <= pivotItem {
            left++
        }
        for (*a)[right] > pivotItem {
            right--
        }
        if left < right {
            (*a)[right], (*a)[left] = (*a)[left], (*a)[right]
        }
    }
    (*a)[tmp_left] = (*a)[right]
    (*a)[right] = pivotItem
    return right
}

func main() {
    var ary []int
    size := 30
    for i := 0; i < size; i++ {
        ary = append(ary, rand.Intn(size-1))
    }
    fmt.Println(ary)
    quickSort(&ary, 0, len(ary)-1)
    fmt.Println(ary)
}

次回はバケツソートの予定です。