sort – TauStation

概要

クイックソートは、特定の値（ピボット）を基準にして、データの先頭と最後尾から1つずつ中央に近づけていきながら、ピボットより小さなデータが前に、大きなデータが後ろに配置されるように交換し、その処理を再帰的に行っていく。

考え方

以下2段階に分けて、与えられたデータ列をピボット以上・未満に振り分ける操作と、それらを再帰的に実行していく操作を示す。

ピボットの取り方にはいろいろあるようだが、ここでは与えられたデータの先頭と最後尾の値の平均値とする。

部分列に対する操作

以下の図で、4,6,2,…5のデータの部分列が与えられたとする。その際の操作は以下の通り。

⓪　部分列の先頭と最後尾のデータの平均を計算し、それをピボットとして設定(4.5)
①　左からピボット以上のデータを探索(6≥4.5)、右からピボット未満のデータを探索(1<4.5)
②　探索した左右のデータを交換
③　さらに左からピボット以上のデータを探索(7≥4.5)、右からピボット未満のデータを探索(0<4.5)
④　探索した左右のデータを交換
⑤　さらに探索を進めた結果、左右のポインターが交差
- このとき、境界より左にピボット未満、境界より右にピボット以上のデータが格納されている
- 3を境界とし、境界を含む左側とそれより右側の部分列に分けて、再帰的に探索を行う

再帰処理

部分列の操作を踏まえたうえで、それらの再帰的な処理の様子を下図に示す。図中、それぞれの線種や背景色の意味は以下の通り

二重枠囲みはピボットの値
赤はピボット以上のデータ
青はピボット未満のデータ
黄色は境界値
緑色は位置が確定したデータ

各段階の処理は以下の通り。

①　元の列からピボット以上／未満のデータを振り分け
②　左側の部分列に対する再帰1段目、ピボットによる振り分け
③　左側の部分列に対する再帰2段目、ピボットによる振り分け
④　左側の部分列に対する再帰3段目、ピボットによる振り分け
⑤⑥　左側・右側の再帰終了、0と1の位置確定
⑦　右側の部分列に対する再帰3段目
⑧⑨　左側・右側の再帰終了、2と3の位置確定
⑩　右側の再帰終了、4の位置確定（ここで再帰1段目の左側終了）
⑪　右側の部分列に対する再帰1段目、ピボットによる振り分け
⑫　左側の再帰終了、5の位置確定
⑬　右側の再帰2段目、ピボットによる振り分け
⑭⑮　左側・右側の再帰終了、6と7の位置確定

コード

以下はPythonによる実装。全体のデータ列に対して位置を指定して並べ替えを実行する再帰関数quick_sort_core()を定義し、全体列に対してこれを呼び出す入口の関数quick_sort()を定義。

def quick_sort(data):
    quick_sort_core(data, 0, len(data)-1)

def quick_sort_core(data, org_left, org_right):
    if org_left == org_right: return

    left = org_left
    right = org_right
    pivot = (data[org_left] + data[org_right]) / 2

    while True:
        while data[left] < pivot:
            left += 1
            if left > org_right: return
        while data[right] >= pivot:
            right -= 1
            if right < org_left: return
        if left >= right:
            border = right
            break
        data[left], data[right] = data[right], data[left]

    quick_sort_core(data, org_left, border)
    quick_sort_core(data, border+1, org_right)

def quick_sort(data):

quick_sort_core(data, 0, len(data)-1)

def quick_sort_core(data, org_left, org_right):

if org_left == org_right: return

left = org_left

right = org_right

pivot = (data[org_left] + data[org_right]) / 2

while True:

while data[left] < pivot:

left += 1

if left > org_right: return

while data[right] >= pivot:

right -= 1

if right < org_left: return

if left >= right:

border = right

break

data[left], data[right] = data[right], data[left]

quick_sort_core(data, org_left, border)

quick_sort_core(data, border+1, org_right)

例示したデータに対して実行。

data = [4, 6, 2, 7, 3, 0, 1, 5]
quick_sort(data)
print(data)

# [0, 1, 2, 3, 4, 5, 6, 7]

data = [4, 6, 2, 7, 3, 0, 1, 5]

quick_sort(data)

print(data)

# [0, 1, 2, 3, 4, 5, 6, 7]

要素がすべて同じで、要素数が偶数・奇数の場合も正常に動作。

data = [1, 1, 1, 1]
quick_sort(data)
print(data)

data = [1, 1, 1, 1, 1]
quick_sort(data)
print(data)

# [1, 1, 1, 1]
# [1, 1, 1, 1, 1]

data = [1, 1, 1, 1]

quick_sort(data)

print(data)

data = [1, 1, 1, 1, 1]

quick_sort(data)

print(data)

# [1, 1, 1, 1]

# [1, 1, 1, 1, 1]

同じ要素が複数含まれる場合も正常に動作。

data = [2, 1, 2, 1, 1]
print(data)
quick_sort(data)
print(data)

# [1, 1, 1, 2, 2]

data = [2, 1, 2, 1, 1]

print(data)

quick_sort(data)

print(data)

# [1, 1, 1, 2, 2]

動作状況の確認

並べ替えの動作中の状況を以下のコードで確認。各所にprint()関数をちりばめてみる。

import random

def quick_sort(data):
    quick_sort_core(data, 0, len(data)-1)

def quick_sort_core(data, org_left, org_right):
    print('function start')
    print(data[org_left:org_right+1], end=' ')
    if org_left == org_right:
        print('return')
        return

    left = org_left
    right = org_right
    pivot = (data[org_left] + data[org_right]) / 2
    print('pivot', pivot, '<-', data[org_left], data[org_right])

    while True:
        print(data[org_left:org_right+1], pivot, 'check', data[left], data[right])
        while data[left] < pivot:
            left += 1
            print(data[org_left:org_right+1], 'left+1 ->', data[left])
            if left > org_right:
                print(data[left], '>', data[org_right], 'return')
                return
        while data[right] >= pivot:
            right -= 1
            print(data[org_left:org_right+1], 'right-1 ->', data[right])
            if right < org_left:
                print(data[org_left], '>', data[right], 'return')
                return
        if left >= right:
            border = right
            print(data[left], '>=', data[right], 'border=', data[border])
            break
        data[left], data[right] = data[right], data[left]
        print(data[org_left:org_right+1], 'switched', data[left], data[right])

    quick_sort_core(data, org_left, border)
    quick_sort_core(data, border+1, org_right)

data = [4, 6, 2, 7, 3, 0, 1, 5]
quick_sort(data)
print(data)

import random

def quick_sort(data):

quick_sort_core(data, 0, len(data)-1)

def quick_sort_core(data, org_left, org_right):

print('function start')

print(data[org_left:org_right+1], end=' ')

if org_left == org_right:

print('return')

return

left = org_left

right = org_right

pivot = (data[org_left] + data[org_right]) / 2

print('pivot', pivot, '<-', data[org_left], data[org_right])

while True:

print(data[org_left:org_right+1], pivot, 'check', data[left], data[right])

while data[left] < pivot:

left += 1

print(data[org_left:org_right+1], 'left+1 ->', data[left])

if left > org_right:

print(data[left], '>', data[org_right], 'return')

return

while data[right] >= pivot:

right -= 1

print(data[org_left:org_right+1], 'right-1 ->', data[right])

if right < org_left:

print(data[org_left], '>', data[right], 'return')

return

if left >= right:

border = right

print(data[left], '>=', data[right], 'border=', data[border])

break

data[left], data[right] = data[right], data[left]

print(data[org_left:org_right+1], 'switched', data[left], data[right])

quick_sort_core(data, org_left, border)

quick_sort_core(data, border+1, org_right)

data = [4, 6, 2, 7, 3, 0, 1, 5]

quick_sort(data)

print(data)

動作結果は以下の通りで、再帰的に実行されているのがわかる。

function start
[4, 6, 2, 7, 3, 0, 1, 5] pivot 4.5 <- 4 5
[4, 6, 2, 7, 3, 0, 1, 5] 4.5 check 4 5
[4, 6, 2, 7, 3, 0, 1, 5] left+1 -> 6
[4, 6, 2, 7, 3, 0, 1, 5] right-1 -> 1
[4, 1, 2, 7, 3, 0, 6, 5] switched 1 6
[4, 1, 2, 7, 3, 0, 6, 5] 4.5 check 1 6
[4, 1, 2, 7, 3, 0, 6, 5] left+1 -> 2
[4, 1, 2, 7, 3, 0, 6, 5] left+1 -> 7
[4, 1, 2, 7, 3, 0, 6, 5] right-1 -> 0
[4, 1, 2, 0, 3, 7, 6, 5] switched 0 7
[4, 1, 2, 0, 3, 7, 6, 5] 4.5 check 0 7
[4, 1, 2, 0, 3, 7, 6, 5] left+1 -> 3
[4, 1, 2, 0, 3, 7, 6, 5] left+1 -> 7
[4, 1, 2, 0, 3, 7, 6, 5] right-1 -> 3
7 >= 3 border= 3
function start
[4, 1, 2, 0, 3] pivot 3.5 <- 4 3
[4, 1, 2, 0, 3] 3.5 check 4 3
[3, 1, 2, 0, 4] switched 3 4
[3, 1, 2, 0, 4] 3.5 check 3 4
[3, 1, 2, 0, 4] left+1 -> 1
[3, 1, 2, 0, 4] left+1 -> 2
[3, 1, 2, 0, 4] left+1 -> 0
[3, 1, 2, 0, 4] left+1 -> 4
[3, 1, 2, 0, 4] right-1 -> 0
4 >= 0 border= 0
function start
[3, 1, 2, 0] pivot 1.5 <- 3 0
[3, 1, 2, 0] 1.5 check 3 0
[0, 1, 2, 3] switched 0 3
[0, 1, 2, 3] 1.5 check 0 3
[0, 1, 2, 3] left+1 -> 1
[0, 1, 2, 3] left+1 -> 2
[0, 1, 2, 3] right-1 -> 2
[0, 1, 2, 3] right-1 -> 1
2 >= 1 border= 1
function start
[0, 1] pivot 0.5 <- 0 1
[0, 1] 0.5 check 0 1
[0, 1] left+1 -> 1
[0, 1] right-1 -> 0
1 >= 0 border= 0
function start
[0] return
function start
[1] return
function start
[2, 3] pivot 2.5 <- 2 3
[2, 3] 2.5 check 2 3
[2, 3] left+1 -> 3
[2, 3] right-1 -> 2
3 >= 2 border= 2
function start
[2] return
function start
[3] return
function start
[4] return
function start
[7, 6, 5] pivot 6.0 <- 7 5
[7, 6, 5] 6.0 check 7 5
[5, 6, 7] switched 5 7
[5, 6, 7] 6.0 check 5 7
[5, 6, 7] left+1 -> 6
[5, 6, 7] right-1 -> 6
[5, 6, 7] right-1 -> 5
6 >= 5 border= 5
function start
[5] return
function start
[6, 7] pivot 6.5 <- 6 7
[6, 7] 6.5 check 6 7
[6, 7] left+1 -> 7
[6, 7] right-1 -> 6
7 >= 6 border= 6
function start
[6] return
function start
[7] return
[0, 1, 2, 3, 4, 5, 6, 7]

function start

[4, 6, 2, 7, 3, 0, 1, 5] pivot 4.5 <- 4 5

[4, 6, 2, 7, 3, 0, 1, 5] 4.5 check 4 5

[4, 6, 2, 7, 3, 0, 1, 5] left+1 -> 6

[4, 6, 2, 7, 3, 0, 1, 5] right-1 -> 1

[4, 1, 2, 7, 3, 0, 6, 5] switched 1 6

[4, 1, 2, 7, 3, 0, 6, 5] 4.5 check 1 6

[4, 1, 2, 7, 3, 0, 6, 5] left+1 -> 2

[4, 1, 2, 7, 3, 0, 6, 5] left+1 -> 7

[4, 1, 2, 7, 3, 0, 6, 5] right-1 -> 0

[4, 1, 2, 0, 3, 7, 6, 5] switched 0 7

[4, 1, 2, 0, 3, 7, 6, 5] 4.5 check 0 7

[4, 1, 2, 0, 3, 7, 6, 5] left+1 -> 3

[4, 1, 2, 0, 3, 7, 6, 5] left+1 -> 7

[4, 1, 2, 0, 3, 7, 6, 5] right-1 -> 3

7 >= 3 border= 3

function start

[4, 1, 2, 0, 3] pivot 3.5 <- 4 3

[4, 1, 2, 0, 3] 3.5 check 4 3

[3, 1, 2, 0, 4] switched 3 4

[3, 1, 2, 0, 4] 3.5 check 3 4

[3, 1, 2, 0, 4] left+1 -> 1

[3, 1, 2, 0, 4] left+1 -> 2

[3, 1, 2, 0, 4] left+1 -> 0

[3, 1, 2, 0, 4] left+1 -> 4

[3, 1, 2, 0, 4] right-1 -> 0

4 >= 0 border= 0

function start

[3, 1, 2, 0] pivot 1.5 <- 3 0

[3, 1, 2, 0] 1.5 check 3 0

[0, 1, 2, 3] switched 0 3

[0, 1, 2, 3] 1.5 check 0 3

[0, 1, 2, 3] left+1 -> 1

[0, 1, 2, 3] left+1 -> 2

[0, 1, 2, 3] right-1 -> 2

[0, 1, 2, 3] right-1 -> 1

2 >= 1 border= 1

function start

[0, 1] pivot 0.5 <- 0 1

[0, 1] 0.5 check 0 1

[0, 1] left+1 -> 1

[0, 1] right-1 -> 0

1 >= 0 border= 0

function start

[0] return

function start

[1] return

function start

[2, 3] pivot 2.5 <- 2 3

[2, 3] 2.5 check 2 3

[2, 3] left+1 -> 3

[2, 3] right-1 -> 2

3 >= 2 border= 2

function start

[2] return

function start

[3] return

function start

[4] return

function start

[7, 6, 5] pivot 6.0 <- 7 5

[7, 6, 5] 6.0 check 7 5

[5, 6, 7] switched 5 7

[5, 6, 7] 6.0 check 5 7

[5, 6, 7] left+1 -> 6

[5, 6, 7] right-1 -> 6

[5, 6, 7] right-1 -> 5

6 >= 5 border= 5

function start

[5] return

function start

[6, 7] pivot 6.5 <- 6 7

[6, 7] 6.5 check 6 7

[6, 7] left+1 -> 7

[6, 7] right-1 -> 6

7 >= 6 border= 6

function start

[6] return

function start

[7] return

[0, 1, 2, 3, 4, 5, 6, 7]