Edited at

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

More than 1 year has passed since last update.

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

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

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


  • アルゴリズム


    • ピボットを選択

    • ピボットより小さい数を前方、大きい数を後方に移動

    • 二分割された各々のデータをソート



https://play.golang.org/p/VjUN303ejs

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)
}

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