クイックソート

• 平均して$O(n\log n)$なソートアルゴリズム
• が，しかし最悪の場合で$O(n^2)$になりうるという欠点もある
• 考え方は「困難は分割しろ」
• ある値$v$を適当に選んで，$v$より小さい値は左側に，$v$より大きい値は右側に集めることで配列を分割していく
• 分割して得られるそれぞれの配列にもう一度同じことをする
• と，いつの間にか全体が整列している
• 「それぞれの要素の位置を決め込むこと」でソートするのではなくて，「大雑把に二分していくこと」を繰り返すことで整列させる
• 「問題をいくつかの部分問題に分解してそれぞれを解き，その結果を組み合わせて全体の解を得る」方法を分割統治法という
• 分割された部分配列は整列されている必要はないということに注意
• 配列の要素を左から舐めながら，「左右の境目をpで保持しながら，pivotの値より小さいやつを見つけたら右側の部分列に入れる」を繰り返すことで配列を分割していく

func QuickSort(target *[]int, left, right int) []int {
    if left < right {
        pivotIdx := rand.Int() % (right - left) + left
        pivot := (*target)[pivotIdx]
        (*target)[pivotIdx] = (*target)[left]
        partitionIdx := left
        for i := left + 1; i <= right; i++ {
            if (*target)[i] < pivot {
                partitionIdx += 1
                (*target)[partitionIdx], (*target)[i] = (*target)[i], (*target)[partitionIdx]
            }
        }
        (*target)[left] = (*target)[partitionIdx]
        (*target)[partitionIdx] = pivot
        QuickSort(target, left, partitionIdx-1)
        QuickSort(target, partitionIdx+1, right)
    }
    return *target
}

• pivotの値より小さいやつは左部分列に，大きいやつは右部分列にいて欲しいので，配列の両側から眺めていって，いるべき場所が違うやつを発見し次第交換することで，分割をもうちょっと賢く

func QuickSort(target *[]int, left, right int) []int {
    if left < right {
        pivotIdx := rand.Int() % (right - left) + left
        pivot := (*target)[pivotIdx]
        log.Printf("Pivot: %d\n", pivot)
        i := left
        j := right
        for i < j {
            for (*target)[i] < pivot {
                i += 1
            }
            for pivot < (*target)[j] {
                j -= 1
            }
            if i <= j {
                (*target)[i], (*target)[j] = (*target)[j], (*target)[i]
                log.Printf("Swap: [%d] <--> [%d] ==> %v\n", i, j, *target)
                i += 1
                j -= 1
            }
        }
        QuickSort(target, left, j)
        QuickSort(target, i, right)
    }
    return *target
}

クイックソートを高速化させるための工夫

基準値の選び方

• 分割した後の左右の部分列が大体同じくらいの長さになるような基準値を選ぶとき，最も高速
• 要するに与えられた配列に格納されている値の中央値が欲しい
• 実用上よく用いられるのは，「3個サンプリングしてそれらの中央値」をピボットとして用いる方法

挿入法の併用

• 整列したい配列の幅が閾値を下回るまでクイックソートでやって，ある程度短くなったら挿入法でソートすることでちょっと高速になる

再帰呼び出しの除去

• クイックソートでは「分割しておしまい」を繰り返すので，整列していない区間を自前のスタックに積んでいくことで記録しておいて再帰を解消することができる

高速化したクイックソート

func QuickSort(target *[]int) []int {
    *target = append([]int{-1}, *target...)
    stack := make([]record, 100)
    limit := 10
    sp := 1
    stack[1] = record{left:1, right: len(*target)-1}
    for sp > 0 {
        left := stack[sp].left
        right := stack[sp].right
        sp -= 1
        for right - left >= limit {
            w1 := (*target)[left]
            w2 := (*target)[right]
            center := (left + right)/2
            w3 := (*target)[center]
            (*target)[center] = (*target)[left + 1]
            if w1 > w2 {
                w1, w2 = w2, w1
            }
            if w2 > w3 {
                w2, w3 = w3, w2
                if w1 > w2 {
                    w1, w2 = w2, w1
                }
            }
            (*target)[left] = w1
            (*target)[right] = w3
            (*target)[left + 1] = w2
            pivot := w2
            i := left + 1
            j := right
            for i < j {
                for (*target)[i] < pivot {
                    i += 1
                }
                for (*target)[j] > pivot {
                    j -= 1
                }
                if i < j {
                    (*target)[i], (*target)[j] = (*target)[j], (*target)[i]
                }
            }
            (*target)[left + 1], (*target)[j] = (*target)[j], (*target)[left + 1]
            sp += 1
            if j - left <= right - j {
                stack[sp].left = j + 1
                stack[sp].right = right
                right = j - 1
            } else {
                stack[sp].left = left
                stack[sp].right = j - 1
                left = j + 1
            }
        }
    }
    for i := 1; i < len(*target); i++ {
        w := (*target)[i]
        (*target)[0] = w
        j := i - 1
        for w < (*target)[j] {
            (*target)[j + 1] = (*target)[j]
            j -= 1
        }
        (*target)[j + 1] = w
    }
    return (*target)[1:]
}