並べ替えは、オブジェクトに対して実行される基本的なアクティビティまたはアクションの 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 の場合、プログラムの実行には n=5 の場合より 2 倍の時間がかかります。プログラムにループが 1 つある場合、実行時間は直線的に増加します。要素が増えると、実行時間も長くなります。上記のコードのアルゴリズムは線形時間 (n) で実行されることがわかります。このような場合、「アルゴリズムの複雑さ」は O(n) と言われます。この表記法は、「ビッグ O」または「漸近動作」とも呼ばれます。ただし、「アルゴリズムの複雑さ」を覚えておくだけで大丈夫です。
最も単純なソート(バブルソート)
したがって、配列があり、それを反復処理できます。素晴らしい。では、昇順に並べ替えてみましょう。これは私たちにとって何を意味するのでしょうか?これは、2 つの要素 (たとえば、a=6、b=5) が与えられた場合、a が b より大きい場合 (a > b の場合)、a と b を交換する必要があることを意味します。(配列の場合と同様に) インデックスによってコレクションを操作する場合、これは何を意味するのでしょうか? これは、インデックス a の要素がインデックス b の要素より大きい場合 (array[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));
ご覧のとおり、要素は実際に場所を変更しました。私たちは 1 つの要素から始めました。なぜなら... 配列が 1 つの要素のみで構成されている場合、式 1 < 1 は true を返さないため、配列に 1 つの要素がある場合や要素がまったくない場合から身を守ることができ、コードの見栄えが良くなります。しかし、最終的な配列はソートされていません。なぜなら... 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
これ以上反復が必要ないと判断するまで、外側のループ ( ) を反復します。デフォルトでは、新しい反復を行う前に、配列がソートされていると想定され、それ以上反復したくありません。したがって、要素を順番に調べて、この仮定を確認します。しかし、要素の順序が間違っている場合は、要素を交換しますが、要素が正しい順序になっているかどうか確信が持てないことがわかります。したがって、もう 1 回反復を実行したいと考えます。たとえば、[3、5、2]。5 は 3 より大きく、すべて問題ありません。ただし、2 は 5 より小さいです。ただし、[3, 2, 5] にはもう 1 回のパスが必要です。3 > 2 の場合は交換する必要があります。ループ内でループを使用するため、アルゴリズムの複雑さが増加することがわかります。n 要素の場合、n * n、つまり O(n^2) になります。この複雑さは二次式と呼ばれます。理解しているように、必要な反復回数を正確に知ることはできません。アルゴリズムの複雑さの指標は、複雑さの増加傾向、最悪のケースを示す目的を果たします。要素数 n が変化すると、実行時間はどれくらい増加しますか。バブル ソートは、最も単純で非効率なソートの 1 つです。「バカな仕分け」と呼ばれることもあります。関連資料:
選択範囲の並べ替え
もう 1 つのソートは選択ソートです。二次複雑性もありますが、それについては後で詳しく説明します。したがって、アイデアはシンプルです。各パスでは最小の要素が選択され、それが先頭に移動されます。この場合、新しいパスはそれぞれ右に移動して開始します。つまり、最初のパスは最初の要素から、2 番目のパスは 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));
この並べ替えは不安定です。同一の要素は (要素を並べ替える際の特性の観点から) 位置を変えることができます。良い例が、Wikipedia の記事「Sorting_by-selection 」に示されています。関連資料:
挿入ソート
挿入ソートもループ内にループがあるため、2 次の複雑さになります。選択ソートとの違いは何ですか? このソートは「安定」しています。これは、同一の要素の順序が変わらないことを意味します。分類する際の特徴という点では同じです。int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int left = 0; left < array.length; left++) {
// Retrieve the value of the element
int value = array[left];
// Move through the elements that are before the pulled element
int i = left - 1;
for (; i >= 0; i--) {
// If a smaller value is pulled out, move the larger element further
if (value < array[i]) {
array[i + 1] = array[i];
} else {
// If the pulled element is larger, stop
break;
}
}
// Insert the extracted value into the freed 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 difference between the elements
while (gap >= 1) {
for (int right = 0; right < array.length; right++) {
// Shift the right pointer until we can find one that
// there won't be enough space 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));
関連資料:
マージソート
ここで示した単純な並べ替えに加えて、より複雑な並べ替えもあります。たとえば、マージソートです。まず、再帰が役に立ちます。第二に、私たちの複雑さは、これまでのように二次関数ではなくなります。このアルゴリズムの複雑さは対数的です。O(n log n) と書きます。それでは、これをやってみましょう。まず、並べ替えメソッドへの再帰呼び出しを作成しましょう。public static void mergeSort(int[] source, int left, int right) {
// Choose a separator, i.e. split the input array in half
int delimiter = left + ((right - left) / 2) + 1;
// Execute this function recursively for the two halves (if we can split(
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) {
// Choose a separator, i.e. split the input array in half
int delimiter = left + ((right - left) / 2) + 1;
// Execute this function recursively for the two halves (if we can split(
if (delimiter > 0 && right > (left + 1)) {
mergeSort(source, left, delimiter - 1);
mergeSort(source, delimiter, right);
}
// Create a temporary array with the desired size
int[] buffer = new int[right - left + 1];
// Starting from the specified left border, go through each element
int cursor = left;
for (int i = 0; i < buffer.length; i++) {
// We use the delimeter to point to the element from the right side
// If delimeter > right, then there are no unadded elements left on the right side
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 つの部分に分割できる場合、分割器が配列を分割したセクションに対して再帰的並べ替えを呼び出します。ソートされたセクションを選択する追加のバッファー配列を準備します。次に、ソートする領域の先頭にカーソルを置き、準備した空の配列の各要素を調べて、最小の要素を入力します。カーソルが指す要素が除数が指す要素より小さい場合、この要素をバッファ配列に配置し、カーソルを移動します。それ以外の場合は、セパレータが指す要素をバッファ配列に配置し、セパレータを移動します。区切り文字が並べ替えられた領域の境界を超えるか、配列全体を埋めるとすぐに、指定された範囲は並べ替えられたとみなされます。 関連資料:
カウンティングソートと基数ソート
もう 1 つの興味深い並べ替えアルゴリズムは、Counting Sort です。この場合のアルゴリズムの複雑さは O(n+k) になります。ここで、n は要素の数、k は要素の最大値です。このアルゴリズムには 1 つ問題があります。それは、配列内の最小値と最大値を知る必要があることです。以下はカウントソートの実装例です。public static int[] countingSort(int[] theArray, int maxValue) {
// Array with "counters" ranging from 0 to the maximum value
int numCounts[] = new int[maxValue + 1];
// In the corresponding cell (index = value) we increase the counter
for (int num : theArray) {
numCounts[num]++;
}
// Prepare array for sorted result
int[] sortedArray = new int[theArray.length];
int currentSortedIndex = 0;
// go through the array with "counters"
for (int n = 0; n < numCounts.length; n++) {
int count = numCounts[n];
// go by the number of values
for (int k = 0; k < count; k++) {
sortedArray[currentSortedIndex] = n;
currentSortedIndex++;
}
}
return sortedArray;
}
ご存知のとおり、最小値と最大値を事前に知っておく必要がある場合、非常に不便です。そして、別のアルゴリズムである Radix Sort があります。ここではアルゴリズムを視覚的にのみ説明します。実装については、資料を参照してください。
Javaクイックソート
さて、デザートとして、最も有名なアルゴリズムの 1 つであるクイック ソートをご紹介します。アルゴリズムの複雑さは O(n log n) です。このソートはホアソートとも呼ばれます。興味深いことに、このアルゴリズムはホア氏がソビエト連邦滞在中に発明したもので、モスクワ大学でコンピューター翻訳を学び、ロシア語と英語の会話集を開発していました。このアルゴリズムは、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 while element is less than pivot
while (source[leftMarker] < pivot) {
leftMarker++;
}
// Move the right marker until element is greater than pivot
while (source[rightMarker] > pivot) {
rightMarker--;
}
// Check if you don't need to swap elements pointed to by markers
if (leftMarker <= rightMarker) {
// The left marker will only be less than the right marker if we have to swap
if (leftMarker < rightMarker) {
int tmp = source[leftMarker];
source[leftMarker] = source[rightMarker];
source[rightMarker] = tmp;
}
// Move markers to get new borders
leftMarker++;
rightMarker--;
}
} while (leftMarker <= rightMarker);
// Execute recursively for parts
if (leftMarker < rightBorder) {
quickSort(source, leftMarker, rightBorder);
}
if (leftBorder < rightMarker) {
quickSort(source, leftBorder, rightMarker);
}
}
ここにあるものはすべて非常に恐ろしいので、それを理解してみましょう。入力配列int[]
ソースに対して、左 (L) と右 (R) の 2 つのマーカーを設定します。初めて呼び出されたとき、配列の先頭と末尾が一致します。次に、サポート要素、別名 を決定しますpivot
。この後、私たちのタスクは、 より小さい値をpivot
左に移動しpivot
、大きい値を右に移動することです。L
これを行うには、まずより大きい値が見つかるまでポインタを移動しますpivot
。これより小さい値が見つからない場合は、pivot
. Потом двигаем указатель
R
пока не найдём меньшее, чем
pivot
meaning. Если меньшее meaning не нашли, то
R
совпадёт с
pivot
. Далее, если указатель
L
находится до указателя
R
or совпадает с ним, то пытаемся выполнить обмен элементов, если элемент
L
меньше, чем
R
. Далее
L
сдвигаем вправо на 1 позицию,
R
сдвигаем влево на одну позицию. Когда левый маркер
L
окажется за правым маркером
R
это будет означать, что обмен закончен, слева от
pivot
меньшие значения, справа от
pivot
— большие значения. После этого рекурсивно вызываем такую же сортировку для участков массива от начала сортируемого участка до правого маркера и от левого маркера до конца сортируемого участка. Почему от начала до правого? Потому что в конце итерации так и получится, что правый маркер сдвинется настолько, что станет границей части слева. Этот алгоритм более сложный, чем простая sorting, поэтому его лучше зарисовать. Возьмём белый лист бумаги, запишем: 4 2 6 7 3 , а
Pivot
по центру, т.е. число 6. Обведём его в круг. Под 4 напишем
L
, под 3 напишем
R
. 4 меньше чем 6, 2 меньше чем 6. Total,
L
переместился на положение
pivot
, т.к. по условию
L
не может уйти дальше, чем
pivot
. Напишем снова 4 2 6 7 3 , обведём 6 вкруг (
pivot
) и поставим под ним
L
. Теперь двигаем указатель
R
. 3 меньше чем 6, поэтому ставим маркер
R
на цифру 3. Так How 3 меньше, чем
pivot 6
выполняем
swap
, т.е. обмен. Запишем результат: 4 2 3 7 6 , обводим 6 вкруг, т.к. он по прежнему
pivot
. Указатель
L
на цифре 3, указатель
R
на цифре 6. Мы помним, что двигаем указатели до тех пор, пока
L
не зайдём за
R
.
L
двигаем на следующую цифру. Тут хочется разобрать два варианта: если бы предпоследняя цифра была 7 и если бы она была не 7, а 1.
Предпоследня цифра 1: Сдвинули указатель
L
на цифру 1, т.к. мы можем двигать
L
до тех пор, пока указатель
L
указывает на цифру, меньшую чем
pivot
. А вот
R
мы не можем сдвинуть с 6, т.к. R не мы можем двигать только если указатель
R
указывает на цифру, которая больше чем
pivot
.
swap
не делаем, т.к. 1 меньше 6. Записываем положение: 4 2 3 1 6, обводим
pivot 6
.
L
сдвигается на
pivot
и больше не двигается.
R
тоже не двигается. Обмен не производим. Сдвигаем
L
и
R
на одну позицию и подписываем цифру 1 маркером
R
, а
L
получается вне числа. Т.к.
L
вне числа — ничего не делаем, а вот часть 4 2 3 1 выписываем снова, т.к. это наша левая часть, меньшая, чем
pivot 6
. Выделяем новый
pivot
и начинаем всё снова )
Предпоследняя цифра 7: Сдвинули указать
L
на цифру 7, правый указатель не можем двигать, т.к. он уже указывает на pivot. т.к. 7 больше, чем
pivot
, то делаем
swap
. Запишем результат: 4 2 3 6 7, обводим 6 кружком, т.к. он
pivot
. Указатель
L
теперь сдвигается на цифру 7, а указатель
R
сдвигается на цифру 3. Часть от
L
до конца нет смысла сортировать, т.к. там всего 1 элемент, а вот часть от 4 до указателя
R
отправляем на сортировку. Выбираем
pivot
и начинаем всё снова ) Может на первый взгляд показаться, что если расставить много одинаковых с
pivot
значений, это сломает алгоритм, но это не так. Можно напридумывать каверзных вариантов и на бумажке убедиться, что всё правильно и подивиться, How такие простые действия предоставляют такой надёжный механизм. Единственный минус — такая sorting не является стабильной. Т.к. при выполнении обмена одинаковые элементы могут поменять свой порядок, если один из них встретился до
pivot
до того, How другой элемент попал в часть до
pivot
при помощи обмена. Материал:
GO TO FULL VERSION