• 日本語
    • English (英語)
Avinton JapanAvinton JapanAvinton JapanAvinton Japan
  • サービス
    • Avinton Data Platform
    • エッジAIカメラ
    • AIサービス開発
    • AI画像解析 – 無償PoC
  • 最新情報
  • アカデミー
  • 採用情報
    • Avintonで働く魅力
    • 求人
    • よくある質問
  • 企業情報
    • 会社概要
    • 代表からご挨拶
    • CSR(企業の社会的責任)
  • お問い合わせ
Engineering Basics - What is a sorting algorithm?

基本情報技術者 ソートのアルゴリズムとは?

By Alexander Doms | blog, 勉強会 | Comments are Closed | 21 4月, 2020 | 2

Avintonでエンジニアをしている福丸です。
私は2019年の3月に未経験で転職してきて、約1年が経ちました。

様々なプロジェクトに参画する中でITの基礎知識が圧倒的に足りない・・!と思うことがよくありました。
例えば、
Webアプリの開発では

  • コンパイラって何?
  • アドレス参照って何?
  • 単体、結合、システム、運用テストの違いって何?

組み込みシステム開発では
そもそも2進数や16進数ってどんなものだっけ?
ASCII文字って何ビットでできているの?
CPUとかメモリとかROM、RAMって何?
ネットワーク分野では
TCP/IPって何?UDPと何が違うの?
CRCチェックって何?
公開鍵と暗号鍵って何?
ネットワークの構成図を見ても何が何だか・・

と、どのプロジェクトでもまずはわからないことだらけを解消していくのが大変でした。
これまではその時々に応じた分野に対して自分で勉強を積み重ねてきていたのですが、土台となる知識を広く蓄えておきたいと思うようになり、いまは基本情報技術者試験の勉強をしています。

基本情報技術者とは・・

基本情報技術者試験は、情報処理の促進に関する法律第29条第1項に基づき経済産業大臣が行う国家試験である情報処理技術者試験の一区分。対象者像は「高度 IT 人材となるために必要な基本的知識・技能をもち,実践的な活用能力を身に付けた者
(Wikipedia参照)

Engineering Basics - What is a sorting algorithm?

IT業界の中でも土台となる知識を試す試験のようです。
私のような未経験者は受けたほうが良いかもしれません。

どんな問題が出るのか?

以下の表は基本情報技術者試験を主宰しているIPA情報処理推進機構が提示している
試験要綱に記載されていたものです。
◎は必須回答問題であり、情報セキュリティとデータ構造及びアルゴリズムが該当しています。
◎がつくということはIT業界で必須の知識ということなのでしょう・・

基本情報技術者 ソートのアルゴリズムとは?今回のブログではこの必須項目のデータ構造及びアルゴリズムから、
“整列”のアルゴリズムを調べてみました。
“整列”とは、よくpythonなどの内部メソッドとして使用している“ソート”のことです。

ソートとは・・データをあるルールに基づいて整列すること

Engineering Basics - What is a sorting algorithm?

この”ソート”と記載されている内部処理には色々なアルゴリズムが存在しています。

基本情報技術者試験のシラバスには

  • バブルソート
  • 選択ソート
  • 挿入ソート
  • ヒープソート
  • クリックソート
  • マージソート
  • シェルソート

の7つのソートが用語例として記載されています。
今回はこの7つのソートについてどのように動いているのか、
また、その時間はどのくらいかかるのか調べてみました。

バブルソート

右から左にかけて隣の数字と交換して整列させる方法

基本情報技術者 ソートのアルゴリズムとは?

選択ソート

数列内の最小値を探索し、左端に設定する方法

Engineering Basics - What is a sorting algorithm?

挿入ソート

最初に左端をソート済に設定し、次の左端が右隣にあるソート済と比較交換していく方法

基本情報技術者 ソートのアルゴリズムとは?

ヒープソート

ヒープというデータ構造を利用して根の数字を取り出しヒープを再構築するのを繰り返す方法

Engineering Basics - What is a sorting algorithm?

マージソート

ソートする数列を半分の長さに分割していき、最小単位まで分割されたら比較しながらもとに戻していく方法

基本情報技術者 ソートのアルゴリズムとは?

クイックソート

ピボットという基準となる値をランダムに選択し、数列の先頭からピボットよりも大きいか小さいかで両側のグループに分割し、それを繰り返す方法

Engineering Basics - What is a sorting algorithm?

シェルソート

一定間隔毎に要素を取り出して挿入ソートを実行し、間隔を縮めながら1になるまで繰り返す方法

基本情報技術者 ソートのアルゴリズムとは?

それぞれのソート手法にかかる時間

計算時間の表記に用いている記号 O(オー)は、ランダウの記号(※)。

Engineering Basics - What is a sorting algorithm?

ランダウの記号 は、関数の極限における値の変化度合いに、おおよその評価を与えるための記法。

オーダー記法とは

例えば選択ソートの場合は
(1) 最小値を探索し、(2)左端の数値と交換しソート済とする
というアルゴリズムですが、それにかかる時間は
数列の数をn、(1)にかかる時間をTc、(2)にかかる時間を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アカデミーで最新技術を学びませんか?

採用に関してはこちら。未経験エンジニアも積極採用しています!

Avinton, Python, ソートのアルゴリズム, データサイエンス, データ解析, 勉強会

採用情報

採用情報

Search

タグ

2017 2018 AI Avinton Avinton Academy Avinton Japan Avintonジャパン DX HTML Linux Python Ruby Webエンジニア アビントン アビントンジャパン アヴィントン アヴィントンジャパン イベント インフラエンジニア エンジニア グローバル サーバーエンジニア データサイエンス データサイエンティスト データベース データ解析 ニュービジネス研究会 ネットワークエンジニア ビックデータ ベンチャー 勉強会 就活 就職活動 成長 技術インターン 採用 新規事業 横浜 機械学習 機械学習エンジニア 派遣 第二新卒 経営者交流会 英語 起業
© 2021 Avinton | All Rights Reserved | プライバシーポリシー
  • サービス
    • Avinton Data Platform
    • エッジAIカメラ
    • AIサービス開発
    • AI画像解析 – 無償PoC
  • 最新情報
  • アカデミー
  • 採用情報
    • Avintonで働く魅力
    • 求人
    • よくある質問
  • 企業情報
    • 会社概要
    • 代表からご挨拶
    • CSR(企業の社会的責任)
  • お問い合わせ
  • 日本語
    • English (英語)
Avinton Japan