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

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