ソートのプログラムを作ってみよう

今日の前提条件

• 言語：JavaScriptを使って例示するけど、他の言語でチャレンジしてもOKです （概して Ruby Python Haskell あたりはかっこよくスマートに書ける）。

  • node.js で実行しても、ブラウザの開発ツールで実行しても、Atom等のエディタの中で実行しても、どれでも大丈夫。

• 配列をソートする機能ぐらいはほぼどんなプログラミング言語でも既存のものが用意されていて（たとえばJSだとこれ）、 平岡も普段は「あるのならそれを使うのが正解」と思って暮らしてますが、

  ここでは勉強のため、既存のライブラリを使うのを封印して自分で書いてみましょう。

  • sortそのもの以外の関数やメソッド（典型的には Math.max や Array.prototype.reduce）は、 こだわる人はこれも使わない選択をしてもいいが、 一度にいろいろチャレンジすると疲れるので、第１段階ではありものを借用して 第２段階で自作してみる、というアプローチをお勧めする。

• 枠組み

  function mySort(ary) {    // 名前は本家とぶつからないようにしておくのが無難
  
    return ソートられた配列
  }
  // と定義しておいて
  mysort([6, 5, 3, 23, 13, 21, 2, 28, 19, 12, 9, 18, 16, 7, 11, 1, 25, 26, 14, 24, 17, 22, 8, 27, 10, 29, 15, 20, 4, 30])
  // のように使う

  • ちなみに 上記のサンプル数列は rubyで [*1..30].shuffle で生成させたもの（重複なしの乱数列）。これが一番手軽に作れる。
  • JavaScriptで Math.random を使う方法はあとで考えてみましょう。

方式について

• ソートの（アルゴリズムの）いろいろ：

  • 「ソート 単純」で検索（しようと）すると、単純選択、単純挿入、単純交換、が候補に現れる。わかりやすい（性能のことは入門の段階では考えなくていいので棚に上げるとして）のはこの３つだろう。
  • 性能向上のため様々な方式がこれまでに提案されている（Wikipediaには詳しく列挙されれているようだが詳細はここでは略す）。
  • 有名なアルゴリズムとして、マージソート クィックソート ヒープソートなどが、 たとえばこのページ に紹介されている。

• 今日扱うもの：

  単純選択（いわゆる単純ソート）、単純交換（バブルソート）と、 少し高度なものとしてマージソートをここで扱う。

• 可視化について：

  • マージソートの紹介動画が、NHKのピタゴラスイッチで「しめじソート」として作られ話題になっている（いちど見ておいて下さい）。
  • 他にもソートの経過を可視化したページや動画が多数あるようだ。
  • プログラミングになれたら自分で可視化することにも挑戦してみてね。

単純ソート（実際に作ってみる）

1. 配列の長さ（ここでは前述の枠組みに沿って 配列 ary の長さをまず取り出すことにする）

   const n = _____

   • 時々こうやって空枠を作るので自分で調べてみて下さい。
   • おそらく n の値を後で書き換える必要はないので、var でも let でもなく const にしました。
   • （薀蓄１）メソッドでなくフィールド（インスタンス変数のような）で得られる言語は割と珍しいかも。
   • （薀蓄２）配列の「長さ（スペースの広さ）」なのに n がよく使われるのは、その昔は、広いスペース（長い配列）を用意しておいてそこにデータを流し込んで（後ろの方には 空きスペースができる）配列計算をする文化があったので、 ここでは「（要素の）数」という意味で（Number の）n が使われがちのようだ。

2. 最大の要素を見つける

   Math.max(...ary)

   • 古い資料だと Math.max.apply(null,ary)が提示されているが、ES6 以降はスプレッド演算子（…）が使えるので、特に apply は覚えなくても大丈夫そう。

   あるいは

   ary.reduce((v,e)=>v>e?v:e)

   • ただしこれらのコードは次の段階で行き詰まるので再考する必要があるだろう。

   • ついでに、伝統的な逐次型の書き方で求めるときにはこんなコードになる。

     var ch= -9999999       // 必ず負ける数を仮チャンピオンとして置いておく
     for(let i=0 ; i<n ; i++)
       if(ary[i]>ch) ch=ary[i]      // 下剋上 新しいチャンピオンが席につく
     // ループが終わると ch に、最大の値が入ってる筈

3. 「優勝者」を指定の席に移す

   • 「２番目に大きい」ものを見つけるコードは誰も書きたくないので、 代わりに、この先の走査対象の範囲から、その優勝者を取り除いて、

     この先もその走査範囲内での「最大の要素」を求める手順を続けられるようにする。

     これが「アルゴリズム」と呼ばれる物たちの、いわばミソになる箇所。

   • （今日はこの部分を書いていません。考えてみましょう）

   • でも少し書き足しておきます。
   • もとの配列の中に（大抵は先頭か末尾といった末端から順に広げて行って）優勝者 （すでに順位が決まったデータ）の席を設けるという考え方がある。

     • 配列を決裁済データの領域と未決データの領域に分割するということでもある。

     • 前述のコード（配列に対するメソッドを活用する）をそのまま使うとしたら、 未決データ領域に限定した部分配列を抽出してそれにメソッド適用する必要がある （Array.prototype.slice が使える）。

       たとえば優勝者を配列の先頭から配置するとしたら、以下のようなコードが必要になる。

       for(let i=0 ; i<n ; i++) {
         let mx=Math.max(...ary.slice(i,n))
         //...  このように対象となる範囲を順次狭めていく。
         // 優勝者データは ary[i] に置き（というのを前提としている）、
         // ループの次回ではそのデータは対象範囲から外れる
       }  

4. 交換、除去、追加、の書き方：

   • 配列の中で、添字 i の要素と添字 j の要素を交換するなら、

     let tmp=ary[i] ; ary[i]=ary[j] ; ary[j]=tmp
     // または
     [a[i],a[j]]=[a[j],a[i]]

   • 添字 i の要素を削除（して前に詰める）なら、

     ary.splice(i,1)

   • 他に、ary.push(data) などもチェックしておこう。

5. 最大の要素、の場所（添字）を見つける（2. について再考）

6. これを繰り返す

   考え方としては、

   • 回数を決めて
   • 条件を決めて

   いずれでも書ける。

バブルソート

• 大枠（伝統的な３項のfor文で書くなら）

  for(i=n; i>1 ; i--)       // 21.7.12 修正
    for(j=0 ; j<i ; j++)
      j番とj+1番を比較

• 前回示した時に１行目をfor(i=n-1; i>1 ; i--) と書いてたのは誤りのようです （訂正しました）。

• これを可視化したアニメーションのページ： このページは50行ほどのHTMLファイルですが、 データ部を覗くとJsのコードは30行程度、 読解をすすめることは可能だと思います。

  • function* という（アスタリスク付きの）定義は「ジェネレータ」と呼ばれるもので、 Webページ上でアニメーション的なコードを書くときには有用な概念です （ということに気がついている人はまだ少ないようなので解説記事があまり多くないが）。

その先へ

• マージソートについては、続編（日程は未定）で扱いたいと思います。
  • （できればそれまでに「しめじソート」は見ておいて下さい。）
• 様々な言語での実現例を置いておきますので、参考にして下さい。
  • ruby
  • python / Coconut
  • haskell
  • erlang / Elixir
• マージソートは来週あらためて(そのための準備とともに)とりあげたいと思います（JSでのコードもそこで提示します）。