並べ替えは、オブジェクトに対して実行する基本操作の 1 つです。幼児期であっても、子供たちは思考スキルを発達させるにつれて分類することを教えられます。コンピュータやソフトウェアも例外ではありません。Java には多種多様なソート アルゴリズムがあります。それらが何であり、どのように機能するかを確認することをお勧めします。いつか面接でそのうちの1つについて聞かれたらどうしますか？
L は に等しくなります
序章
要素の並べ替えは、開発者が知っておく必要があるアルゴリズムのカテゴリの 1 つです。私が学生だった頃にコンピューター サイエンスが真剣に受け止められていなかったとしても、今日の学生は並べ替えアルゴリズムを実装して理解できるはずです。最も単純な基本アルゴリズムは、forループを使用して実装されます。当然のことながら、配列などの要素のコレクションを並べ替えるには、何らかの方法でコレクションを処理する必要があります。例えば：
int[] array = {10, 2, 10, 3, 1, 2, 5};
for (int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
int iインデックス ( ) を 0 から配列の最後の要素まで変更するループがあります。実際には、配列内の各要素を取得してその内容を出力しているだけです。配列内の要素が多いほど、コードが完了するまでにかかる時間が長くなります。つまり、 がn要素の数である場合、n = 10プログラムの実行には、 の場合よりも 2 倍の時間がかかりますn = 5。プログラムにループが 1 つある場合、実行時間は直線的に増加します。要素が増えるほど、実行時間は長くなります。上記のアルゴリズムは線形時間 (n の線形関数) で動作することがわかります。このような場合、アルゴリズムの複雑さは「O(n)」であると言います。この表記法は、「ビッグ O」または「漸近動作」とも呼ばれます。でも、覚えておくだけでもいいよ」
最も単純なソートアルゴリズム（バブルソート）
配列があり、それを反復処理できるとします。素晴らしい。では、昇順に並べ替えてみましょう。これは何を意味するのでしょうか？これは、2 つの要素 (たとえば、a = 6、b = 5) が与えられた場合、並べ替える必要がありa、bifが(if )aより大きいことを意味します。(配列の場合と同様に) インデックスを使用してコレクションを操作する場合、これは何を意味するのでしょうか? これは、インデックス a の要素がインデックス( )の要素よりも大きい場合、要素を交換する必要があることを意味します。場所を変えるにはさまざまな方法があります。ただし、シンプルでわかりやすく、覚えやすいテクニックを使用します。 ba > bbarray[a] > array[b]
private void swap(int[] array, int ind1, int ind2) {
int tmp = array[ind1];
array[ind1] = array[ind2];
array[ind2] = tmp;
}
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i-1);
}
}
System.out.println(Arrays.toString(array));
array[i] < array[i-1]に対して無効になるため、インデックス 1 から開始しました0。これを行うと、配列に要素がないか、要素が 1 つしかない場合からも保護され、コードの見栄えが良くなります。ただし、1 回のパスでは並べ替えを行うのに十分ではないため、結果の配列はまだ並べ替えられていません。ソートされた配列を取得するまでパスを何度も実行する別のループを追加する必要があります。
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
boolean needIteration = true;
while (needIteration) {
needIteration = false;
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i-1);
needIteration = true;
}
}
}
System.out.println(Arrays.toString(array));
whileこれ以上の反復が必要ないと判断するまで、外側のループ ( ) を繰り返します。デフォルトでは、新しい反復が行われる前に、配列がソートされており、ループする必要がなくなったと想定します。したがって、要素を順番に移動して、この仮定を確認します。しかし、要素の順序が正しくない場合は、要素を交換しますが、要素が正しい順序であるという保証はなくなったことを理解します。これは、別の反復を実行する必要があることを意味します。たとえば、 があるとします[3, 5, 2]。5以上です3— すべて順調です。ただし、2未満です5。ただし、[3, 2, 5]別のパスが必要です。3 > 2そしてそれらを交換する必要があります。ループ内でループを使用しているため、アルゴリズムの複雑さが増加します。n要素が与えられると、それはn * n、つまり になりますO(n^2)。これは二次複雑度と呼ばれます。一般に、何回の反復が必要になるかを正確に知ることはできません。アルゴリズムの複雑さの表現は、最悪の場合に複雑さがどのように増加するかを示します。つまり、要素の数がn変化すると実行時間がどれだけ増加するかを示します。バブル ソートは、最も単純で最も非効率的なソート アルゴリズムの 1 つです。「バカソート」と呼ばれることもあります。このトピックに関する資料:
選択の並べ替え
もう 1 つの並べ替えアルゴリズムは選択並べ替えです。二次複雑性もありますが、それについては後で詳しく説明します。したがって、アイデアはシンプルです。各パスで最小の要素を選択し、それを先頭に移動します。さらに、各パスは右に 1 ステップずつ開始されます。つまり、最初のパスは 0 番目の要素から始まり、2 番目のパスは最初の要素から始まり、以下のようになります。
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int left = 0; left < array.length; left++) {
int minInd = left;
for (int i = left; i < array.length; i++) {
if (array[i] < array[minInd]) {
minInd = i;
}
}
swap(array, left, minInd);
}
System.out.println(Arrays.toString(array));
挿入ソート
挿入ソートもループ内にループがあるため、2 次の複雑さになります。挿入ソートの違いは何ですか? この並べ替えアルゴリズムは「安定」しています。これは、同一の要素が相対的な順序を変更しないことを意味します。繰り返しになりますが、分類する際の特徴という点で同一であることを意味します。
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int left = 0; left < array.length; left++) {
// Get an element
int value = array[left];
// Iterate through the elements that are in front of this element
int i = left - 1;
for (; i >= 0; i--) {
// If the current element is smaller, then move the larger element to the right.
if (value < array[i]) {
array[i + 1] = array[i];
} else {
// If the current element is larger, we stop
break;
}
}
// Insert the current value in the empty space
array[i + 1] = value;
}
System.out.println(Arrays.toString(array));
シャトルソート
もう 1 つの単純なソート アルゴリズムとして、シャトル ソートがあります。これは、双方向バブル ソートまたはカクテル シェーカー ソートとしても知られています。これらの別名は、シャトルの種類がスペースシャトルに関するものではないことを示しています。前後に動くものについてです。このアルゴリズムを考えるとき、それを考えることができます。アルゴリズムの本質は何ですか? このアルゴリズムの本質は、左から右に反復して要素を交換し、他の方向に残っている要素を交換する必要があるかどうかを確認することです。
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i - 1);
for (int z = i - 1; (z - 1) >= 0; z--) {
if (array[z] < array[z - 1]) {
swap(array, z, z - 1);
} else {
break;
}
}
}
}
System.out.println(Arrays.toString(array));
シェルソート
もう 1 つの単純なソート アルゴリズムはシェル ソートです。その要点はバブルソートに似ていますが、反復ごとに比較される要素間に異なるギャップが生じます。反復ごとに半分にカットされます。実装は次のとおりです。
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
// Calculate the gap between the checked elements
int gap = array.length / 2;
// As long as there is a gap between the elements
while (gap >= 1) {
for (int right = 0; right < array.length; right++) {
// Shift the right index until we find one for which
// there is the necessary gap between it and the element before it
for (int c = right - gap; c >= 0; c -= gap) {
if (array[c] > array[c + gap]) {
swap(array, c, c + gap);
}
}
}
// Recalculate the gap
gap = gap / 2;
}
System.out.println(Arrays.toString(array));
マージソート
これらの単純な並べ替えアルゴリズムに加えて、より複雑な並べ替えアルゴリズムもあります。たとえば、マージソートです。注意すべき点が 2 つあります。まず、ここでは再帰が役に立ちます。第二に、アルゴリズムの複雑さは、私たちが慣れ親しんでいるような二次関数ではなくなりました。このアルゴリズムの複雑さは対数的です。これは と書きますO(n log n)。それでは、実装してみましょう。まず、sort メソッドへの再帰呼び出しを作成します。
public static void mergeSort(int[] source, int left, int right) {
// Select the delimiter, i.e. split the input array in half
int delimiter = left + ((right - left) / 2) + 1;
// Recursively execute this function on the two halves (if we can split the input array)
if (delimiter > 0 && right > (left + 1)) {
mergeSort(source, left, delimiter - 1);
mergeSort(source, delimiter, right);
}
}
public static void mergeSort(int[] source, int left, int right) {
// Select the delimiter, i.e. split the input array in half
int delimiter = left + ((right - left) / 2) + 1;
// Recursively execute this function on the two halves (if we can split the input array)
if (delimiter > 0 && right > (left + 1)) {
mergeSort(source, left, delimiter - 1);
mergeSort(source, delimiter, right);
}
// Create a temporary array with the required size
int[] buffer = new int[right - left + 1];
// Starting from the specified left index, go through each element.
int cursor = left;
for (int i = 0; i < buffer.length; i++) {
// We use delimeter to point to the element on the right half
// If delimeter> right, then the right half has no elements that haven't been added
if (delimiter > right || source[cursor] > source[delimiter]) {
buffer[i] = source[cursor];
cursor++;
} else {
buffer[i] = source[delimiter];
delimiter++;
}
}
System.arraycopy(buffer, 0, source, left, buffer.length);
}
mergeSort(array, 0, array.length-1)。ご覧のとおり、プロセスは要約すると、並べ替える必要があるセクションの先頭と末尾の指示とともに入力配列を受け入れることになります。並べ替えが開始されると、これらが配列の先頭と末尾になります。次に、配列を分割するインデックスである区切り文字を計算します。配列が 2 つの部分に分割できる場合は、配列の 2 つの部分に対して sort メソッドを再帰的に呼び出します。ソートされたセクションを挿入する補助バッファーを準備します。次に、ソートするセクションの先頭にインデックスを設定し、空のバッファーの各要素を調べ始めて、最小の要素でバッファーを埋めます。インデックスが指す要素が区切り文字が指す要素より小さい場合、その要素をバッファに入れてインデックスをシフトします。さもないと、区切り文字が指す要素をバッファに配置し、区切り文字をシフトします。区切り文字がソート対象のセクションの境界を超えるか、配列全体を埋めるとすぐに、指定された範囲はソートされたとみなされます。このトピックに関する資料:
カウンティングソートと基数ソート
もう 1 つの興味深い並べ替えアルゴリズムは、カウント ソートです。ここでのアルゴリズムの複雑さは です。O(n+k)ここで、nは要素の数、kは要素の最大値です。このアルゴリズムには欠点が 1 つあります。それは、配列内の最小値と最大値を知る必要があることです。以下にカウントソートの例を示します。
public static int[] countingSort(int[] theArray, int maxValue) {
// An array of "counters", ranging from 0 to the maximum value
int numCounts[] = new int[maxValue + 1];
// We increase the counter in the corresponding cell (index = value)
for (int num : theArray) {
numCounts[num]++;
}
// Create an array to hold the sorted result
int[] sortedArray = new int[theArray.length];
int currentSortedIndex = 0;
// Run through the array of "counters"
for (int n = 0; n < numCounts.length; n++) {
int count = numCounts[n];
// Run through the number of values
for (int k = 0; k < count; k++) {
sortedArray[currentSortedIndex] = n;
currentSortedIndex++;
}
}
return sortedArray;
}
クイックソート
さて、デザートの時間です。最も有名な並べ替えアルゴリズムの 1 つであるクイック ソートです。対数的な複雑さがあります:O(n log n)。このソート アルゴリズムは Tony Hoare によって開発されました。興味深いことに、彼はソビエト連邦に住んでいたときにこの言語を発明し、モスクワ大学で機械翻訳を学び、ロシア語と英語の会話集を開発しました。さらに、Java は、このアルゴリズムのより複雑なバージョンを で使用しますArrays.sort。どうですかCollections.sort？「内部」で物事がどのように分類されているかを覗いてみませんか? コードは次のとおりです。
public static void quickSort(int[] source, int leftBorder, int rightBorder) {
int leftMarker = leftBorder;
int rightMarker = rightBorder;
int pivot = source[(leftMarker + rightMarker) / 2];
do {
// Move the left marker from left to right as long as the element is less than pivot
while (source[leftMarker] < pivot) {
leftMarker++;
}
// Move the right marker as long as the element is greater than pivot
while (source[rightMarker] > pivot) {
rightMarker--;
}
// Check whether we need to swap the elements pointed to by the markers
if (leftMarker <= rightMarker) {
// The left marker will be less than the right one only if we need to do a swap
if (leftMarker < rightMarker) {
int tmp = source[leftMarker];
source[leftMarker] = source[rightMarker];
source[rightMarker] = tmp;
}
// Shift the markers to get new borders
leftMarker++;
rightMarker--;
}
} while (leftMarker <= rightMarker);
// Execute recursively on the parts
if (leftMarker < rightBorder) {
quickSort(source, leftMarker, rightBorder);
}
if (leftBorder < rightMarker) {
quickSort(source, leftBorder, rightMarker);
}
}
int[]の 2 つのマーカーを作成します。最初のメソッド呼び出しでは、それらは配列の先頭と末尾に対応します。次に、 という適切な名前が付けられたピボット要素を特定します。この後、私たちのタスクは、 より小さい値を の左側に移動し、大きい値を右側に移動することです。これを行うには、まずより大きい値が見つかるまでマーカーを移動します。これより小さい値が見つからない場合は、LRpivotpivotpivotLpivotpivot。
R次に、より小さい値が見つかるまでマーカーを移動します
pivot。より大きな値が見つからない場合、 は と
R等しくなります
pivot。次に、
Lマーカーがマーカーの前にある場合
R、またはマーカーと一致する場合、要素が
L要素より小さい場合は要素を交換しようとします
R。
L次に、右に 1シフトし、
R左に 1シフトします。
Lマーカーがマーカーを越えて移動すると
R、交換が完了したことを意味します。小さい値は の左側にあり
pivot、大きい値は の右側にあります。
pivot。この後、同じソートメソッドをサブ配列に対して再帰的に呼び出します。ソート対象のセクションの先頭から右のマーカーまで、および左のマーカーからソート対象のセクションの末尾までです。なぜ最初から右のマーカーまでなのか? 反復の終わりに、右側のマーカーが左側の部分の境界になるまで十分に移動したことが判明するためです。このアルゴリズムは単純な並べ替えよりも複雑であるため、概要を説明することをお勧めします。白い紙を用意して、4 2 6 7 3 と書きます。次に、
pivot真ん中、つまり番号 6 の下に書きます。丸で囲みます。4 の下には 、
L3 の下には と書きます
R。4 は 6 より少なく、2 は 6 より少なくなります。
Lその位置を越えることはできない
pivotため、最終的にその位置に移動することになります。
L
pivot、条件に応じて。もう一度書きます 4 2 6 7 3. 6 (
pivot) を丸で囲み、
Lその下に置きます。次に
Rマーカーを移動します。3 は 6 より小さいので、
R3 にマーカーを置きます。3 は 6 より小さいので (
pivot)、 を実行します
swap。結果を書きます: 4 2 3 7 6. まだ であるため、6 を丸で囲みます
pivot。マーカー
Lは 3 にあります。マーカーは 6 にあります。 を超える
Rまでマーカーを移動することに注意してください。次の番号に移動します。ここでは 2 つの可能性を検討したいと思います。1) 最後から 2 番目の数字が 7 の場合と 2) 7 ではなく 1 である場合。
最後から 2 番目の数字が 1 の場合:マーカーを 1 に移動します。移動できるためです。限り
L
R
L
L
L
Lマーカーは より小さい数値を指します
pivot。しかし、マーカーが より大きい数値を指している
R場合にのみ R を移動できるため、6 から離れることはできません。1 は 6 より小さいため、は実行しません。現在の状況を書きます: 4 2 3 1 6。6 ( ) を丸で囲みます。ずれて動きを止めます。動かない。交換は行っておりません。とを 1 つずつシフトします。1 の下にマーカーを書き込みます。マーカーは範囲外です。範囲外なので何もしません。ただし、これは左側であり、(6) より小さいため、もう一度 4 2 3 1 と書きます。新しいものを選択して、すべてをやり直してください:)
最後から 2 番目の番号が 7 の場合:
R
pivot
swap
pivot
L
pivot
R
L
R
R
L
L
pivot
pivot
マーカーを 7 に移動します
L。右のマーカーはすでにピボットを指しているため、移動できません。7 は より大きいため
pivot、 を実行します
swap。結果を書きます: 4 2 3 6 7. 6 を丸で囲みます
pivot。マーカー
Lは 7 に移動し、マーカーは 3 に移動します。要素が 1 つしかないため、パーツを から最後まで
R並べ替えるのは意味がありません。
Lただし、4 の部分を
Rソート用のマーカーに送信します。a を選択して
pivot、最初からやり直します :) 一見すると、次の値に等しい値を多数追加すると、次のように見えるかもしれません。
pivot、そうするとアルゴリズムが壊れてしまいます。しかしそうではありません。トリッキーな組み合わせを考え出し、紙の上ですべてが正しいと確信し、このような単純なアクションでこれほど信頼性の高い並べ替えメカニズムが実装されていることに驚くことができます。唯一の欠点は、この並べ替えアルゴリズムが安定していないことです。
pivot他の要素が前の部分に交換される前に、いずれかの要素が前に見つかった場合、交換によって同一要素の相対的な順序が変更される可能性があるためです
pivot。
GO TO FULL VERSION