## 2018年12月17日月曜日

### Algorithm - Python - 整理が苦手な修理屋(クイックソート、ピボット、移動個数、近似式、インプレースピボット決め、再帰インプレースソート)

コード(Emacs)

Python 3

```#!/usr/bin/env python3
def pivot_partition_clever(lst: list, start: int, end: int) -> (int, int):
pivot = lst[end]
bottom = start - 1
top = end
done = False
move_count = 0
while not done:
while not done:
bottom += 1
if bottom == top:
done = True
break
if lst[bottom] > pivot:
lst[top] = lst[bottom]
move_count += 1
break
while not done:
top -= 1
if top == bottom:
done = True
break
if lst[top] <= pivot:
lst[bottom] = lst[top]
move_count += 1
break
lst[top] = pivot

def quick_sort(lst: list, start: int, end: int) -> None:
'''
>>> a = [4, 65, 2, -31, 0, 99, 83, 782, 1]
>>> quick_sort(a, 0, len(a) - 1)
9
>>> a
[-31, 0, 1, 2, 4, 65, 83, 99, 782]
>>> l = list(range(100))
>>> quick_sort(l, 0, len(l) - 1)
0
>>> d = list(range(99, -1, -1))
>>> quick_sort(d, 0, len(d) - 1)
50
>>> d = list(range(-1, -1, -1))
>>> quick_sort(d, 0, len(d) - 1)
0
>>> d = list(range(0, -1, -1))
>>> quick_sort(d, 0, len(d) - 1)
0
>>> d = list(range(1, -1, -1))
>>> quick_sort(d, 0, len(d) - 1)
1
>>> d = list(range(10, -1, -1))
>>> quick_sort(d, 0, len(d) - 1)
5
>>> d = list(range(11, -1, -1))
>>> quick_sort(d, 0, len(d) - 1)
6
'''
move_count = 0
if start < end:
pivot_index, count = pivot_partition_clever(lst, start, end)
move_count += count
move_count += quick_sort(lst, start, pivot_index - 1)
move_count += quick_sort(lst, pivot_index + 1, end)
return move_count

if __name__ == '__main__':
import doctest
doctest.testmod()
# 要素数nの場合の近似式 n // 2
```

```\$ ./sample1.py -v
Trying:
a = [4, 65, 2, -31, 0, 99, 83, 782, 1]
Expecting nothing
ok
Trying:
quick_sort(a, 0, len(a) - 1)
Expecting:
9
ok
Trying:
a
Expecting:
[-31, 0, 1, 2, 4, 65, 83, 99, 782]
ok
Trying:
l = list(range(100))
Expecting nothing
ok
Trying:
quick_sort(l, 0, len(l) - 1)
Expecting:
0
ok
Trying:
d = list(range(99, -1, -1))
Expecting nothing
ok
Trying:
quick_sort(d, 0, len(d) - 1)
Expecting:
50
ok
Trying:
d = list(range(-1, -1, -1))
Expecting nothing
ok
Trying:
quick_sort(d, 0, len(d) - 1)
Expecting:
0
ok
Trying:
d = list(range(0, -1, -1))
Expecting nothing
ok
Trying:
quick_sort(d, 0, len(d) - 1)
Expecting:
0
ok
Trying:
d = list(range(1, -1, -1))
Expecting nothing
ok
Trying:
quick_sort(d, 0, len(d) - 1)
Expecting:
1
ok
Trying:
d = list(range(10, -1, -1))
Expecting nothing
ok
Trying:
quick_sort(d, 0, len(d) - 1)
Expecting:
5
ok
Trying:
d = list(range(11, -1, -1))
Expecting nothing
ok
Trying:
quick_sort(d, 0, len(d) - 1)
Expecting:
6
ok