28 Nov 2015, 09:33

ソートアルゴリズムのまとめと実装(Python)

はじめに

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

挿入ソート(Insertion Sort)

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

ALDS1_1_A

<div class="outline-text-3" id="text-orgheadline3">
  <p>
    サンプル問題(AOJ): <a href="http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_1_A&lang=jp">http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_1_A&lang=jp</a>
  </p>

  <p>
    [sourcecode language=&#8221;python&#8221; title=&#8221;&#8221; ]<br /> N = int(input())<br /> A = list(map(int, input().split()))
  </p>

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

  <p>
    print(*A)<br /> insertion_sort(A, N)<br /> [/sourcecode]
  </p>
</div>

バブルソート(Bubble Sort)

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

ALDS1_2_A

<div class="outline-text-3" id="text-orgheadline5">
  <p>
    サンプル問題(AOJ) <a href="http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_A&lang=jp">http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_A&lang=jp</a>
  </p>

  <p>
    [sourcecode language=&#8221;python&#8221; title=&#8221;&#8221; ]<br /> N = int(input())<br /> A = list(map(int, input().split()))
  </p>

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

  <p>
    print(&#8221; &#8220;.join(list(map(str, A))))<br /> print(cnt)
  </p>

  <p>
    bubble_sort(A, N)<br /> [/sourcecode]
  </p>
</div>

選択ソート(Selection Sort)

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

ALDS1_2_B

<div class="outline-text-3" id="text-orgheadline7">
  <p>
    サンプル問題(AOJ) <a href="http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_B&lang=jp">http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_B&lang=jp</a>
  </p>

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

  <p>
    [sourcecode language=&#8221;python&#8221; title=&#8221;&#8221; ]<br /> def selection_sort(A, N):<br /> count = 0<br /> for i in range(0, N):<br /> minj = i<br /> for j in range(i, N):<br /> if(A[minj] > A[j]):<br /> minj = j<br /> if(minj != i):<br /> count += 1<br /> A[minj], A[i] = A[i], A[minj]
  </p>

  <p>
    print(&#8221; &#8220;.join(map(str, A)))<br /> print(count)
  </p>

  <p>
    N = int(input())<br /> A = list(map(int, input().split()))<br /> selection_sort(A, N)<br /> [/sourcecode]
  </p>
</div>

シェルソート(Shell Sort)

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

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

ALDS1_2_D

<div class="outline-text-3" id="text-orgheadline9">
  <p>
    サンプル問題(AOJ)
  </p>

  <ul class="org-ul">
    <li>
      <a href="http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_D&lang=jp">http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_D&lang=jp</a>
    </li>
  </ul>

  <p>
    コード省略。解けない..
  </p>
</div>

マージソート(Merge Sort)

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

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

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

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

ALDS1_5_B

<div class="outline-text-3" id="text-orgheadline11">
  <p>
    サンプル問題(AOJ) <a href="http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_B&lang=jp">http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_B&lang=jp</a>
  </p>

  <p>
    [sourcecode language=&#8221;python&#8221; title=&#8221;&#8221; ]<br /> def merge(A, left, mid, right):<br /> global count<br /> L = A[left:mid] + [1000000001]<br /> R = A[mid:right] + [1000000001]<br /> i = j = 0<br /> for k in range(left, right):<br /> if L[i] <= R[j]: A[k] = L[i] i += 1 else: A[k] = R[j] 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) [/sourcecode] </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">クイックソート &#8211; 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&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&lang=jp">http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_6_C&lang=jp</a>
          </p>

          <p>
            [sourcecode language=&#8221;python&#8221; title=&#8221;&#8221; ]<br /> def partition(a, p, r):<br /> x = a[r][1]<br /> i = p &#8211; 1<br /> for j in range(p, r):<br /> if a[j][1] <= x: i = i + 1 a[i], a[j] = a[j], a[i] a[i + 1], a[r] = a[r], a[i + 1] 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 = [] for i in range(n): suit, num = sys.stdin.readline().split() a += [[suit, int(num), i]] quicksort(a, 0, len(a) - 1) [/sourcecode] </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>

                <p>
                  [sourcecode language=&#8221;python&#8221; title=&#8221;&#8221; ]<br /> listobj.sort()<br /> listobj.reverce()<br /> [/sourcecode]
                </p>

                <ul class="org-ul">
                  <li>
                    <a href="http://qiita.com/fantm21/items/6df776d99356ef6d14d4">【Python】ソート &#8211; Qiita</a>
                  </li>
                  <li>
                    <a href="http://www.pythonweb.jp/tutorial/list/index11.html">要素のソート(sortメソッド, reverseメソッド) &#8211; リスト &#8211; Python入門</a>
                  </li>
                </ul>
              </div>
            </div>

            <div id="outline-container-orgheadline15" class="outline-2">
              <h2 id="orgheadline15">
                Special Thanks
              </h2>

              <div class="outline-text-2" id="text-orgheadline15">
                <ul class="org-ul">
                  <li>
                    <p>
                      <a href="http://gigazine.net/news/20140501-sorting/">数あるソートアルゴリズムをビジュアル化し堪能できるサービス「SORTING」 &#8211; GIGAZINE</a>
                    </p>

                    <p>
                      ソーティングアルゴリズムを可視化した動画がオモシロイ.
                    </p>
                  </li>
                </ul>

                <p>
                  <iframe width="560" height="315" src="https://www.youtube.com/embed/kPRA0W1kECg" frameborder="0" allowfullscreen></iframe>
                </p>

                <ul class="org-ul">
                  <li>
                    <a href="http://kojikoji75.hatenablog.com/entry/2013/09/21/115937">プログラムで簡単理解! 7つの超重要な整列アルゴリズム(ソートアルゴリズム)まとめ &#8211; TechNote</a>
                  </li>
                  <li>
                    <p>
                      <a href="http://qiita.com/hiso/items/5c36f50c7de61fe870a2">基本的なソートアルゴリズムまとめ+α。C言語での実装例 &#8211; Qiita</a>
                    </p>

                    <p style="font-size:32px">
                      以上、Happy Hacking!!
                    </p>
                  </li>
                </ul>
              </div>
            </div>