アルゴリズムとアニメーションの整合#
バブルソート#
バブルソート（Bubble Sort）は、シンプルなソートアルゴリズムで、ソートするリストを繰り返し走査し、隣接する要素を比較して位置を交換します。順序が間違っている場合に交換を行います。このプロセスは、リスト全体がもはや交換を必要としなくなるまで繰り返され、最終的に整列されたリストが得られます。
public class BubbleSort {
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
// 交換が行われたかどうかを示すフラグ
boolean 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;
}
}
}
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
bubbleSort(arr);
System.out.println("ソート後の配列:");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
選択ソート#
その基本的な考え方は、毎回ソート待ちのシーケンスから最小（または最大）の要素を選択し、それをシーケンスの先頭に置き、すべての要素がソートされるまで繰り返すことです。
public class SelectionSort {
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[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
public static void main(String[] args) {
int[] arr = {64, 25, 12, 22, 11};
selectionSort(arr);
System.out.println("ソート後の配列:");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
挿入ソート#
最初のソート待ちのシーケンスの最初の要素をソート済みのシーケンスと見なし、2 番目の要素から最後の要素までを未ソートのシーケンスとします。
未ソートのシーケンスを先頭から末尾までスキャンし、スキャンした各要素をソート済みのシーケンスの適切な位置に挿入します。（挿入する要素がソート済みのシーケンス内のある要素と等しい場合は、挿入する要素を等しい要素の後ろに挿入します。）
public class InsertionSort {
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; 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;
}
}
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6};
insertionSort(arr);
System.out.println("ソート後の配列:");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
クイックソート#
クイックソート（QuickSort）は、トニー・ホア（Tony Hoare）によって開発された効率的なソートアルゴリズムです。平均的には、n 個の要素をソートするのに Ο(nlogn) 回の比較が必要ですが、最悪の場合は Ο(n²) 回の比較が必要になる可能性がありますが、このような状況は稀です。実際、クイックソートは通常、他の Ο(nlogn) アルゴリズムよりも速いです。
クイックソートは、分割統治法（Divide and Conquer）を使用して、シーケンス（リスト）を 2 つの部分シーケンス（サブリスト）に分けてソートします。
クイックソートの最悪の実行時間は O (n²) ですが、例えば順序数列のクイックソートです。しかし、その平均期待時間は O (nlogn) であり、O (nlogn) 記号に含まれる定数因子は非常に小さく、複雑度が O (nlogn) に等しいマージソートよりもはるかに小さいです。したがって、ほとんどの順序性が弱いランダムな数列に対して、クイックソートは常にマージソートより優れています。
public class QuickSort {
// 主メソッド、テスト用
public static void main(String[] args) {
int[] array = {34, 7, 23, 32, 5, 62, 32, 7, 9};
quickSort(array, 0, array.length - 1);
System.out.println("ソート後の配列：");
for (int num : array) {
System.out.print(num + " ");
}
}
// クイックソートの主メソッド
public static void quickSort(int[] array, int low, int high) {
if (low < high) {
int pivotIndex = partition(array, low, high);
quickSort(array, low, pivotIndex - 1); // 左半分をソート
quickSort(array, pivotIndex + 1, high); // 右半分をソート
}
}
// 分割メソッド、基準点を選択して分割
private static int partition(int[] array, int low, int high) {
int pivot = array[high]; // 最右の要素を基準点として選択
int i = low - 1; // iは基準点より小さい領域のインデックス
for (int j = low; j < high; j++) {
if (array[j] < pivot) {
i++;
swap(array, i, j); // 基準点より小さい要素を左に交換
}
}
swap(array, i + 1, high); // 基準点を正しい位置に置く
return i + 1; // 基準点の位置を返す
}
// 配列内の2つの要素を交換
private static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
シェルソート#
シェルソート（Shell Sort）は、挿入ソートの効率的な改良版であり、安定したソートアルゴリズムではありません。
シェルソートの改良は、挿入ソートの 2 つの重要な特性に基づいています：
- 挿入ソートは基本的に整列されたデータに対して効率が高い：データがほぼ整列されている場合、挿入ソートの効率は線形に近づくことがあります。
- 挿入ソートの限界：挿入ソートは毎回 1 つの要素しか移動できないため、大規模な無秩序データを処理する際の効率が低下します。
シェルソートの基本的な考え方は：
- グループソート：まず、ソート待ちのシーケンスをいくつかの小さな部分シーケンスに分割し、これらの部分シーケンスに対して挿入ソートを行います。部分シーケンスのグループは、減少する増分（gap）によって行われます。初期には、増分は大きく、ソートが進むにつれて、増分は徐々に小さくなります。
- 最終ソート：増分が 1 に減少すると、全体のシーケンスの記録は「基本的に整列されている」状態になり、この時点で全体の記録に対して 1 回の挿入ソートを行うことでソートが完了します。
シェルソートの鍵は、合理的な増分シーケンスを選択することです。異なる増分シーケンスはソートの効率に大きな影響を与え、一般的な増分シーケンスには初期の増分が n/2 であり、その後の増分が徐々に 1 に減少します。
public class ShellSort {
// 主メソッド、テスト用
public static void main(String[] args) {
int[] array = {34, 7, 23, 32, 5, 62, 32, 7, 9};
shellSort(array);
System.out.println("ソート後の配列：");
for (int num : array) {
System.out.print(num + " ");
}
}
// シェルソートメソッド
public static void shellSort(int[] array) {
int n = array.length;
// 初期の増分を配列の長さの半分に設定
for (int gap = n / 2; gap > 0; gap /= 2) {
// 各増分値に対して挿入ソートを行う
for (int i = gap; i < n; i++) {
int temp = array[i];
int j = i;
// 現在の要素に対して挿入ソートを行う
while (j >= gap && array[j - gap] > temp) {
array[j] = array[j - gap];
j -= gap;
}
array[j] = temp;
}
}
}
}
マージソート#
マージソート（Merge Sort）は、分割統治法に基づく効率的なソートアルゴリズムです。その基本的な考え方は、ソート待ちのシーケンスを再帰的に 2 つの部分シーケンスに分割し、各部分シーケンスが 1 つの要素だけを含むまで分割し、その後、これらの部分シーケンスを徐々にマージして 1 つの整列されたシーケンスにすることです。マージソートは、上から下への再帰的な実装と、下から上への反復的な実装の 2 つの方法に分けられます。
public class MergeSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) throws Exception {
// arrをコピーして、パラメータの内容を変更しない
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
if (arr.length < 2) {
return arr;
}
int middle = (int) Math.floor(arr.length / 2);
int[] left = Arrays.copyOfRange(arr, 0, middle);
int[] right = Arrays.copyOfRange(arr, middle, arr.length);
return merge(sort(left), sort(right));
}
protected int[] merge(int[] left, int[] right) {
int[] result = new int[left.length + right.length];
int i = 0;
while (left.length > 0 && right.length > 0) {
if (left[0] <= right[0]) {
result[i++] = left[0];
left = Arrays.copyOfRange(left, 1, left.length);
} else {
result[i++] = right[0];
right = Arrays.copyOfRange(right, 1, right.length);
}
}
while (left.length > 0) {
result[i++] = left[0];
left = Arrays.copyOfRange(left, 1, left.length);
}
while (right.length > 0) {
result[i++] = right[0];
right = Arrays.copyOfRange(right, 1, right.length);
}
return result;
}
}
ヒープソート#
ヒープソート（Heap Sort）は、ヒープデータ構造に基づく効率的なソートアルゴリズムです。ヒープの特性を利用してソートを実現し、通常は最大ヒープまたは最小ヒープを使用します。ヒープソートの基本的な考え方は、ソート待ちのシーケンスをヒープに変換し、最大または最小の値をヒープから逐次抽出し、ヒープの構造を調整することでソートを実現します。
ヒープソートの基本ステップ：#
-
ヒープの構築：ソート待ちの配列を最大ヒープ（または最小ヒープ）に構築します。最大ヒープでは、各親ノードの値はその子ノードの値以上でなければなりません。最小ヒープでは、各親ノードの値はその子ノードの値以下でなければなりません。
-
ソート：
- ヒープから根ノード（最大値または最小値）を抽出し、それをヒープの最後の要素と交換します。
- ヒープを再調整して、ヒープの特性を再び満たすようにします。
- ヒープが空になるまで、上記のステップを繰り返します。
public class HeapSort {
// 主メソッド、テスト用
public static void main(String[] args) {
int[] array = {34, 7, 23, 32, 5, 62, 32, 7, 9};
heapSort(array);
System.out.println("ソート後の配列：");
for (int num : array) {
System.out.print(num + " ");
}
}
// ヒープソートメソッド
public static void heapSort(int[] array) {
int n = array.length;
// 最大ヒープを構築
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(array, n, i);
}
// ヒープから要素を抽出
for (int i = n - 1; i > 0; i--) {
// 根ノード（最大値）を配列の末尾と交換
swap(array, 0, i);
// ヒープを再調整
heapify(array, i, 0);
}
}
// iを根とする部分木が最大ヒープの特性を満たすように調整するメソッド
private static void heapify(int[] array, int n, int i) {
int largest = i; // 最大値を根ノードとして初期化
int left = 2 * i + 1; // 左子ノード
int right = 2 * i + 2; // 右子ノード
// 左子ノードがより大きい場合
if (left < n && array[left] > array[largest]) {
largest = left;
}
// 右子ノードがより大きい場合
if (right < n && array[right] > array[largest]) {
largest = right;
}
// 最大値が根ノードでない場合
if (largest != i) {
swap(array, i, largest);
// 子木を再帰的に調整
heapify(array, n, largest);
}
}
// 配列内の2つの要素を交換
private static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
カウントソート#
カウントソートは、線形時間複雑度のソートアルゴリズムで、整数の範囲が限られている状況に適しています。その基本的な考え方は、各要素の出現回数を数えることによって要素の位置を決定し、ソートを完了することです。以下はカウントソートの基本ステップです：
- 範囲を決定：まず、ソート待ちの要素の最大値と最小値を決定します。この範囲が、作成するカウント配列のサイズを決定します。
- カウント配列を作成：要素の範囲に基づいてカウント配列を作成します。配列のインデックスはソート待ちの要素の値を表し、配列の値はその値の出現回数を表します。
- 要素の出現回数を数える：元のデータを走査し、各要素に対応するカウント配列の位置の値を 1 増やします。
- 累積カウントを計算：カウント配列に累積和を計算し、各要素の最終位置を決定します。
- ソート結果を生成：累積カウント配列の情報に基づいて、要素を正しい位置に配置し、ソートされた配列を生成します。
import java.util.Arrays;
public class CountingSort {
public static void countingSort(int[] array) {
if (array == null || array.length == 0) {
return;
}
// 配列内の最大値を見つける
int max = Arrays.stream(array).max().orElse(Integer.MAX_VALUE);
// カウント配列を作成し、初期化
int[] count = new int[max + 1];
// 各要素の出現回数を数える
for (int num : array) {
count[num]++;
}
// カウント配列を累積カウント配列に変換
for (int i = 1; i < count.length; i++) {
count[i] += count[i - 1];
}
// 累積カウント配列に基づいてソートされた結果を生成
int[] sortedArray = new int[array.length];
for (int i = array.length - 1; i >= 0; i--) {
sortedArray[count[array[i]] - 1] = array[i];
count[array[i]]--;
}
// ソート結果を元の配列にコピー
System.arraycopy(sortedArray, 0, array, 0, array.length);
}
public static void main(String[] args) {
int[] array = {4, 2, 2, 8, 3, 3, 1};
System.out.println("元の配列: " + Arrays.toString(array));
countingSort(array);
System.out.println("ソート後: " + Arrays.toString(array));
}
}
バケットソート#
バケットソート（Bucket Sort）は、分布に基づくソートアルゴリズムで、特に入力データが均等に分布している場合に適しています。要素を複数のバケットに分け、各バケット内の要素を個別にソートし、最後にすべてのバケット内の要素を順番にマージすることでソートを完了します。
バケットソートの基本ステップ#
- バケットを作成：入力データの範囲と分布に基づいて、一定数のバケットを作成します。各バケットは 1 つの区間を表します。
- 要素をバケットに割り当てる：入力配列を走査し、各要素をその値に基づいて適切なバケットに配置します。
- 各バケット内の要素をソート：適切なソートアルゴリズム（挿入ソートやクイックソートなど）を選択して、各バケット内の要素をソートします。
- すべてのバケットのソート結果をマージ：各バケット内の要素を順番に連結し、最終的な整列された配列を形成します。
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class BucketSort {
public static void bucketSort(float[] array) {
if (array == null || array.length == 0) {
return;
}
// バケットを作成
int numberOfBuckets = array.length;
List<Float>[] buckets = new ArrayList[numberOfBuckets];
for (int i = 0; i < numberOfBuckets; i++) {
buckets[i] = new ArrayList<>();
}
// 要素をバケットに割り当てる
for (float num : array) {
int bucketIndex = (int) (num * numberOfBuckets); // バケットの位置を決定
buckets[bucketIndex].add(num);
}
// 各バケット内の要素をソート
for (List<Float> bucket : buckets) {
Collections.sort(bucket);
}
// すべてのバケットのソート結果をマージ
int index = 0;
for (List<Float> bucket : buckets) {
for (float num : bucket) {
array[index++] = num;
}
}
}
public static void main(String[] args) {
float[] array = {0.42f, 0.32f, 0.73f, 0.25f, 0.67f, 0.48f, 0.12f, 0.89f, 0.94f, 0.36f};
System.out.println("元の配列: ");
for (float num : array) {
System.out.print(num + " ");
}
System.out.println();
bucketSort(array);
System.out.println("ソート後: ");
for (float num : array) {
System.out.print(num + " ");
}
}
}
基数ソート#
基数ソート（Radix Sort）は、比較を行わない整数ソートアルゴリズムで、整数や特定の長さの文字列をソートするのに適しています。基数ソートは、最下位有効桁（LSD、Least Significant Digit）から最上位有効桁（MSD、Most Significant Digit）までの各桁または数字の位数に基づいてソートを行い、最終的に配列全体を整列させます。
基数ソートの基本的な考え方#
基数ソートの核心は、ソート待ちの数字を桁ごとに（低い桁から高い桁またはその逆）ソートすることです。基数ソートは各桁のソートに依存しているため、通常は安定したソートアルゴリズム（カウントソートやバケットソートなど）を利用して、各ラウンドのソート後に同じ桁数の要素がその相対的な順序を保持することを保証します。
基数ソートのステップ#
- 最大値の桁数を決定：配列内の最大要素の桁数を見つけ、これがソートのラウンド数を決定します。
- 最下位桁からソートを開始：最下位桁から始めて、各桁の数字をソートします。ソート時には安定したソートアルゴリズムを使用できます。
- 繰り返す：より高い各桁に対してソートを行い、最高位まで続けます。
- 最終的なソート結果：すべての桁のソートが完了すると、配列は整列されます。
例#
整数配列 [170, 45, 75, 90, 802, 24, 2, 66] を基数ソートする場合：
-
最大値の桁数を決定：最大値
802は 3 桁なので、ソートは 3 ラウンド行います。 -
第一ラウンド（最下位桁でソート）：
- ソート結果：
[170, 90, 802, 2, 24, 45, 75, 66]
- ソート結果：
-
第二ラウンド（十位でソート）：
- ソート結果：
[802, 2, 24, 45, 66, 170, 75, 90]
- ソート結果：
-
第三ラウンド（百位でソート）：
- ソート結果：
[2, 24, 45, 66, 75, 90, 170, 802]
- ソート結果：
import java.util.*;
public class RadixSortWithHashMap {
// 配列内の最大値を取得し、ソートのラウンド数を決定
private static int getMax(int[] array) {
int max = array[0];
for (int num : array) {
if (num > max) {
max = num;
}
}
return max;
}
// HashMapを使用してカウントソートを実装
private static void countingSortWithHashMap(int[] array, int exp) {
// HashMapを使用して各桁の対応リストを保存
Map<Integer, List<Integer>> countMap = new HashMap<>();
// HashMapのキー（0-9の数字）に対してリストを初期化
for (int i = 0; i < 10; i++) {
countMap.put(i, new ArrayList<>());
}
// 各桁の数字に基づいて要素をHashMapのリストに配置
for (int num : array) {
int digit = (num / exp) % 10;
countMap.get(digit).add(num);
}
// HashMapの要素をキーの順序（0から9）で配列に書き戻す
int index = 0;
for (int i = 0; i < 10; i++) {
for (int num : countMap.get(i)) {
array[index++] = num;
}
}
}
// 主基数ソート関数
public static void radixSort(int[] array) {
// 最大値を見つけてラウンド数を決定
int max = getMax(array);
// 最下位桁から各桁に対してカウントソートを行う
for (int exp = 1; max / exp > 0; exp *= 10) {
countingSortWithHashMap(array, exp);
}
}
public static void main(String[] args) {
int[] array = {170, 45, 75, 90, 802, 24, 2, 66};
System.out.println("元の配列: " + Arrays.toString(array));
radixSort(array);
System.out.println("ソート後: " + Arrays.toString(array));
}
}
この記事は Mix Space によって xLog に同期更新されました。元のリンクは https://me.liuyaowen.club/posts/default/20240821and3