From: リスキルテクノロジー 松田航
新宿本校にて、、、
プログラムでは必ずデータを扱いますが...
データ量が増えれば増えるほど、
並べ替えしておいた方が扱いやすくなります。
今回は並べ替えのアルゴリズムである、
「ソート」
についてお話ししましょう。
ネット検索にも使われている
インターネットのウェブサイトの数は
2014年に10億件を突破しました。
Yahoo!やGoogleなどの
検索サイトからサイト検索をするときに、
いちいち10億件のサイトを
検索していたのでは時間がかかって仕方ないですよね。
このため、
インターネットで何かを検索すると
必ず訪問者の多いサイトが上位に表示されます。
これはサーチエンジンが
有効な情報を持っているサイト順に並べ替えて、
訪問者の多いサイトを上位に表示しているからです。
データというのは
量が増えれば増えるほど、
きちんと並べ替えられている方が管理しやすいですよね。
この並べ替えのことを...
「ソート」
...と言い、非常によく使われるアルゴリズムです。
ソートする時には
以前にお伝えした「配列」が必要で、
配列にデータを入れてからソートするのが一般的です。
値の小さい順にソートすることを「昇順」、
値の大きい順にソートすることを「降順」と言います。
どちらの順でソートするかはケースバイケースですね。
それでは、
代表的なソートアルゴリズムを
いくつかご紹介しましょう。
バブルソート
～単純なソートアルゴリズム～
ソートのアルゴリズムで
もっとも単純なもののひとつがこの「バブルソート」です。
バブルソートとは、
隣り合ったデータの値を比べて、
単純に並べ替えていくというものです。
イメージを見てみましょう。
1、4、3、2と並んだ
4つの値が入っている配列があります。
これを左から順に...
1番目と2番目のデータを比べ、
1番目と3番目のデータを比べ、
1番目と4番目のデータを比べ...と、
単純に順序だてて比べていって、
左側の値が大きければ位置を交換する仕組みです。
1番目の値を比べ終わったら、
2番目のデータを元に比べてゆきます。
数字が上に上がっていく様子が、
泡が水の中で上に浮いてくる様子に似ていることから
バブルソートと言います。
ソートのアルゴリズムの中では単純で、
少ないデータを扱う時には問題ありません。
ですが、
データ量が増えれば増えるほど、
バブルソートでは処理に時間がかかってしまうのです。
例えば、全ての値を
比べ終わるのに必要な処理回数は最大...
1,000個の配列だと49万9500回、
10,000個の配列だと4999万5000回かかります。
ちょっとかかりすぎですよね。
そこで、バブルソートよりも
高速なアルゴリズムが必要になってきます。
クイックソート
～文字通り高速にソートできるアルゴリズム～
バブルソートよりも処理の速いアルゴリズムで、
代表的なものに「クイックソート」があります。
簡単に言うと、
データの中から基準となる値を決めて、
それより大きいグループと小さいグループに分けてから、
ソートしてゆくアルゴリズムです。
ちょっとややこしいので、
今はわからなくても大丈夫です。
クイックソートのイメージだけ掴んでくださいね。
それでは、イメージを見てみましょう。
3、4、5、2、1と並んだ
5つの値が入っている配列があります。
一番左にある3を
とりあえず基準値として、
3よりも大きいグループと小さいグループに分けます。
このとき、3の位置はもう確定しています。
ちょうど大きいグループと小さいグループの間ですね。
そして今度は、
それぞれのグループから基準値を決めて、
その基準値と
グループの中のほかの数を比べて、
相手の値が小さければ並べ替えます。
最終的に比較するものがなければ、
そこでソートが終わりです。
ちなみに、この5つの値のソートを
バブルソートですると処理回数が10回かかります。
クイックソートは名前のとおり、
素早くソートできるアルゴリズムなのです。
適切なアルゴリズムを使って効率性を上げよう
バブルソートやクイックソート以外にも、
さまざまなソートのアルゴリズムがありますが...
それらは必要に応じて覚えてゆけばいいでしょう。
クイックソートは
実用的で処理の早いアルゴリズムとして
多くのシステムで使われますが、
データ件数によっては
別のアルゴリズムの方が速いケースもあります。
扱うデータ件数によって
アルゴリズムを使い分けると処理速度が上がるのです。
アルゴリズムはあくまで
効率的に処理を行う手順です。
1つの手順にこだわることなく、
常に適切なアルゴリズムを使うことができれば、
効率の良いプログラムを組めるエンジニアになれます。
柔軟な考え方のできるエンジニアになってください。
リスキルテクノロジー
松田
PS
柔軟な発想を持つには、
基本から応用まで、幅広いノウハウが必要です。
基本的なアルゴリズムを始め
現場で使える応用力を身に着けたいなら資料請求を。
コメント