2026/07/25 今日のテーマ 整列アルゴリズム
シェルソート
マージソート
ヒープソート
クイックソート
バブルソート(交換ソート)
選択ソート
挿入ソート
についてまとめてみたので、参考にしてね。と自分に語っている。@o@//
シェルソート
シェルソートのしくみ
シェルソート（Shell Sort）は、挿入ソートを「間隔（ギャップ）」を使って拡張した高速ソートアルゴリズムである。 配列を部分的に整列させながら、徐々にギャップを縮めていくことで、最終的にほぼ整列済みの状態を作り、挿入ソートの弱点を克服する。
1. 基本アイデア
挿入ソートは「ほぼ整列している配列」に対して非常に高速である。 そこでシェルソートでは、配列をいきなり完全に整列させるのではなく、 大きな間隔で要素を比較 → 少しずつ間隔を縮める という手順を踏む。
これにより、遠く離れた要素を先に整列させ、 最終段階ではほぼ整列済みの状態で挿入ソートが働くため高速化が起こる。
2. ギャップ（間隔）の定義
シェルソートでは、まず配列長 \(N\) に対してギャップ \(g\) を設定する。
一般的な初期ギャップは \[ g = \left\lfloor \frac{N}{2} \right\rfloor \] である。
その後、ギャップを \[ g \leftarrow \left\lfloor \frac{g}{2} \right\rfloor \] のように縮めていく。
ギャップが 1 になったとき、通常の挿入ソートと同じ処理になる。
3. ギャップごとの挿入ソート
ギャップ \(g\) が決まったら、配列の要素を \[ A[i],\ A[i+g],\ A[i+2g],\ \dots \] という「ギャップごとの部分列」として扱い、 各部分列に対して挿入ソートを行う。
これにより、配列全体が「粗く整列された状態」になる。
4. ギャップを縮める理由
ギャップを縮めることで、 遠く離れた要素の位置関係を先に改善し、 最終的にギャップが 1 になったときには、 配列はほぼ整列済みとなる。
挿入ソートは「ほぼ整列している配列」に対して高速であるため、 この段階で非常に効率よく整列が完了する。
5. シェルソートの計算量
シェルソートの計算量はギャップの選び方によって変わる。
- 最悪計算量：\(O(N^2)\)
- 良いギャップ列（Knuth など）を使うと：\(O(N^{3/2})\)
- 最適ギャップ列では：\(O(N \log^2 N)\)
実用上は非常に高速で、 クイックソートよりも安定した性能を示す場合もある。
6. シェルソートの流れ（まとめ）
\[ \boxed{ \begin{aligned} 1.\ &\text{初期ギャップ } g = \lfloor N/2 \rfloor \\ 2.\ &\text{ギャップごとに挿入ソートを実行} \\ 3.\ &g \leftarrow \lfloor g/2 \rfloor \\ 4.\ &g = 1 \text{ になったら通常の挿入ソート} \\ 5.\ &\text{配列が完全に整列する} \end{aligned} } \]
この「ギャップを縮めながら整列する」という構造が、 シェルソートの本質である。
マージソート
マージソートのしくみ
マージソート（Merge Sort）は、配列を再帰的に「分割」し、 最後に「マージ（結合）」することで整列させるソートアルゴリズムである。 常に 計算量 \(O(N \log N)\) を保証する、非常に安定した高速ソートである。
1. 基本アイデア
マージソートは、配列をいきなり整列させるのではなく、 分割 → 整列 → 結合（マージ） の手順を踏む。
配列を小さく分割していくことで、 各部分配列は簡単に整列できるようになり、 最後にそれらを「順序を保ちながら結合」することで全体が整列する。
2. 分割（Divide）
配列長 \(N\) の配列を中央で分割する。
\[ A = [a_1, a_2, \dots, a_N] \] \[ A_{\text{left}} = A[1 : N/2],\quad A_{\text{right}} = A[N/2+1 : N] \]
この分割を再帰的に繰り返し、 最終的に配列が長さ 1 になるまで細分化する。
3. マージ（Merge）
長さ 1 の配列はすでに整列済みであるため、 2 つの整列済み配列を次のルールで結合する。
\[ \text{左の先頭} \le \text{右の先頭} \] なら左を取り出し、 そうでなければ右を取り出す。
この操作を繰り返すことで、 2 つの整列済み配列を「安定に」結合できる。
4. マージソートの再帰構造
マージソートは次の再帰式で表される。
\[ T(N) = 2T(N/2) + O(N) \]
これは「分割が 2 回」「マージが \(O(N)\)」であることを意味する。
この再帰式を解くと、
\[ T(N) = O(N \log N) \]
となり、最悪でも高速であることが保証される。
5. マージソートの計算量
- 最良計算量：\(O(N \log N)\)
- 平均計算量：\(O(N \log N)\)
- 最悪計算量：\(O(N \log N)\)
- 追加メモリ：\(O(N)\)
常に高速であり、安定ソートである点が大きな特徴である。
6. マージソートの流れ（まとめ）
\[ \boxed{ \begin{aligned} 1.\ &\text{配列を中央で分割する} \\ 2.\ &\text{分割を再帰的に繰り返す} \\ 3.\ &\text{長さ 1 になったら整列済みとみなす} \\ 4.\ &\text{左右の配列をマージして結合する} \\ 5.\ &\text{すべての階層でマージを行い整列完了} \end{aligned} } \]
この「分割してから結合する」という構造が、 マージソートの本質である。
ヒープソート
ヒープソートのしくみ
ヒープソート（Heap Sort）は、二分ヒープ（Binary Heap）というデータ構造を利用して整列を行うソートアルゴリズムである。 ヒープは「親 ≥ 子（最大ヒープ）」または「親 ≤ 子（最小ヒープ）」という性質を持つ完全二分木であり、 この構造を使うことで常に 計算量 \(O(N \log N)\) を達成する。
1. 基本アイデア
ヒープソートは次の 2 ステップで構成される。
① 配列をヒープ構造にする（ヒープ化）
② 最大値（または最小値）を取り出して末尾と交換し、ヒープを再調整する
この操作を繰り返すことで、配列が完全に整列される。
2. ヒープ（Heap）とは？
ヒープは次の性質を持つ完全二分木である。
\[ \text{最大ヒープ： } A[\text{parent}] \ge A[\text{child}] \] \[ \text{最小ヒープ： } A[\text{parent}] \le A[\text{child}] \] \]
ヒープは配列で効率的に表現でき、 インデックスを使って親子関係を次のように管理する。
\[ \text{親} = \left\lfloor \frac{i}{2} \right\rfloor,\quad \text{左子} = 2i,\quad \text{右子} = 2i + 1 \]
3. ヒープ化（Build Heap）
まず配列全体を最大ヒープに変換する。
\[ \text{for } i = \lfloor N/2 \rfloor \text{ down to } 1: \quad \text{heapify}(i) \]
これにより、配列の先頭（根）は常に最大値となる。
4. 最大値を取り出して整列する
最大ヒープでは、根（配列の先頭）が最大値である。
\[ \text{swap}(A[1], A[N]) \]
最大値を配列末尾に移動したら、 残りの部分に対して再びヒープ化（heapify）を行う。
この操作を繰り返すことで、 配列末尾から順に最大値が確定していく。
5. 計算量の解析
ヒープソートの計算量は次のように求められる。
ヒープ化（Build Heap）： \[ O(N) \] 各ステップで最大値を取り出し、heapify を行う： \[ N \times O(\log N) \]
したがって全体の計算量は
\[ O(N) + O(N \log N) = O(N \log N) \]
最悪でも高速である点が大きな特徴である。
6. ヒープソートの計算量
- 最良計算量：\(O(N \log N)\)
- 平均計算量：\(O(N \log N)\)
- 最悪計算量：\(O(N \log N)\)
- 追加メモリ：\(O(1)\)（in-place）
クイックソートのように最悪ケースが悪化することがなく、 安定した性能を持つ。
7. ヒープソートの流れ（まとめ）
\[ \boxed{ \begin{aligned} 1.\ &\text{配列を最大ヒープに変換する} \\ 2.\ &\text{根（最大値）を末尾と交換する} \\ 3.\ &\text{残りの部分を再ヒープ化する} \\ 4.\ &\text{これを配列が尽きるまで繰り返す} \\ 5.\ &\text{末尾から順に整列が完成する} \end{aligned} } \]
この「ヒープ構造を使って最大値を効率的に取り出す」という仕組みが、 ヒープソートの本質である。
クイックソート
クイックソートのしくみ
クイックソート（Quick Sort）は、「分割統治法（Divide and Conquer）」を用いた高速ソートアルゴリズムである。 配列から基準値（ピボット）を選び、要素を ピボットより小さいグループ と 大きいグループ に分割し、 それぞれを再帰的に整列することで高速なソートを実現する。
1. 基本アイデア
クイックソートは次の 3 ステップで構成される。
① ピボット（基準値）を選ぶ
② ピボットより小さい要素と大きい要素に分割する（パーティション）
③ 分割された配列を再帰的にソートする
この「分割 → 再帰」の構造が高速性の源である。
2. ピボット（Pivot）の選び方
ピボットは配列の中から 1 つ選ぶ値である。 一般的な選び方は次の通り。
- 先頭の要素
- 末尾の要素
- 中央の要素
- ランダムに選ぶ（最悪ケースを避けやすい）
ピボットの選び方は計算量に大きく影響する。
3. パーティション（Partition）
ピボットを基準に、配列を次のように分割する。
\[ \text{Left} = \{ x \mid x < \text{pivot} \} \] \[ \text{Right} = \{ x \mid x > \text{pivot} \} \] \]
この操作により、ピボットの位置は「最終的な正しい位置」に確定する。
4. 再帰的ソート
分割された Left と Right に対して、同じ操作（ピボット選択 → 分割）を再帰的に行う。
\[ T(N) = T(L) + T(R) + O(N) \]
ここで \(L\) と \(R\) は左右の配列の長さである。
平均的には左右が均等に分割されるため、
\[ T(N) = O(N \log N) \] \]
となり、非常に高速なソートとなる。
5. クイックソートの計算量
- 最良計算量：\(O(N \log N)\)
- 平均計算量：\(O(N \log N)\)
- 最悪計算量：\(O(N^2)\)
最悪ケースは「ピボットが常に最小（または最大）」になる場合である。 ランダムピボットを使うことで最悪ケースを避けやすくなる。
6. クイックソートの流れ（まとめ）
\[ \boxed{ \begin{aligned} 1.\ &\text{ピボットを選ぶ} \\ 2.\ &\text{ピボットより小さい・大きいで分割する} \\ 3.\ &\text{ピボットの位置が確定する} \\ 4.\ &\text{左右の配列を再帰的にソートする} \\ 5.\ &\text{すべての再帰が終わると整列完了} \end{aligned} } \]
この「分割してから再帰的に整列する」という構造が、 クイックソートの本質である。
バブルソート（交換ソート)
バブルソート(交換ソート)のしくみ
バブルソート（Bubble Sort）は、隣り合う要素を比較して交換することで整列させる、もっとも基本的なソートアルゴリズムである。 要素が「泡（bubble）」のように上へ浮かび上がるイメージからこの名前が付いている。
1. 基本アイデア
バブルソートは次の操作を繰り返す。
① 隣り合う要素を比較する
② 順序が逆なら交換する
③ 配列の末尾に最大値が確定する
この操作を配列の長さ分だけ繰り返すことで、 すべての要素が整列される。
2. 隣接交換のしくみ
バブルソートでは、インデックス \(i\) と \(i+1\) の要素を比較する。
\[ \text{if } A[i] > A[i+1] \text{ then swap} \]
これにより、1 回の走査で「最大値」が配列の末尾へ移動する。
3. 内側ループと外側ループ
バブルソートは二重ループで構成される。
内側ループ：隣接要素を比較して交換 外側ループ：配列全体を何度も走査する
\[ \text{for } j = 1 \text{ to } N: \quad \text{for } i = 1 \text{ to } N-j: \quad \text{swap if needed} \]
外側ループの回数が増えるごとに、末尾から順に値が確定していく。
4. 改良バブルソート（早期終了）
交換が一度も起きなかった場合、配列はすでに整列済みである。
\[ \text{if no swap in a pass} \Rightarrow \text{break} \]
この改良により、最良計算量は \(O(N)\) になる。
5. バブルソートの計算量
- 最良計算量：\(O(N)\)（交換が一度も起きない場合）
- 平均計算量：\(O(N^2)\)
- 最悪計算量：\(O(N^2)\)
- 追加メモリ：\(O(1)\)
計算量は大きいが、アルゴリズムの理解や教育用途でよく使われる。
6. バブルソートの流れ（まとめ）
\[ \boxed{ \begin{aligned} 1.\ &\text{隣り合う要素を比較する} \\ 2.\ &\text{順序が逆なら交換する} \\ 3.\ &\text{末尾に最大値が確定する} \\ 4.\ &\text{これを配列の長さ分繰り返す} \\ 5.\ &\text{交換がなければ早期終了する} \end{aligned} } \]
この「隣接交換を繰り返して値を浮かび上がらせる」という構造が、 バブルソートの本質である。
選択ソート
選択ソートのしくみ
選択ソート（Selection Sort）は、配列の中から 最小値（または最大値）を選び出し、 それを先頭へ移動する操作を繰り返すソートアルゴリズムである。 交換回数が少なく、構造が非常にシンプルで理解しやすい。
1. 基本アイデア
選択ソートは次の 3 ステップで構成される。
① 未整列部分から最小値を探す
② 最小値を先頭の位置と交換する
③ 未整列部分を縮めて繰り返す
この操作を配列の長さ分だけ繰り返すことで整列が完了する。
2. 最小値の探索
インデックス \(i\) を「現在の先頭」とし、 そこから右側の要素を走査して最小値を探す。
\[ \text{minIndex} = i \] \[ \text{for } j = i+1 \text{ to } N: \quad \text{if } A[j] < A[\text{minIndex}] \text{ then minIndex = j} \]
この操作により、未整列部分の最小値が確定する。
3. 最小値を先頭と交換する
見つけた最小値を先頭の位置 \(i\) と交換する。
\[ \text{swap}(A[i], A[\text{minIndex}]) \]
これにより、配列の左側から順に値が確定していく。
4. 選択ソートの特徴
- 交換回数が最大でも \(N-1\) と少ない
- 比較回数は常に多い（改善しにくい）
- 安定ソートではない（同じ値の順序が変わることがある）
- 構造が非常にシンプルで教育用途に向く
5. 選択ソートの計算量
選択ソートは常に同じ比較回数を必要とする。
\[ \text{比較回数} = \frac{N(N-1)}{2} \]
したがって計算量は
\[ O(N^2) \]
- 最良計算量：\(O(N^2)\)
- 平均計算量：\(O(N^2)\)
- 最悪計算量：\(O(N^2)\)
- 追加メモリ：\(O(1)\)
バブルソートや挿入ソートと同じく、基本ソートの代表例である。
6. 選択ソートの流れ（まとめ）
\[ \boxed{ \begin{aligned} 1.\ &\text{未整列部分から最小値を探す} \\ 2.\ &\text{最小値を先頭と交換する} \\ 3.\ &\text{未整列部分を縮める} \\ 4.\ &\text{これを配列の長さ分繰り返す} \\ 5.\ &\text{左側から順に整列が確定する} \end{aligned} } \]
この「最小値を選んで先頭へ送る」という構造が、 選択ソートの本質である。
挿入ソート
挿入ソートのしくみ
挿入ソート（Insertion Sort）は、配列を左から順に見ていき、 現在の要素を「適切な位置」に挿入することで整列させるソートアルゴリズムである。 「手札のカードを並べる」ような自然な操作で理解しやすい。
1. 基本アイデア
挿入ソートは次の 3 ステップで構成される。
① 左側は常に整列済みとみなす
② 現在の要素を取り出す
③ 左側の整列済み部分に挿入する
これを配列の左から右へ順に繰り返すことで整列が完了する。
2. 整列済み部分への挿入
インデックス \(i\) の要素を「挿入対象」とし、 左側の整列済み部分（0〜\(i-1\)）を逆向きに走査して適切な位置を探す。
\[ \text{key} = A[i] \] \[ \text{while } j \ge 0 \text{ and } A[j] > \text{key}: \quad A[j+1] = A[j] \quad j = j - 1 \] \[ A[j+1] = \text{key} \]
この操作により、左側は常に整列済みの状態を保つ。
3. 挿入ソートの特徴
- ほぼ整列済みの配列に対して非常に高速
- 安定ソート（同じ値の順序が保持される）
- 実装が簡単で理解しやすい
- 小規模データに強い
4. 挿入ソートの計算量
挿入ソートの計算量は配列の状態に大きく依存する。
- 最良計算量：\(O(N)\)（すでに整列済みの場合）
- 平均計算量：\(O(N^2)\)
- 最悪計算量：\(O(N^2)\)
- 追加メモリ：\(O(1)\)
「ほぼ整列済み」の場合に強い点が大きな特徴である。
5. 挿入ソートの流れ（まとめ）
\[ \boxed{ \begin{aligned} 1.\ &\text{左側は常に整列済みとみなす} \\ 2.\ &\text{現在の要素を取り出す} \\ 3.\ &\text{左側の整列済み部分を逆向きに走査する} \\ 4.\ &\text{適切な位置に挿入する} \\ 5.\ &\text{これを配列の終わりまで繰り返す} \end{aligned} } \]
この「整列済み部分へ挿入する」という構造が、 挿入ソートの本質である。
ソートアルゴリズムまとめ
ソートアルゴリズム図解まとめ
ここでは、代表的なソートアルゴリズムの動きを 矢印・ブロック図を使って直感的に理解できるようにまとめる。
1. バブルソート（Bubble Sort）図解
隣り合う要素を比較して、順序が逆なら交換する。
初期状態： [ 5, 3, 4, 1 ] 1回目の走査： 5 ⇄ 3 → [ 3, 5, 4, 1 ] 5 ⇄ 4 → [ 3, 4, 5, 1 ] 5 ⇄ 1 → [ 3, 4, 1, 5 ] ← 最大値が末尾へ 2回目の走査： 3 ⇄ 4 → [ 3, 4, 1, 5 ] 4 ⇄ 1 → [ 3, 1, 4, 5 ] 3回目の走査： 3 ⇄ 1 → [ 1, 3, 4, 5 ]
「最大値が泡のように末尾へ浮かび上がる」イメージ。
2. 選択ソート（Selection Sort）図解
未整列部分から最小値を選び、先頭へ送る。
初期状態： [ 5, 3, 4, 1 ] ステップ1：最小値を探す 未整列部分：5, 3, 4, 1 最小値 = 1 → 先頭と交換 [ 1, 3, 4, 5 ] ステップ2：次の未整列部分 未整列部分：3, 4, 5 最小値 = 3 → 先頭（位置1）と交換（変化なし） [ 1, 3, 4, 5 ]
「最小値を選んで左側に並べていく」イメージ。
3. 挿入ソート（Insertion Sort）図解
左側は常に整列済みとみなし、そこへ挿入していく。
初期状態： [ 5, 3, 4, 1 ] ステップ1： 整列済み：[ 5 ] 挿入対象：3 → 5の前に挿入 [ 3, 5, 4, 1 ] ステップ2： 整列済み：[ 3, 5 ] 挿入対象：4 → 5の前に挿入 [ 3, 4, 5, 1 ] ステップ3： 整列済み：[ 3, 4, 5 ] 挿入対象：1 → 3の前に挿入 [ 1, 3, 4, 5 ]
「手札のカードを並べる」イメージ。
4. マージソート（Merge Sort）図解
分割してから結合するソート。
初期状態： [ 8, 3, 5, 1, 9, 2 ] 分割： [ 8, 3, 5 ] [ 1, 9, 2 ] [ 8 ] [ 3, 5 ] [ 1 ] [ 9, 2 ] [ 3 ] [ 5 ] [ 9 ] [ 2 ] マージ： [ 3, 5 ] [ 2, 9 ] [ 3, 5, 8 ] [ 1, 2, 9 ] 最終マージ： [ 1, 2, 3, 5, 8, 9 ]
「小さく分けてから、順序を保ってくっつける」イメージ。
5. クイックソート（Quick Sort）図解
ピボットを基準に分割していくソート。
初期状態： [ 8, 3, 5, 1, 9, 2 ] ピボット = 5 とする 分割： 左（小さい）: [ 3, 1, 2 ] 右（大きい）: [ 8, 9 ] 再帰的にソート： 左 → [ 1, 2, 3 ] 右 → [ 8, 9 ] 結合： [ 1, 2, 3, 5, 8, 9 ]
「基準値で左右に分けて、分割統治する」イメージ。
6. ヒープソート（Heap Sort）図解
ヒープ構造を使って最大値を取り出すソート。
初期状態：
[ 5, 3, 8, 1, 2 ]
最大ヒープ化：
8
/ \
3 5
/ \
1 2
配列表現：
[ 8, 3, 5, 1, 2 ]
最大値 8 を末尾と交換：
[ 2, 3, 5, 1, 8 ]
残りを再ヒープ化 → 最大値を末尾へ
[ 1, 2, 3, 5, 8 ]
「木構造から最大値を順に取り出す」イメージ。
7. シェルソート（Shell Sort）図解
ギャップを使って遠くの要素から整列していくソート。
初期状態： [ 8, 3, 5, 1, 9, 2 ] ギャップ g = 3 とする 部分列1： 8 → 1 (位置0, 3) 部分列2： 3 → 9 (位置1, 4) 部分列3： 5 → 2 (位置2, 5) 粗く整列： [ 1, 3, 2, 8, 9, 5 ] ギャップを縮めて g = 1 にし、 通常の挿入ソートで仕上げ： [ 1, 2, 3, 5, 8, 9 ]
「遠くの乱れを先に直して、最後に近くを整える」イメージ。
整列アルゴリズム(java)
public class AllSorts {
// 1. Bubble Sort
public static void bubbleSort(int[] arr) {
int n = arr.length;
boolean swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
if (!swapped) break;
}
}
// 2. Selection Sort
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
// 3. Insertion Sort
public static void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
// 4. Shell Sort
public static void shellSort(int[] arr) {
int n = arr.length;
for (int gap = n / 2; gap > 0; gap /= 2) {
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j = i;
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
}
}
// 5. Merge Sort
public static void mergeSort(int[] arr) {
mergeSort(arr, 0, arr.length - 1);
}
private static void mergeSort(int[] arr, int left, int right) {
if (left >= right) return;
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
private static void merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) temp[k++] = arr[i++];
else temp[k++] = arr[j++];
}
while (i <= mid) temp[k++] = arr[i++];
while (j <= right) temp[k++] = arr[j++];
for (int t = 0; t < temp.length; t++) {
arr[left + t] = temp[t];
}
}
// 6. Quick Sort
public static void quickSort(int[] arr) {
quickSort(arr, 0, arr.length - 1);
}
private static void quickSort(int[] arr, int left, int right) {
if (left >= right) return;
int pivot = arr[(left + right) / 2];
int index = partition(arr, left, right, pivot);
quickSort(arr, left, index - 1);
quickSort(arr, index, right);
}
private static int partition(int[] arr, int left, int right, int pivot) {
while (left <= right) {
while (arr[left] < pivot) left++;
while (arr[right] > pivot) right--;
if (left <= right) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
}
return left;
}
// 7. Heap Sort
public static void heapSort(int[] arr) {
int n = arr.length;
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
for (int i = n - 1; i > 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
private static void heapify(int[] arr, int size, int root) {
int largest = root;
int left = 2 * root + 1;
int right = 2 * root + 2;
if (left < size && arr[left] > arr[largest]) largest = left;
if (right < size && arr[right] > arr[largest]) largest = right;
if (largest != root) {
int temp = arr[root];
arr[root] = arr[largest];
arr[largest] = temp;
heapify(arr, size, largest);
}
}
// Main
public static void main(String[] args) {
int[] data = {8, 3, 5, 1, 9, 2};
System.out.println("元の配列:");
printArray(data);
int[] arr1 = data.clone();
bubbleSort(arr1);
System.out.println("Bubble Sort:");
printArray(arr1);
int[] arr2 = data.clone();
selectionSort(arr2);
System.out.println("Selection Sort:");
printArray(arr2);
int[] arr3 = data.clone();
insertionSort(arr3);
System.out.println("Insertion Sort:");
printArray(arr3);
int[] arr4 = data.clone();
shellSort(arr4);
System.out.println("Shell Sort:");
printArray(arr4);
int[] arr5 = data.clone();
mergeSort(arr5);
System.out.println("Merge Sort:");
printArray(arr5);
int[] arr6 = data.clone();
quickSort(arr6);
System.out.println("Quick Sort:");
printArray(arr6);
int[] arr7 = data.clone();
heapSort(arr7);
System.out.println("Heap Sort:");
printArray(arr7);
}
public static void printArray(int[] arr) {
for (int n : arr) System.out.print(n + " ");
System.out.println();
}
}
整列アルゴリズム(java)ダウンロード
今日はこれをテーマに将棋と音楽について考察する
将棋
全手数を求めて、効率よく深堀していく。
効率よく深堀していくためには、今日はベクトル探索してみようと思います。
指し手の評価の高いものから順番に読みを入れていくことにします。
大規模将棋評価モデル(Large Shogi Value Model)にしてみようと思います。
あれっ、整列アルゴリズム使うところがないにゃーーー？ もうひとひねり必要ですね。
評価関数の加点値の高いものから順番に並び替えるときに必要？
後は、ベクトル値の整列に使ってみようかにゃーーー。
計算量を最小にできるようにしたい。
整列アルゴリズムは何を使えばよいかにゃーーー。
どうすればよいかにゃーーー。
音楽
全音数を求めて、効率よく深堀していく。
効率よく深堀していくためには、今日はベクトル探索してみようと思います。
良かったフレーズの評価の高いものから順番に読みを入れていくことにします。
大規模音楽評価モデル(Large Music Value Model)にしてみようと思います。
こちら評価関数の加点値の高いものから順番に並び替えて使ってみようかなぁ。
こちらも計算量を最小に抑えたい。
整列アルゴリズムは重たい処理なので回数を抑えつつ、
効率よく使用するために工夫してみようかにゃーーー。
整列アルゴリズムで違いはあるかにゃーーー。
とても１日では終わらない量だにゃーーー
暇な時のためにネタをストックしておこう。そうしよう。
今考えたのですが、整列オートマトンなんてどうでしょ？
最後に１回だけ整列をするオートマトンです。
slack型時系列オートマトンなんてのも面白そうです。
あともう一つ考えてみよう
Santa Sort 一番高速で軽量で計算量の少ないソート
これを作ってみたくなりました。わくわくどきどき。@o@//
どんなアルゴリズムになるのか、今日はいろいろチャレンジしてみようと思います。