基本的なアルゴリズムを理解してプログラミングしよう：無償ソフトで技術計算しよう【プログラミング処理編】（2）（2/2 ページ）

アルゴリズムとは、問題を解くための手順を定式化して表現したもの。プログラミングにおける基本的なアルゴリズムには、探索やソート、マージなどがある。

[伊藤孝宏，MONOist]

ソート

　続いて、初歩的なソートのアルゴリズムを説明します。例えば、昇順に並べ替えるには、最初の要素をminとして、次の要素がminより小さい場合、minを次の要素で置き換えて、最初の要素と次の要素の位置を置き換えるということを繰り返します。

　「ex317.m」は、forループを用いたソートプログラムです。始めに、「randperm」コマンドで、1〜1000までの整数がランダムに並んだ配列を生成します。これを変数aに格納し、この後のFreeMatのソートコマンド用に変数bにも格納しておきます。

　ここで、k番目までは昇順に並んでいるとします。s=kとして、kをsにも格納します。k番目の要素を最小値minとして、k+1番目から最後の要素まで、minより小さいかを比較します。もし、n番目の要素がminよりも小さい場合、min=a(n)として、minを置き換えます。また、s=nとして、k番目の要素位置sをnと置き換えます。最後に、t=a(k); a(k)=a(s); a(s)=t;として、k番目の要素と、最小であったn番目の要素を置き換えます。kを最初の要素番号1から最後の要素の手前まで変えながら、以上の操作を繰り返していくと、要素は昇順に並びます。

　また、コマンドticとtocをforループの前後に置いて、計算に要した時間を計測しています。

clear;
a=randperm(1000);b=a;
tic;
for k=1:length(a)-1
    min=a(k);
    s=k;
    for n=k+1:length(a)
        if(a(n)<min)
            min=a(n);s=n;
        end
    end
    t=a(k);a(k)=a(s);a(s)=t;
end
time1=toc;
disp(['The calculation needs ',num2str(time1),'second']);

ex317.m

＞＞「ex317.m」ダウンロード

　FreeMatでは「sort」コマンドで、昇順に並べ替えることができます。sortコマンドを使って、ex317.mのforループを置き換えたものが下記です。とても簡単です。

tic;
sort(b);
time2=toc;
disp(['The calculation needs ',num2str(time2),'second']);

　双方の計算効率を調べてみましょう。ex317.mに上記のプログラムを付け加えて動作させると、例えば下記のような結果が得られます。

The calculation needs 5.238second
The calculation needs 0.001second

　forループによる処理では、5.238秒で、sortによる処理では、0.001秒であることが分かります。先ほどの探索アルゴリズムでの比較よりも大きな差が生じているのは、2重のループを使っているためです。先のアルゴリズムは、初歩的なアルゴリズムで効率があまり良くないとはいえ、sortコマンドを使った方が、簡単で計算が速いことが分かると思います。なお、これは数値をランダムに並べたものから該当の数値を見つけ出すプログラムであり、ハードウェアの処理能力の違いなども考えられるため、同様の計算を行っても、同じ結果にはなりませんのであらかじめご了承ください。

　ちなみに、sortコマンドは、文字列をソートすることも可能です。例えば、sort('How much wood a woodstock chuck?')とすると、?Haccccddhhkkmoooooostuuwwwと、特殊記号、大文字アルファベット、小文字アルファベットの順に並び変わります。

　セル配列のソートも同様です。例えば、sort({'abc','def','ghi','jkl'},2,'descend')とすると、[jkl] [ghi] [def] [abc]と、文字列がアルファベット順に降順に並び変わっています。

　マージは配列の結合とソートの組み合わせで実現できます。例えば、ab=randperm(1000); a=ab(1:500); b=ab(501:1000);とすると、1〜1000までの整数がランダムに並んだ2つの配列aとbが出来上がります。plot(a,'o',b,'*')とすると、図1のように、○で示すaの要素と＊で示すbの要素とがランダムに並んでいることが分かります。

図1　配列aとbの要素

　次に、ab=[a,b];として、2つの配列をつなげ、ab=sort(ab);とすると、要素が昇順に並び変わった配列abが出来上がります。plot(ab,'o')とすると、図2のように、要素が昇順に並んでいることが分かります。

図2　配列abの要素

◇

　次回は、「再帰アルゴリズム」について説明します。

参考文献

• 「MATLABハンドブック」小林一行著、秀和システム刊
• 「はじめてのFreeMat」赤間世紀著、工学社刊

無償ソフトで技術計算しよう

無償ソフトで技術計算しよう

無償の工学計算ソフトでも、かなり高度な計算ができる！

筆者紹介

伊藤孝宏（いとう・たかひろ）

1960年生。小型モーターメーカーのエンジニア。博士（工学）。専門は流体工学、音・振動工学。現在は、LabVIEWを使って、音不良の計測・診断ソフト、特性自動検査装置などの開発を行っている。