最速の並べ替えアルゴリズム Java
この記事では、2つの最速のソート アルゴリズムについて説明し、それらのコードを Java で記述します。
最初の手法はカウント ソートですが、これにはいくつかの制限があります。 そのため、Merge Sort アルゴリズムについても説明します。
Java での並べ替えアルゴリズムのカウント
カウントソートアルゴリズムは、配列要素が特定の範囲内にある場合に使用できる最速のソート手法の 1つです。 これは比較ベースの並べ替え手法ではありませんが、すべての配列要素の頻度をカウントして格納することにより、配列を並べ替えます。
簡単に言えば、ハッシュを使用して配列をソートします。
ユーザーは、カウントの並べ替えについて以下のアルゴリズムに従う必要があります。
-
配列の最大要素と最小要素を見つけます。
-
次に、最大要素と最小要素を使用して配列の範囲を見つけ、サイズ範囲の新しい
freq配列を作成して、すべての要素の頻度を格納します。 -
元の配列を繰り返し処理し、すべての要素の頻度を
freq配列に格納します。 -
頻度を加算することにより、すべての要素の累積頻度を数えます。
-
最後から元の配列への反復を開始し、
freq配列を使用してすべての要素をソートされた位置に配置します。 -
resultから元の配列にすべての並べ替えられた要素を格納して、元の配列を並べ替えます。
コード例:
class CountingSort {
// function to find the maximum from the array
static int findMax(int arr[]) {
int maxi = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > maxi)
maxi = arr[i];
}
return maxi; // return maximum
}
// function to find the minimum from the array
static int findMin(int arr[]) {
int mini = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] < mini)
mini = arr[i];
}
return mini; // return minimum
}
static void cntSort(int[] arr) {
int maxi = findMax(arr);
int mini = findMin(arr);
// getting range from maximum and minimum elements of the array
int range = maxi - mini + 1;
// creating the array to store the frequency of elements
int freq[] = new int[range];
// resultant array
int result[] = new int[arr.length];
// counting frequency of elements and storing it to freq array
for (int i = 0; i < arr.length; i++) {
freq[arr[i] - mini]++;
}
// Doing addition of frequency
for (int i = 1; i < freq.length; i++) {
freq[i] += freq[i - 1];
}
// Putting every element of arr to its correct place based on the freq array
for (int i = arr.length - 1; i >= 0; i--) {
result[freq[arr[i] - mini] - 1] = arr[i];
freq[arr[i] - mini]--;
}
// Make arr array sorted by assigning elements from the result array
for (int i = 0; i < arr.length; i++) {
arr[i] = result[i];
}
}
public static void main(String[] args) {
int[] arr = {10, 20, -2, -4, 3, 40, 50, 30, 20, 10};
cntSort(arr);
System.out.println("Sorted Array using counting sort is ");
for (int a = 0; a < arr.length; a++) {
System.out.print(arr[a] + " ");
}
}
}
出力：
Sorted Array is -4 -2 3 10 10 20 20 30 40 50
Java のカウンティング ソート アルゴリズムの時間計算量
単一の for ループを使用しているため、Counting Sort の時間計算量は線形の順序です。
| 最良の場合 | O(n+k) |
| 平均ケース | O(n+k) |
| 最悪の場合 | O(n+k) |
Java のカウンティング ソート アルゴリズムのスペースの複雑さ
一時配列を使用してソートされた要素を格納するため、カウントソートのスペースの複雑さは O(n) です。
Java のカウントソートアルゴリズムの制限
カウンティングソート手法は、間違いなく配列の要素をソートする最速のアルゴリズムですが、いくつかの制限があります。
ユーザーは、配列の長さが非常に小さく、入力範囲が数百万のように大きすぎるシナリオについて考えることができます。 このような場合は、バブル ソートでさえもパフォーマンスが向上します。
そのため、入力範囲が小さい場合、ユーザーはこれを使用して線形時間で配列を並べ替えることができます。
Java のマージ ソート アルゴリズム
Counting Sort の制限を克服するために、ユーザーは Merge Sort 手法を使用できます。
マージ ソート アルゴリズムは、分割統治法に従います。 まず、配列を 2つに分割して並べ替え、並べ替えた配列をマージします。
完全なアルゴリズムを段階的に学習するには、ユーザーは以下の手順に従うことができます。
-
配列の中点を見つけます。
-
配列の最初と 2 番目の部分に対して
mergeSort()関数を再帰的に呼び出します。 -
merge()関数を呼び出して、配列をマージします。 -
merge()関数で、配列の 2つの部分と同じサイズの 2つの一時配列を作成し、配列要素を対応する一時配列に格納します。 -
両方の要素が並べ替えられていない要素になるまで一時配列を反復処理し、両方の配列から最小要素を見つけて元の配列に格納し、移動を続けます。
-
LeftArrayに要素が残っている場合は、それらを元の配列に格納し、RightArrayについても同じことを行います。
コード例:
class Test {
// function to merge two sorted arrays
static void merge(int arr[], int left, int mid, int right) {
// sizes for temp arrays
int n1 = mid - left + 1;
int n2 = right - mid;
// temp arrays
int LeftArray[] = new int[n1];
int RigthArray[] = new int[n2];
// clone data to temp arrays
for (int i = 0; i < n1; ++i) LeftArray[i] = arr[left + i];
for (int j = 0; j < n2; ++j) RigthArray[j] = arr[mid + 1 + j];
int a = 0, b = 0;
// merging temp arrays to the original array
int k = left;
while (a < n1 && b < n2) {
if (LeftArray[a] <= RigthArray[b]) {
arr[k] = LeftArray[a];
a++;
} else {
arr[k] = RigthArray[b];
b++;
}
k++;
}
// If any elements are left in LeftArray, clone it to the original array
while (a < n1) {
arr[k] = LeftArray[a];
a++;
k++;
}
// If any elements are left in RightArray, clone it to the original array
while (b < n2) {
arr[k] = RigthArray[b];
b++;
k++;
}
}
static void mergeSort(int arr[], int left, int right) {
if (left < right) {
// Find the mid of the array using the left and right
int mid = left + (right - left) / 2;
// sort the first half of the array
mergeSort(arr, left, mid);
// sort the second half of the array
mergeSort(arr, mid + 1, right);
// sort both parts of the array and merge it
merge(arr, left, mid, right);
}
}
public static void main(String args[]) {
int[] arr = {10, 201, -22121, -412, 3, 212121, 50, 30, 20, 1021212};
mergeSort(arr, 0, arr.length - 1);
System.out.println("Sorted array using merge sort is");
for (int a = 0; a < arr.length; a++) {
System.out.print(arr[a] + " ");
}
}
}
出力：
Sorted array is -22121 -412 3 10 20 30 50 201 212121 1021212
Java のマージ ソート アルゴリズムの時間計算量
mergeSort() の時間計算量は O(nlogn) です。ここで、n は配列の長さです。 ここで、merge() 関数の時間計算量は O(n) であり、mergeSort() 関数の時間計算量は O(logn) です。 配列の半分。
| 最良の場合 | O(nlog(n)) |
| 平均ケース | O(nlog(n)) |
| 最悪の場合 | O(nlog(n)) |
Java のマージ ソート アルゴリズムのスペースの複雑さ
ソートされていない要素を格納するために 2つの一時配列を使用するため、マージソートのスペースの複雑さは O(n) です。
この記事では、Java で最も高速なアルゴリズムの 1つであるカウンティング ソート アルゴリズムを、サンプル コードを使用して段階的に学習しました。 また、カウントソートの制限を克服するために、任意の入力範囲で機能するマージソートを学習しました。
