アルゴリズムとデータ構造 - クイックソート

アルゴリズム データ構造 クイックソート

プログラミング

2020-02-01 16:02:47

概要

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

実装は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))
}

参考

About the author

Image

bmf san @bmf_san
A web developer in Japan.