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

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

<div class='amazlink-box' style='text-align:left;padding-bottom:20px;font-size:small;/zoom: 1;overflow: hidden;'>
  <div class='amazlink-list' style='clear: both;'>
    <div class='amazlink-image' style='float:left;margin:0px 12px 1px 0px;'>
      <a href='https://www.amazon.co.jp/%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E3%82%B3%E3%83%B3%E3%83%86%E3%82%B9%E3%83%88%E6%94%BB%E7%95%A5%E3%81%AE%E3%81%9F%E3%82%81%E3%81%AE%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%81%A8%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0-%E6%B8%A1%E9%83%A8-%E6%9C%89%E9%9A%86/dp/4839952957%3FSubscriptionId%3DAKIAJDINZW45GEGLXQQQ%26tag%3Dsleephacker-22%26linkCode%3Dxm2%26camp%3D2025%26creative%3D165953%26creativeASIN%3D4839952957https://ecx.images-amazon.com/images/I/51oWwpzibRL._SL160_.jpg' style='border: none;' /></a>
    </div>
    
    <div class='amazlink-info' style='height:160; margin-bottom: 10px'>
      <div class='amazlink-name' style='margin-bottom:10px;line-height:120%'>
        <a href='https://www.amazon.co.jp/%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E3%82%B3%E3%83%B3%E3%83%86%E3%82%B9%E3%83%88%E6%94%BB%E7%95%A5%E3%81%AE%E3%81%9F%E3%82%81%E3%81%AE%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%81%A8%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0-%E6%B8%A1%E9%83%A8-%E6%9C%89%E9%9A%86/dp/4839952957%3FSubscriptionId%3DAKIAJDINZW45GEGLXQQQ%26tag%3Dsleephacker-22%26linkCode%3Dxm2%26camp%3D2025%26creative%3D165953%26creativeASIN%3D4839952957' rel='nofollow' target='_blank'>プログラミングコンテスト攻略のためのアルゴリズムとデータ構造</a>
      </div>
      
      <div class='amazlink-powered' style='font-size:80%;margin-top:5px;line-height:120%'>
        posted with <a href='https://amazlink.keizoku.com/' title='アマゾンアフィリエイトリンク作成ツール' target='_blank'>amazlink</a> at 15.11.28
      </div>
      
      <div class='amazlink-detail'>
        渡部 有隆
      </div>
      
      <div class='amazlink-sub-info' style='float: left;'>
        <div class='amazlink-link' style='margin-top: 5px'>
          <img src='https://amazlink.fuyu.gs/icon_amazon.png' width='18' /><a href='https://www.amazon.co.jp/%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E3%82%B3%E3%83%B3%E3%83%86%E3%82%B9%E3%83%88%E6%94%BB%E7%95%A5%E3%81%AE%E3%81%9F%E3%82%81%E3%81%AE%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%81%A8%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0-%E6%B8%A1%E9%83%A8-%E6%9C%89%E9%9A%86/dp/4839952957%3FSubscriptionId%3DAKIAJDINZW45GEGLXQQQ%26tag%3Dsleephacker-22%26linkCode%3Dxm2%26camp%3D2025%26creative%3D165953%26creativeASIN%3D4839952957' 
        </div>
      </div>
    </div>
  </div>
</div>

<ul class="org-ul">
  <li>
    <a href="https://judge.u-aizu.ac.jp/onlinejudge/user.jsp?id=tsu_nera">https://judge.u-aizu.ac.jp/onlinejudge/user.jsp?id=tsu_nera</a>
  </li>
</ul>

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

<ul class="org-ul">
  <li>
    挿入ソート
  </li>
  <li>
    バブルソート
  </li>
  <li>
    選択ソート
  </li>
  <li>
    マージソート
  </li>
  <li>
    シェルソート
  </li>
  <li>
    クイックソート
  </li>
</ul>

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

<ul class="org-ul">
  <li>
    <a href="https://ja.wikipedia.org/wiki/%E6%8C%BF%E5%85%A5%E3%82%BD%E3%83%BC%E3%83%88">挿入ソート - Wikipedia</a>
  </li>
</ul>

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

<ul class="org-ul">
  <li>
    <a href="https://ja.wikipedia.org/wiki/%E3%83%90%E3%83%96%E3%83%AB%E3%82%BD%E3%83%BC%E3%83%88">バブルソート - Wikipedia</a>
  </li>
</ul>

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

<ul class="org-ul">
  <li>
    <a href="https://ja.wikipedia.org/wiki/%E9%81%B8%E6%8A%9E%E3%82%BD%E3%83%BC%E3%83%88">選択ソート - Wikipedia</a>
  </li>
</ul>

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

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

<ul class="org-ul">
  <li>
    <a href="https://ja.wikipedia.org/wiki/%E3%82%B7%E3%82%A7%E3%83%AB%E3%82%BD%E3%83%BC%E3%83%88">シェルソート - Wikipedia</a>
  </li>
</ul>

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

<blockquote>
  <p>
    マージソートは、ソートのアルゴリズムで、既に整列してある複数個の列を1 個の列にマージする際に、小さいものから先に新しい列に並べれば、新しい列 も整列されている、というボトムアップの分割統治法による。大きい列を多数 の列に分割し、そのそれぞれをマージする作業は並列化できる。
  </p>
  
  <p>
    n個のデータを含む配列をソートする場合、最悪計算量O(n log n)である。分 割と統合の実装にもよるが、一般に安定なソートを実装できる。インプレース なソートも提案されているが、通常O(n)の外部記憶を必要とする。
  </p>
  
  <p>
    （ナイーブな）クイックソートと比べると、最悪計算量は少ない 。ランダムなデータでは通常、クイックソートのほうが速い。
  </p>
</blockquote>

<ul class="org-ul">
  <li>
    <a href="https://ja.wikipedia.org/wiki/%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88">マージソート - Wikipedia</a>
  </li>
</ul>