基本情報技術者試験のデータ構造及びアルゴリズム問題をPythonで実装する（平成三十年度春期）。

この問題では、ちょっと正しくない実装になっている。

はろー、yukiです。

基本的に試験問題にある通りに実装していますが、うまくいかないこともあります。

pythonならではの仕様とかが主な要因です。

今回の試験内容は、ヒープソートになります。

ソーティングはアルゴリズムの基本的な内容です（どの本にも書いてあります）。

ですので、アルゴリズムの本を読めば、他のソート問題が出ても対応できると思います。

ちなみに、僕が読んでいるのは「はじめてのアルゴリズ / 上原 隆平」です。

　※もっと良い本があれば、ご紹介ください

それでは、コードをみてみましょう。

# H30 春
import math

data = [60, 35, 45, 15, 5, 10, 20]
heap = []
hnum = len(data)

def lchild(i):
    i = 2 * i + 1
    return i

def rchild(i):
    i = 2 * i + 2
    return i

def parent(i):
    i = math.floor((i - 1) / 2)
    return i

def makeHeap(data, heap, hnum):
    for i in range(0, hnum):
        heap.append(data[i])

    for i in range(0, hnum):
        # heap.append(data[i])
        k = i

        # Because k = 0, under process is never used...why?
        while k > 0:
            if heap[k] > heap[parent(k)]:
                swap(heap, k, heap[k])
                k = parent(k)
        else:
            break

def swap(heap, i, j):
    tmp = int()
    tmp = heap[i]
    heap[i] = heap[j]
    heap[j] = tmp

def heapSort(data, heap, hnum):
    last = hnum - 1

    makeHeap(data, heap, hnum)

    for last in reversed(range(0, hnum)):
        swap(heap, 0, last)
        downHeap(heap, last - 1)
    
def downHeap(heap, hlast):
    n = 0

    if lchild(n) <= hlast:
        tmp = lchild(n)

        if rchild(n) <= hlast:
            if heap[tmp] <= heap[rchild(n)]:
                tmp = rchild(n)
        
        if heap[tmp] > heap[n]:
            swap(heap, n, tmp)
        else:
            return
        
        n = tmp

print("Before:", data)
heapSort(data, heap, hnum)
print("After:", heap)

配列parentでは、小数点以下を切り捨てた値を格納するため、mathライブラリを使用しています。

コードを実行すると、整列前と後の結果を表示するようにしています。

Before: [60, 35, 45, 15, 5, 10, 20]
After: [5, 10, 15, 20, 35, 45, 60]

今回のコードは予想した結果通りに動くのですが、二つ分からない点があります。

一つ目に、「# Because k = 0, under process is never used...why?」の部分。

while k > 0: 以下の処理は何に使うのでしょうか。。。

ブレークポイントを置いても、処理に使われなかったような。。。

二つ目に、本当は正しく整列されないという点です。

整列対象の数値で、先頭の数値を、他の数値よりも低くした場合、正しくありません。

また、先頭以外の数値を、先頭よりも高くした場合も、正しくなりません。

これはミスだと思います。

ですので、まるごとコピーしたり、写経するのはあまりお勧めできません。

むしろ、正しくない部分を指摘できる方がおられれば、コメント欄に投稿をお願いします。

以上