1. バブルソート
バブルソートは、単純で直感的なソートアルゴリズムです。配列を繰り返し走査し、隣接する要素を比較して順序が逆であれば交換します。このプロセスを、配列が完全にソートされるまで繰り返します。このアルゴリズムの名前は、小さい要素が「泡」として徐々に配列の先頭に「浮かび上がって」いく様子に由来します。
アルゴリズムのステップ:
- 隣接する要素を比較します。もし一つ目の要素が二つ目の要素より大きければ、それらを交換します。
- 配列の先頭から末尾まで、すべての隣接する要素ペアに対して上記の操作を行います。このステップが完了すると、最後の要素は配列の中で最大の値になります。
- 最後の要素を除いたすべての要素に対して、上記のステップを繰り返します。
- 比較が必要な要素の数がゼロになるまで、上記のステップを繰り返します。
public void bubbleSort(int[] array) {
int swapValue;
int arrayLength = array.length;
for (int outerIndex = 0; outerIndex < arrayLength; outerIndex++) {
for (int innerIndex = 1; innerIndex < arrayLength - outerIndex; innerIndex++)
if (array[innerIndex - 1] > array[innerIndex]) {
// 順序が逆であれば交換
swapValue = array[innerIndex - 1];
array[innerIndex - 1] = array[innerIndex];
array[innerIndex] = swapValue;
}
}
}
最適化されたバブルソート
配列が早期にソートされる場合、元のバブルソートは最後まで走査を続けます。この無駄を省くために、フラグを導入して、あるパスで交換が発生しなかった場合、ソートが完了したと判断し処理を終了させることができます。
public void optimizedBubbleSort(int[] array) {
int swapValue;
int arrayLength = array.length;
boolean swapped;
do {
swapped = false;
for (int innerIndex = 1; innerIndex < arrayLength; innerIndex++)
if (array[innerIndex - 1] > array[innerIndex]) {
swapValue = array[innerIndex - 1];
array[innerIndex - 1] = array[innerIndex];
array[innerIndex] = swapValue;
swapped = true; // 交換が発生したことを記録
}
} while (swapped); // 交換が発生しなかったら終了
}
2. クイックソート
クイックソートは、分割統治法に基づいた効率的なソートアルゴリズムです。平均的なケースでは O(n log n) の比較回数でソートが完了します。最悪のケースでは O(n²) が必要になりますが、これは稀な状況です。実際には、多くの O(n log n) アルゴリズムよりも高速に動作します。
クイックソートは、配列を「ピボット」と呼ばれる要素を基準に二つの部分に分割します。
アルゴリズムのステップ:
- 配列から一つの要素をピボットとして選択します。
- 配列を再配置し、ピボットより小さい要素をその前に、大きい要素をその後に配置します（同じ値はどちら側でも構いません）。この「分割」操作の後、ピボットは配列の中央に配置されます。
- ピボットより小さい要素の部分配列と、大きい要素の部分配列を再帰的にソートします。
- 再帰の基底ケースは、配列のサイズが0または1のときです。この場合はすでにソート済みと見なされます。再帰は、各反復で少なくとも一つの要素が最終的な位置に配置されるため、必ず終了します。
private static void quickSortRecursive(int[] data, int left, int right) {
if (left < right) {
int pivotIndex = partition(data, left, right);
quickSortRecursive(data, left, pivotIndex - 1);
quickSortRecursive(data, pivotIndex + 1, right);
}
}
private static int partition(int[] data, int left, int right) {
int pivotValue = data[right];
int partitionIndex = left - 1;
int temp;
for (int currentIndex = left; currentIndex < right; currentIndex++) {
if (data[currentIndex] < pivotValue) {
partitionIndex++;
temp = data[partitionIndex];
data[partitionIndex] = data[currentIndex];
data[currentIndex] = temp;
}
}
temp = data[partitionIndex + 1];
data[partitionIndex + 1] = data[right];
data[right] = temp;
return partitionIndex + 1;
}
3. マージソート
マージソートは、マージ操作に基づいた効率的なソートアルゴリズムです。分割統治法の典型的な応用例です。
アルゴリズムのステップ:
- ソート済みの二つの部分配列の合計サイズを持つ領域を確保し、マージ後の配列を格納します。
- 二つの部分配列の先頭を指すポインタを設定します。
- 二つのポインタが指す要素を比較し、小さい方をマージ領域にコピーし、対応するポインタを進めます。
- 一方のポインタが部分配列の末尾に達するまでステップ3を繰り返します。
- もう一方の部分配列に残った要素を、そのままマージ領域の末尾にコピーします。
public static int[] mergeSort(int[] sourceArray, int startIndex, int endIndex) {
int middleIndex = (startIndex + endIndex) / 2;
if (startIndex < endIndex) {
mergeSort(sourceArray, startIndex, middleIndex);
mergeSort(sourceArray, middleIndex + 1, endIndex);
merge(sourceArray, startIndex, middleIndex, endIndex);
}
return sourceArray;
}
public static void merge(int[] sourceArray, int startIndex, int middleIndex, int endIndex) {
int[] mergedArray = new int[endIndex - startIndex + 1];
int leftPointer = startIndex;
int rightPointer = middleIndex + 1;
int mergedIndex = 0;
while (leftPointer <= middleIndex && rightPointer <= endIndex) {
if (sourceArray[leftPointer] <= sourceArray[rightPointer]) {
mergedArray[mergedIndex++] = sourceArray[leftPointer++];
} else {
mergedArray[mergedIndex++] = sourceArray[rightPointer++];
}
}
while (leftPointer <= middleIndex) {
mergedArray[mergedIndex++] = sourceArray[leftPointer++];
}
while (rightPointer <= endIndex) {
mergedArray[mergedIndex++] = sourceArray[rightPointer++];
}
for (int i = 0; i < mergedArray.length; i++) {
sourceArray[startIndex + i] = mergedArray[i];
}
}
4. 選択ソート
選択ソートは、単純な比較ベースのソートアルゴリズムです。
アルゴリズムのステップ:
- 未ソートの部分配列から最小（または最大）の要素を見つけ、ソート済み部分の末尾に移動します。
- 残りの未ソートの要素から、再び最小の要素を見つけ、ソート済み部分の末尾に追加します。
- すべての要素がソートされるまでステップ2を繰り返します。
public int[] selectionSort(int[] inputArray) {
int arrayLength = inputArray.length;
for (int sortedIndex = 0; sortedIndex < arrayLength - 1; sortedIndex++) {
int minIndex = sortedIndex;
for (int searchIndex = sortedIndex + 1; searchIndex < arrayLength; searchIndex++) {
if (inputArray[searchIndex] < inputArray[minIndex]) {
minIndex = searchIndex;
}
}
// 最小の要素を現在の位置と交換
int swapTemp = inputArray[sortedIndex];
inputArray[sortedIndex] = inputArray[minIndex];
inputArray[minIndex] = swapTemp;
}
return inputArray;
}
5. ヒープソート
ヒープソートは、ヒープというデータ構造を利用した比較的高性能なソートアルゴリズムです。ヒープは、完全二分木に近い構造を持ち、親ノードの値が子ノードの値より常に大きい（または小さい）という性質を満たします。ヒープソートの平均時間計算量は O(n log n) です。
アルゴリズムのステップ:
- ヒープ H[0..n-1] を構築します。
- ヒープのルート（最大値）と最後の要素を交換します。
- ヒープのサイズを1減らし、`heapify` 関数を呼び出して新しいルート要素を正しい位置に調整します。
- ヒープのサイズが1になるまでステップ2を繰り返します。
public void heapSort(int[] heapArray) {
int n = heapArray.length;
// ヒープを構築する（最大ヒープ）
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(heapArray, n, i);
}
// ヒープから要素を1つずつ取り出す
for (int i = n - 1; i > 0; i--) {
// 現在のルート（最大要素）を配列の末尾に移動
int temp = heapArray[0];
heapArray[0] = heapArray[i];
heapArray[i] = temp;
// 縮小したヒープを再構築
heapify(heapArray, i, 0);
}
}
// ヒープの性質を維持するためのヘルパー関数
void heapify(int[] heapArray, int n, int i) {
int largest = i; // 親ノードのインデックス
int leftChild = 2 * i + 1; // 左の子ノードのインデックス
int rightChild = 2 * i + 2; // 右の子ノードのインデックス
// 左の子が親より大きい場合
if (leftChild < n && heapArray[leftChild] > heapArray[largest]) {
largest = leftChild;
}
// 右の子が現在の最大値より大きい場合
if (rightChild < n && heapArray[rightChild] > heapArray[largest]) {
largest = rightChild;
}
// 最大値が親ノードでない場合、交換して再帰的にヒープを修正
if (largest != i) {
int swap = heapArray[i];
heapArray[i] = heapArray[largest];
heapArray[largest] = swap;
heapify(heapArray, n, largest);
}
}