Avintonでエンジニアをしている福丸です。
私は2019年の3月に未経験で転職してきて、約1年が経ちました。
様々なプロジェクトに参画する中でITの基礎知識が圧倒的に足りない・・！と思うことがよくありました。
例えば、
Webアプリの開発では
- コンパイラって何？
- アドレス参照って何？
- 単体、結合、システム、運用テストの違いって何？
組み込みシステム開発では
そもそも2進数や16進数ってどんなものだっけ？
ASCII文字って何ビットでできているの？
CPUとかメモリとかROM、RAMって何？
ネットワーク分野では
TCP/IPって何？UDPと何が違うの？
CRCチェックって何？
公開鍵と暗号鍵って何？
ネットワークの構成図を見ても何が何だか・・
と、どのプロジェクトでもまずはわからないことだらけを解消していくのが大変でした。
これまではその時々に応じた分野に対して自分で勉強を積み重ねてきていたのですが、土台となる知識を広く蓄えておきたいと思うようになり、いまは基本情報技術者試験の勉強をしています。
基本情報技術者とは・・
基本情報技術者試験は、情報処理の促進に関する法律第29条第1項に基づき経済産業大臣が行う国家試験である情報処理技術者試験の一区分。対象者像は「高度 IT 人材となるために必要な基本的知識・技能をもち，実践的な活用能力を身に付けた者
（Wikipedia参照）
IT業界の中でも土台となる知識を試す試験のようです。
私のような未経験者は受けたほうが良いかもしれません。
どんな問題が出るのか？
以下の表は基本情報技術者試験を主宰しているIPA情報処理推進機構が提示している
試験要綱に記載されていたものです。
◎は必須回答問題であり、情報セキュリティとデータ構造及びアルゴリズムが該当しています。
◎がつくということはIT業界で必須の知識ということなのでしょう・・
今回のブログではこの必須項目のデータ構造及びアルゴリズムから、
“整列”のアルゴリズムを調べてみました。
“整列”とは、よくpythonなどの内部メソッドとして使用している“ソート”のことです。
ソートとは・・データをあるルールに基づいて整列すること
この”ソート”と記載されている内部処理には色々なアルゴリズムが存在しています。
基本情報技術者試験のシラバスには
- バブルソート
- 選択ソート
- 挿入ソート
- ヒープソート
- クリックソート
- マージソート
- シェルソート
の７つのソートが用語例として記載されています。
今回はこの７つのソートについてどのように動いているのか、
また、その時間はどのくらいかかるのか調べてみました。
バブルソート
右から左にかけて隣の数字と交換して整列させる方法
選択ソート
数列内の最小値を探索し、左端に設定する方法
挿入ソート
最初に左端をソート済に設定し、次の左端が右隣にあるソート済と比較交換していく方法
ヒープソート
ヒープというデータ構造を利用して根の数字を取り出しヒープを再構築するのを繰り返す方法
マージソート
ソートする数列を半分の長さに分割していき、最小単位まで分割されたら比較しながらもとに戻していく方法
クイックソート
ピボットという基準となる値をランダムに選択し、数列の先頭からピボットよりも大きいか小さいかで両側のグループに分割し、それを繰り返す方法
シェルソート
一定間隔毎に要素を取り出して挿入ソートを実行し、間隔を縮めながら１になるまで繰り返す方法
それぞれのソート手法にかかる時間
計算時間の表記に用いている記号 O（オー）は、ランダウの記号（※）。
ランダウの記号 は、関数の極限における値の変化度合いに、おおよその評価を与えるための記法。
オーダー記法とは
例えば選択ソートの場合は
（１） 最小値を探索し、（２）左端の数値と交換しソート済とする
というアルゴリズムですが、それにかかる時間は
数列の数をn、（１）にかかる時間をTc、（２）にかかる時間をTsとすると
(nTc+Ts) + ((n-1)Tc+Ts) + ((n-2)Tc+Ts) + … +(2Tc+Ts) + (1Tc+Ts)
となります。（最後の(1Tc+Ts)が含まれているのは計算の便宜上の都合です）
数値を全部足すのは
1+2+3+⋯+n=(1/2)n(n+1)
ですので、
(1/2)n(n+1)*Tc + Ts*n
で表すことができます。
ここで、ソートの時間推移の最も大きな影響を与える要素は数列の数(n)なので
ざっくりと計算量を認識するため、
(1/2)n(n+1)*Tc + Ts*n = O(n^2)
としてざっくり認識できるようにすることをオーダー記法といいます。
まとめ
ソートにも色々な実装方法があることをこの勉強で初めて知りました。
今回は概要の理解だけだったので、余裕があれば自分で実装して時間を計ってみるのも良い勉強になるなと思いました！
Avintonはエンジニアの教育に力を入れています。Avintonアカデミーで最新技術を学びませんか？
採用に関してはこちら。未経験エンジニアも積極採用しています！
