## 2018年12月19日水曜日

### Algorithm - Python - 整理が苦手な修理屋(未ソート配列のk番目に小さい要素のの探索、再帰分割、インプレースピボット決め、再帰インプレースソート)

コード(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:
move_count += 1
bottom += 1
if bottom == top:
done = True
break
if lst[bottom] > pivot:
lst[top] = lst[bottom]
break
while not done:
move_count += 1
top -= 1
if top == bottom:
done = True
break
if lst[top] <= pivot:
lst[bottom] = lst[top]
break
lst[top] = pivot

def quick_select(lst: list, start: int, end: int, k: int) -> int:
'''
>>> quick_select([10], 0, 0, 1)
10
>>> quick_select([0, 1, 2, 3, 4], 0, 4, 1)
0
>>> quick_select([0, 1, 2, 3, 4], 0, 4, 5)
4
>>> quick_select([0, 1, 2, 3, 4], 0, 4, 2)
1
>>> quick_select([0, 1, 2, 3, 4], 0, 4, 3)
2
>>> quick_select([4, 65, 2, -31, 0, 99, 83, 782, 1], 0, 8, 1)
-31
>>> quick_select([4, 65, 2, -31, 0, 99, 83, 782, 1], 0, 8, 9)
782
>>> quick_select([4, 65, 2, -31, 0, 99, 83, 782, 1], 0, 8, 4)
2
>>> quick_select([4, 65, 2, -31, 0, 99, 83, 782, 1], 0, 8, 5)
4
'''
if start < end:
pivot_index, _ = pivot_partition_clever(lst, start, end)
if pivot_index == k - 1:
return lst[pivot_index]
if pivot_index > k - 1:
return quick_select(lst, start, pivot_index - 1, k)
return quick_select(lst, pivot_index + 1, end, k)
return lst[k - 1]

if __name__ == '__main__':
import doctest
doctest.testmod()

import random
n = 20
l = list(range(n, 0, -1))
print(l)
print(sorted(l))
for k in range(1, n + 1):
random.shuffle(l)
sorted_l = sorted(l)
num = quick_select(l, 0, len(l) - 1, k)
print(f'k = {k}, num = {num}, {sorted_l[k - 1]}, '
f'{sorted_l[k - 1] == num}')
```

```\$ ./sample3.py -v
Trying:
quick_select([0, 1, 2, 3, 4], 0, 4, 1)
Expecting:
0
ok
Trying:
quick_select([0, 1, 2, 3, 4], 0, 4, 5)
Expecting:
4
ok
Trying:
quick_select([0, 1, 2, 3, 4], 0, 4, 2)
Expecting:
1
ok
Trying:
quick_select([0, 1, 2, 3, 4], 0, 4, 3)
Expecting:
2
ok
Trying:
quick_select([4, 65, 2, -31, 0, 99, 83, 782, 1], 0, 8, 1)
Expecting:
-31
ok
Trying:
quick_select([4, 65, 2, -31, 0, 99, 83, 782, 1], 0, 8, 9)
Expecting:
782
ok
Trying:
quick_select([4, 65, 2, -31, 0, 99, 83, 782, 1], 0, 8, 4)
Expecting:
2
ok
Trying:
quick_select([4, 65, 2, -31, 0, 99, 83, 782, 1], 0, 8, 5)
Expecting:
4
ok
__main__
__main__.pivot_partition_clever
1 items passed all tests:
8 tests in __main__.quick_select
8 tests in 3 items.
8 passed and 0 failed.
Test passed.
[20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
k = 1, num = 1, 1, True
k = 2, num = 2, 2, True
k = 3, num = 3, 3, True
k = 4, num = 4, 4, True
k = 5, num = 5, 5, True
k = 6, num = 6, 6, True
k = 7, num = 7, 7, True
k = 8, num = 8, 8, True
k = 9, num = 9, 9, True
k = 10, num = 10, 10, True
k = 11, num = 11, 11, True
k = 12, num = 12, 12, True
k = 13, num = 13, 13, True
k = 14, num = 14, 14, True
k = 15, num = 15, 15, True
k = 16, num = 16, 16, True
k = 17, num = 17, 17, True
k = 18, num = 18, 18, True
k = 19, num = 19, 19, True
k = 20, num = 20, 20, True
\$
```