概要

アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。

実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。

クイックソート

• データ列の中から適当なデータ（ピボット）を選択し、ピボットより小さいデータを前方、大きいデータを後方に移動させる。
• 分割されたデータをそれぞれソートする
• 分割統治法の一種

計算時間

• 最悪計算時間
  • O(n²)
• 最良計算時間、平均計算時間
  • O(n log n)

実装

package main

import (
	"fmt"
	"math/rand"
)

func quickSort(n []int) []int {
	if len(n) <= 1 {
		return n
	}

	pivot := n[rand.Intn(len(n))]

	low := make([]int, 0, len(n))
	high := make([]int, 0, len(n))
	middle := make([]int, 0, len(n))

	for _, i := range n {
		switch {
		case i < pivot:
			low = append(low, i)
		case i == pivot:
			middle = append(middle, i)
		case i > pivot:
			high = append(high, i)
		}
	}

	low = quickSort(low)
	high = quickSort(high)

	low = append(low, middle...)
	low = append(low, high...)

	return low
}

func main() {
	n := []int{2, 5, 7, 1, 3, 9}
	fmt.Println(quickSort(n))
}

• cf. アルゴリズムとデータ構造 - ヒープ

参考

• アルゴリズムとデータ構造