アルゴリズムの比較

このページの内容は文科省の以下の資料を基に作成されたものです。

アルゴリズムの比較

線形探索

def linsearch(a,p):
    for i in range(0,len(a),1):
        if a[i]==p:
            print(" 見つかりました ")
            break

a = [61,15,82,77,21,32,53]
p = 82
linsearch(a,p)

見つからないときには見つからないと報告すべきだよね。

def linsearch(a,p):
    for i in range(0,len(a),1):
        if a[i]==p:
            print(" 見つかりました ")
            return
    print(" 見つかりませんでした ")

a = [25,33,43,51,66,71,88]
p = 43
linsearch(a,p)

検索関数を使用する場合には、ただ要素が見つかったかどうかを知りたいだけではなく、その位置を知りたいことが多い。

配列の添え字は0から始まるので、要素が見つかった場合には必ず0以上の値が返される。そこで、その値とは重複しない値、典型的には-1が値が見つからなかった場合には返される。

def linsearch(a,p):
    for i in range(0,len(a),1):
        if a[i]==p:
            return i
    return -1

a = [25,33,43,51,66,71,88]
p = 43
linsearch(a,p)

値が見つかっていないのにその位置が-1として返されるのは変だと考えるならば、要素が見つからない場合には、Noneを返すようにする方法もある。

def linsearch(a,p):
    for i in range(0,len(a),1):
        if a[i]==p:
            return i
    return None

a = [25,33,43,51,66,71,88]
p = 43
print(linsearch(a,p))

ここからはちょっと脱線。

Pythonらしいプログラム。でも先進的な言語機能を利用しており共通テスト対策としては不適切。

def linsearch(a,p):
    for v in a:
        if v==p:
            print(" 見つかりました ")
            return
    print(" 見つかりませんでした ")

a = [25,33,43,51,66,71,88]
p = 43
linsearch(a,p)

Pythonがとんでもない言語である片りん。

実はプログラムを書かなくても検索ができる。ある集合の中にこの要素はあるかと聞くだけ。

a = [25,33,43,51,66,71,88]
p = 43
print(p in a)
print(44 in a)

先進的な言語機能を利用していて共通テスト対策にはならないけど、実務的に有益な例。単純すぎて実際に関数化しないと思うけど。。。Pythonが広く利用されるようになっている理由の一つ：ある意味アルゴリズムを考えなくてもプログラムは書ける。。。ことが結構ある。

def linsearch(a,p):
    if p in a:
        print(" 見つかりました ")
    else:
        print(" 見つかりませんでした ")

a = [25,33,43,51,66,71,88]
p = 43
linsearch(a,p)

二分探索

コメントなさすぎ。

def binsearch(a,p):
    i = 0
    j = len(a)-1
    while i<=j:
        m = int((i+j)/2)
        if a[m]==p:
            print(" 見つかりました ")
            break
        else:
            if a[m]>p:
                j=m-1
            else:
                i=m+1

a = [25,33,43,51,66,71,88]
p = 43
binsearch(a,p)
def binsearch(a,p):
    i = 0
    j = len(a)-1
    while i<=j:
        m = int((i+j)/2)
        if a[m]==p:
            print(" 見つかりました ")
            return
        else:
            if a[m]>p:
                j=m-1
            else:
                i=m+1
    print(" 見つかりませんでした ")

a = [25,33,43,51,66,71,88]
p = 43
binsearch(a,p)

探索回数の表示と比較

選択ソート

def selectionsort(a):
    for i in range(0,len(a),1):
        for j in range(i+1,len(a),1):
            if a[j]<a[i]:
                temp = a[i]
                a[i] = a[j]
                a[j] = temp

a = [7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1]
print(" ソート前 ",a)
selectionsort(a)
print(" ソート後 ",a)

参考までに。。。Python恐るべし。複数の代入を並行して一度に実施できるので、一時的な退避先はいらない。

def selectionsort(a):
    for i in range(0,len(a),1):
        for j in range(i+1,len(a),1):
            if a[j]<a[i]:
                a[i], a[j] = a[j], a[i]

a = [7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1]
print(" ソート前 ",a)
selectionsort(a)
print(" ソート後 ",a)

クイックソート

def quicksort(a,start,end):
    m = int((start+end)/2)
    i = start
    j = end
    while(i<j):
        while a[i] < a[m]:
            i = i+1
        while a[j] > a[m]:
            j = j-1
        if i>=j:
            break
        temp = a[i]
        a[i] = a[j]
        a[j] = temp
        if i==m:
            m = j
        elif j==m:
            m = i
        i = i+1
        j = j-1
    if start < i-1:
        quicksort(a,start,m-1)
    if end > j+1:
        quicksort(a,m+1,end)

a = [7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1]
print(" ソート前 ",a)
quicksort(a,0,len(a)-1)
print(" ソート後 ",a)