ソートのアルゴリズムについて 【情報処理安全確保支援士】

このエントリーをはてなブックマークに追加
Pocket

整列（ソート）に使ったアルゴリズム解説

クイックソート

参考サイト：https://paiza.jp/works/mondai/sort_efficient/sort_efficient__quick

クイックソートは、ピボットと呼ばれる値を1つ選び、それを基準としてデータ列を「ピボット未満の要素からなるデータ列」と「ピボット以上の要素からなるデータ列」に二分することを再帰的に行うアルゴリズム。

問題を小さな問題に分割して解くことを繰り返すことによって、元の問題となる答えを得る手法である「分割統治法」に基づいており、実用的なソートアルゴリズムの中で最も高速であるとされている。

ピボット選びの種類

  1. データ列の先頭をとる
  2. データ列の末尾をとる
  3. データ列からランダムにとる
  4. データ列からランダムに２つとり、その中央値をとる

ピボット選択後の動き

  1. ピボット選択
  2. データ列の先頭からデータを１つずつ確認し、ピボット未満のデータをデータ列の先頭に集める
  3. ピボット列より左側がピボット未満、右側がピボット以上となるようにピボットを移動し、データ列を２分する
  4. 分割された２つのデータ列に対して再び同じ操作を繰り替える

挿入ソート

参考サイト：https://paiza.jp/works/mondai/sort_naive/sort_naive__insertion

挿入ソートは、データ列を「整列済み」と「未整列」の2つに分け、「未整列な配列」からデータを1つ取り出し、「整列済み配列」の適切な位置に挿入することを繰り返す手法

手持ちのトランプを並ぶ替える際によく使う手法

バブルソート

参考サイト：https://paiza.jp/works/mondai/sort_naive/sort_naive__bubble

バブルソートは、データ列の隣り合う要素を比較し交換することを繰り返すことによりデータ列をソートする手法

バブルソートの基本方針

左から右へ昇順ソートを考える

  1. 左の要素と比較する
  2. 左のほうが大きければ交換する

ヒープソート

ヒープソート (heap sort) とはリストの並べ替えを二分ヒープ木を用いて行うソートのアルゴリズム

参考サイト：https://medium-company.com/%E3%83%92%E3%83%BC%E3%83%97%E3%82%BD%E3%83%BC%E3%83%88/

※ヒープ（英: heap）とは、「子要素は親要素より常に大きいか等しい（または常に小さいか等しい）」という制約を持つ木構造の事

ヒープソートの４つの手順

  1. 未整列の配列からヒープの性質を持つ木構造を作成する
  2. 木構造の作成が完了したら、根（ルート）の値を整列済みとする
  3. 根（ルート）の値を除いて、再度ヒープの性質を持つ木構造を作成する
  4. すべてのデータが整列済みになるまで、２～３を繰り返す

過去問：https://www.sc-siken.com/kakomon/05_aki/am1_3.html

情報処理安全確保支援士情報処理安全確保支援士

Posted by wpmaster