クイックソート

Javaによるアルゴリズム事典

の P.60 のクイックソートをやってみた。

#!/usr/bin/env python
# -*- coding: utf-8 -*-

def _sort(list, first, last):
    x = list[(first + last) / 2]
    i = first
    j = last
    while True:
        print list
        while list[i] < x :
            i += 1
        while x < list[j] :
            j -= 1
        if i >= j :
            break
        swap = list[i]
        list[i] = list[j]
        list[j] = swap
        i += 1
        j -= 1
    if first < i -1 :
        _sort(list, first , i - 1)
    if j + 1 < last :
        _sort(list, j + 1 , last)
    return list

def sort(list):
    return _sort(list, 0, len(list) -1)
    

if __name__ == "__main__":
    print sort([5,8,2,3,4,1,6,4,0,2])

結果

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

あとで書くかも