• このエントリーをはてなブックマークに追加

スポンサードリンク

はじめに

以下の本を読みながら、アルゴリズムの勉強を始めてます.

書籍では、C, C++の実装例が載っている.自分は、Pythonで実装してみた. 紹介するのは以下.

  • 挿入ソート
  • バブルソート
  • 選択ソート
  • マージソート
  • シェルソート
  • クイックソート

挿入ソート(Insertion Sort)

挿入ソート(インサーションソート)は、ソートのアルゴリズムの一つ。整列 してある配列に追加要素を適切な場所に挿入すること。平均計算時間・最悪計 算時間がともにO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、し ばしば用いられる。安定な内部ソート。基本挿入法ともいう。in-placeアルゴ リズムであり、オンラインアルゴリズムである。

ALDS1_1_A

サンプル問題(AOJ): http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_1_A&lang=jp

N = int(input())
A = list(map(int, input().split()))


def insertion_sort(A, N):
    for i in range(1, N):
        v = A[i]
        j = i - 1
        while j >= 0 and A[j] > v:
            # vより大きければ右へずらす
            A[j+1] = A[j]
            j -= 1
        A[j+1] = v
        print(*A)

print(*A)
insertion_sort(A, N)

バブルソート(Bubble Sort)

バブルソート (bubble sort) は、ソートのアルゴリズムの一つ。隣り合う要 素の大小を比較しながら整列させること。最悪計算時間がO(n2)と遅いが、ア ルゴリズムが単純で実装が容易なため、また並列処理との親和性が高いことか ら、しばしば用いられる。安定な内部ソート。基本交換法、隣接交換法ともい う。(単に交換法と言う場合もある)

ALDS1_2_A

サンプル問題(AOJ) http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_A&lang=jp

N = int(input())
A = list(map(int, input().split()))


def bubble_sort(A, N):
    cnt = 0
    flag = True
    while(flag):
        flag = False
        for i in range(N-1, 0, -1):
            if(A[i-1] > A[i]):
                A[i-1], A[i] = A[i], A[i-1]
                cnt += 1
                flag = True

    print(" ".join(list(map(str, A))))
    print(cnt)

bubble_sort(A, N)

選択ソート(Selection Sort)

選択ソート(英: selection sort)は、ソートのアルゴリズムの一つ。配列さ れた要素から、最大値やまたは最小値を探索し配列最後の要素と入れ替えをお こなうこと。最悪計算時間がO(n2)と遅いが、 アルゴリズムが単純で実装が容易なため、しばしば用いられる。内部ソート。 後述するように、安定ソートではない。

ALDS1_2_B

サンプル問題(AOJ) http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_B&lang=jp

↓のコード、どうしてもAOJ のテストケースを通せなかった。 どこかバグってるのだろうか??

def selection_sort(A, N):
    count = 0
    for i in range(0, N):
        minj = i
        for j in range(i, N):
            if(A[minj] > A[j]):
                minj = j
        if(minj != i):
            count += 1
            A[minj], A[i] = A[i], A[minj]

    print(" ".join(map(str, A)))
    print(count)

N = int(input())
A = list(map(int, input().split()))
selection_sort(A, N)

シェルソート(Shell Sort)

基本的な部分は、挿入ソートと同じである。挿入ソートは「ほとんど整列され たデータに対しては高速」という特長があるものの、「隣り合った要素同士し か交換しない」ため、あまり整列されていないデータに対しては低速であった。

そのため、適当な間隔をあけた飛び飛びのデータ列に対してあらかじめソート しておき、挿入ソートを適用すれば高速になると考えられる。この考え方を適 用したのがシェルソートである。

ALDS1_2_D

サンプル問題(AOJ)

コード省略。解けない..

マージソート(Merge Sort)

分割統治法によるソート.

マージソートは、ソートのアルゴリズムで、既に整列してある複数個の列を1 個の列にマージする際に、小さいものから先に新しい列に並べれば、新しい列 も整列されている、というボトムアップの分割統治法による。大きい列を多数 の列に分割し、そのそれぞれをマージする作業は並列化できる。

n個のデータを含む配列をソートする場合、最悪計算量O(n log n)である。分 割と統合の実装にもよるが、一般に安定なソートを実装できる。インプレース なソートも提案されているが、通常O(n)の外部記憶を必要とする。

(ナイーブな)クイックソートと比べると、最悪計算量は少ない 。ランダムなデータでは通常、クイックソートのほうが速い。

ALDS1_5_B

サンプル問題(AOJ) http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_B&lang=jp

def merge(A, left, mid, right):
    global count
    L = A[left:mid] + [1000000001]
    R = A[mid:right] + [1000000001]
    i = j = 0
    for k in range(left, right):
        if L[i] <= R&#91;j&#93;:
            A&#91;k&#93; = L&#91;i&#93;
            i += 1
        else:
            A&#91;k&#93; = R&#91;j&#93;
            j += 1
    count += right - left


def merge_sort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right)

N = int(input())
A = list(map(int, input().split()))
count = 0
merge_sort(A, 0, N)
print(*A)
print(count)
&#91;/sourcecode&#93;
</div>
</div>
</div>

<div id="outline-container-orgheadline12" class="outline-2">
<h2 id="orgheadline12">クイックソート(Quick Sort)</h2>
<div class="outline-text-2" id="text-orgheadline12">
<blockquote>
<p> クイックソート (quicksort) は、1960年にアントニー・ホーアが開発した ソートのアルゴリズム。分割統治法の一種。 </p>

<p> 最良計算量および平均計算量はO( nlog n )である。他のソート法と比べて、 一般的に最も高速だといわれているが対象のデータの並びやデータの数によっ ては必ずしも速いわけではなく、最悪の計算量はO( n^2)である。また数々 の変種がある。 安定ソートではない。 </p>
</blockquote>
<ul class="org-ul">
<li><a href="https://ja.wikipedia.org/wiki/%E3%82%AF%E3%82%A4%E3%83%83%E3%82%AF%E3%82%BD%E3%83%BC%E3%83%88">クイックソート - Wikipedia</a></li>
</ul>
</div>

<div id="outline-container-orgheadline13" class="outline-3">
<h3 id="orgheadline13">ALDS1_6_B, ALDS1_6_C</h3>
<div class="outline-text-3" id="text-orgheadline13">
<p> サンプル問題(AOJ) <a href="http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_6_B&amp;lang=jp">http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_6_B&lang=jp</a> <a href="http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_6_C&amp;lang=jp">http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_6_C&lang=jp</a> </p>


def partition(a, p, r):
    x = a[r][1]
    i = p - 1
    for j in range(p, r):
        if a[j][1] <= x:
            i = i + 1
            a&#91;i&#93;, a&#91;j&#93; = a&#91;j&#93;, a&#91;i&#93;
    a&#91;i + 1&#93;, a&#91;r&#93; = a&#91;r&#93;, a&#91;i + 1&#93;
    return i + 1
 
 
def quicksort(a, p, r):
    if p < r:
        q = partition(a, p, r)
        quicksort(a, p, q - 1)
        quicksort(a, q + 1, r)

import sys
n = int(input())
a = &#91;&#93;
for i in range(n):
    suit, num = sys.stdin.readline().split()
    a += &#91;&#91;suit, int(num), i&#93;&#93;
 
quicksort(a, 0, len(a) - 1)
&#91;/sourcecode&#93;
</div>
</div>
</div>

<div id="outline-container-orgheadline14" class="outline-2">
<h2 id="orgheadline14">Python 標準ライブラリ</h2>
<div class="outline-text-2" id="text-orgheadline14">
<p> リストオブジェクトに対する操作として、 sort()や, reverse()メソッドが用意されている. </p>


listobj.sort()
listobj.reverce()

スポンサードリンク