問題一覧
1
バブルソートとは何か
隣接する要素を比較し必要に応じて交換することでソートする方法
2
バブルソートの利点は何か
・実装が簡単である ・追加メモリを使用しないため、メモリ効率が良い ・安定している
3
バブルソートの欠点は何か
・交換を多く行うため、大規模なデータでは非効率
4
バブルソートの計算量を答えよ
最適O(n) 既にソート 平均O(n^2) 最悪O(n^2)
5
選択ソートとは何か
線形探索を用いて、最小値を見つけ、ソートする方法
6
選択ソートのメリットは何か
・実装しやすい ・追加のメモリを使用しないため、メモリ効率がよい ・各for文で一回の交換しかしないため、書き込み操作のコストが高い場合に有利
7
選択ソートのデメリットとは何か
・安定性がない
8
選択ソートの計算量
最適O(n^2) ソート済み 平均O(n^2) 最悪O(n^2)
9
挿入ソートとは何か
配列を左側から順次処理することでソートする方法
10
挿入ソートのメリットとは何か
・実装が簡単である ・安定している 追加のメモリを使用しないため、メモリ効率が良い ・データが到着するたびにソートを行うことができるため、オンラインソートに適している
11
挿入ソートのデメリットとは何か
・大規模なデータに対しては計算時間が増加するため、非効率である
12
挿入ソートの計算量
最適O(n) 平均O(n^2) 最悪O(n^2)
13
ヒープソートとは何か
ヒープ構造を利用したソートである
14
ヒープソートのメリットとは何か
・追加のメモリを使用しないため、メモリ効率が良い。
15
ヒープソートのデメリットは何か
・実装が複雑である ・安定性がない
16
ヒープソートの時間計算量
最適O(n logn) 平均O(n logn) 最悪O(n logn)
17
マージソートとは何か
分割統治法に基づき、再帰的に配列を分割し、それらを統合することでソートする方法である
18
マージソートのメリット
・安定している ・全てO(n logn)でありデータの並びに依存しない ・外部ソートに適している
19
マージソートのデメリット
・追加メモリを使用するため、メモリ効率が悪い
20
マージソートの計算量
最適O(n logn) 平均O(n logn) 最悪O(n logn)
21
クイックソートとは何か
分割統治法の一種で基準となる数(ピボット)を決めそれ以上とそれ以下に分けてソートする方法
22
クイックソートのメリット
・追加のメモリを使用しないためメモリ効率が良い ・分割統治法を用いて再帰的に処理するため、アルゴリズムがシンプル
23
クイックソートの欠点
・最悪の場合O(n^2)になる ・安定性がない
24
クイックソートの計算量
最適O(n logn) 平均O(n logn) 最悪O(n^2)
25
バケットソートとは何か
データをバケット(器)に分割し、各バケットごとに別のアルゴリズムを適用するソート方法
26
バケットソートのメリット
・1回の線形探索で済むため、O(n)である ・外部ソートに適している
27
バケットソートの欠点
・追加メモリを使用するためメモリ効率が悪い ・安定性がない
28
バケットソートの計算量
最適O(n) 平均O(n+k) 最悪O(n^2)
29
安定しているソートを3つ答えよ
・バブルソート ・挿入ソート ・マージソート