golang のクイックソートの仕組みを教えてください。

2年 ago
陽, 向宇
1 minute

Go言語でクイックソートを実装する方法は次のとおりです。

package main

import "fmt"

func main() {
    arr := []int{5, 9, 3, 1, 7, 6}

    quickSort(arr, 0, len(arr)-1)

    fmt.Println(arr)
}

func quickSort(arr []int, low, high int) {
    if low < high {
        pivot := partition(arr, low, high)

        quickSort(arr, low, pivot-1)
        quickSort(arr, pivot+1, high)
    }
}

func partition(arr []int, low, high int) int {
    pivot := arr[high]
    i := low - 1

    for j := low; j < high; j++ {
        if arr[j] < pivot {
            i++
            arr[i], arr[j] = arr[j], arr[i]
        }
    }

    arr[i+1], arr[high] = arr[high], arr[i+1]

    return i + 1
}

単純なクイックソートの実装です。まず、配列を再帰的にソートする quickSort 関数を定義します。quickSort 関数では、まず partition 関数で基準値（ここでは配列の最後の要素を選択）を見つけ、次に基準値より小さい要素を基準値の左に、基準値より大きい要素を基準値の右に配置します。その後、再帰的に quickSort 関数を呼び出して、左右の 2 つのサブ配列をソートします。最終的に、配列は昇順にソートされます。

基準値で配列を2つに分割するパーティション関数。iとjの2つのポインタを使い、配列の最初と最後を指す。配列を走査し、現在の要素が基準値より小さい場合、iポインタが指す要素と入れ替えて、iポインタを後ろに移動する。走査が終わったら、基準値をi+1ポインタが指す要素と入れ替え、基準値を正しい位置に置き、基準値のインデックスを返す。

上記のコードを実行すると、[1, 3, 5, 6, 7, 9]という結果が表示され、配列が昇順に並べ替えられていることを示しています。

bannerAds