• 日本語
    • English (英語)
Avinton JapanAvinton JapanAvinton JapanAvinton Japan
  • サービス
    • Avinton Data Platform
    • エッジAIカメラ
      • 自動車ナンバープレート自動認識システム
    • プライベートクラウド
    • AIサービス開発
    • AIカメラ/画像解析無料体験版
    • 見てわかる観光庁オープンデータ
  • 最新情報
    • ニュースリリース&イベント情報
    • 技術ブログ&インタビュー
  • アカデミー
    • Avintonアカデミー
    • Academy on Campus
    • Academy with Platform
  • 採用情報
    • Avintonジャパン 採用ページ
    • 求人一覧
    • よくある質問
    • 新卒採用
  • 企業情報
    • 会社概要
    • 代表からご挨拶
    • SDGsへの貢献
  • お問い合わせ
Engineering Basics - What is a sorting algorithm?

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

By James Cauchi | 技術解説, 技術ブログ&インタビュー | 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アカデミーで最新技術を学びませんか?

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

資格, 技術, 基本情報技術者

採用情報

採用情報

Categories

  • 相互学習
  • 採用
  • 社員インタビュー
  • 学習&資格取得
  • 技術解説
  • イベント告知
  • 学内説明会&講義
  • 産学連携
  • 就職活動
  • イベントレポート
  • その他
  • 技術ブログ&インタビュー
  • mainpage
  • New Graduates Interviews
  • 中途エンジニア
  • カテゴリーなし
  • ニュースリリース&イベント

Avinton SDGs

SDGsへの貢献

Search

タグ

AIカメラ AI時代の経営 AvintonAcademy on Campus AWS Docker DQN FINOLAB Git James Cauchi LPIC LPIC-2 PM&PMO Raspberry Pi Sound Analysis SSD イベントレポート インターン インフラ エッジコンピューティング エリクソン エンジニア クラウトネイティブ コンテナ技術 ディープラーニング データ生成 ファンダフルリレーマラソン モブワーク リスキリング リードエンジニア 中瀬幸子 企業説明会 勉強会 大学&専門学校 帰社日 強化学習、機械学習 技術ブログ 採用 掲載告知 未経験 深層学習 田中 研之輔 画像分類 社員紹介 第一級陸上特殊無線技士 観光データ
© 2023 Avinton | All Rights Reserved | プライバシーポリシー
  • サービス
    • Avinton Data Platform
    • エッジAIカメラ
      • 自動車ナンバープレート自動認識システム
    • プライベートクラウド
    • AIサービス開発
    • AIカメラ/画像解析無料体験版
    • 見てわかる観光庁オープンデータ
  • 最新情報
    • ニュースリリース&イベント情報
    • 技術ブログ&インタビュー
  • アカデミー
    • Avintonアカデミー
    • Academy on Campus
    • Academy with Platform
  • 採用情報
    • Avintonジャパン 採用ページ
    • 求人一覧
    • よくある質問
    • 新卒採用
  • 企業情報
    • 会社概要
    • 代表からご挨拶
    • SDGsへの貢献
  • お問い合わせ
  • 日本語
    • English (英語)
Avinton Japan