Java のソートアルゴリズム

情報を特定の順序で並べ替えることは、多くの場合、配列のようなフレームワーク内で、情報を配置することです。さまざまなシーケンス要件を使用できます。一般的なものは、数値を最小値から最大値へ、またはその逆に並べ替えたり、文字列を辞書順に並べ替えたりすることです。並べ替えの仕組みに興味がある場合は、非効率的だが直感的な代替案から、Java やその他の言語で効果的に実装された効率的なアルゴリズムまで、さまざまなアルゴリズムを取り上げます。

Java のさまざまな並べ替えアルゴリズム

さまざまな並べ替えアルゴリズムがあり、すべてが同じように効果的であるわけではありません。それらを比較し、どれが最もパフォーマンスが高いかを確認するために、時間計算量を分析します。

広告 このカテゴリーの人気コース JAVA マスタリー - スペシャライゼーション | 78 コース シリーズ | 15 回の模擬テスト

1. 並べ替えの挿入
2. バブルソート
3. 選択並べ替え
4. 並べ替えを結合
5. ヒープソート

1.挿入ソート

挿入ソートの背後にある概念は、範囲をソートされたサブ配列とソートされていないサブ配列に分割します。分類された部分は期間 1 の先頭にあり、配列内の最初 (左側) のコンポーネントと一致します。配列内を移動し、反復ごとに配列の分類された部分を 1 コンポーネントずつ拡張します。展開すると、ソートされたサブ配列に新しい要素が配置されます。これを行うには、最初のコンポーネントを変更する必要がなくなるまで、すべての要素を右に移動します。たとえば、次の配列で太字の部分を昇順にソートすると、次のようになります。

1. 3 5 7 8 4 2 1 9 6: 4 を検討し、これを挿入することが必要です。 8時からシフトしてます> 4
2. 2. 3 5 7 x 8 2 1 9 6
3. 3 5 x 7 8 2 1 9 6
4. 3 x 5 7 8 2 1 9 6
5. 3 4 5 7 8 2 1 9 6

コード:

public class InsertionSortEx {
public static void insertionSort(int[] arr) {
for (int x = 1; x < arr.length; x++) {
int current = arr[x];
int y = x - 1;
while(y >= 0 && current < arr[y]) {
arr[y+1] = arr[y];
y--;
}
arr[y+1] = current;
}
}
public static void main(String a[]){
int[] arr1 = {3,5,7,8,4,2,1,9,6};
System.out.println("Before Sorting");
for(int x:arr1){
System.out.print(x+" ");
}
System.out.println();
insertionSort(arr1);//sorting array using insertion sort
System.out.println("After Insertion Sorting");
for(int x:arr1){
System.out.print(x+" ");
}
}
}

出力:

この方法に従って、1 つのコンポーネントがソートされた部分を拡張しました。要素は 4 つではなく 5 つになりました。すべての反復でこれが行われ、配列全体が末尾でソートされます。

注: これは、反復ごとに分類リスト全体を 1 つずつ転送する必要があるためです (O(n))。これを各テーブルの各コンポーネントに対して行う必要があります。これは、テーブルが O(n^2) で区切られていることを意味します。

2.バブルソート

バブルが必要な順序にない場合は、隣接するコンポーネントを置き換えることによって動作します。これは、すべてのコンポーネントが配列の先頭から順番に揃うまで繰り返されます。スワップなしで反復全体を実行できた場合、隣接する要素と比較したすべての項目が望ましい順序になっており、ひいては配列全体も望ましい順序になっていることがわかります。バブルソートアルゴリズムの理由は、数字のようなものが「地面」に「泡立つ」ためです。特定の量に達した後、インスタンスを再度実行すると (4 が適切な例です)、数値がゆっくりと右に移動していることがわかります。

バブルソートの手順は次のとおりです:

1. 4 21 5 3: ここでは、1^st の 2 つの数値の順序が正しくありません。したがって、両方の数値を並べ替える必要があります。
2. 2 4 15 3: その後、次の数字のペアも正しい順序ではありません。したがって、並べ替えが再び行われます。
3. 2 1 4 53: これら 2 つは正しい順序です。4 <; 5 であるため、交換する必要はありません。
4. 2 1 4 5 3: 繰り返しますが、正しい順序に入れ替える必要があります。
5. 2 1 4 3 5: 1 回の反復後の結果の配列を次に示します。
6. 数字が適切な順序になるまで、このプロセスを再度繰り返す必要があります。

コード:

public class BubbleSortExample {
public static void bubbleSort(int[] arr) {
int n = arr.length;
int tmp = 0;
for(int x=0; x < n; x++){
for(int y=1; y < (n-x); y++){
if(arr[y-1] > arr[y]){
//swap elements
tmp = arr[y-1];
arr[y-1] = arr[y];
arr[y] = tmp;
}
}
}
}
public static void main(String[] args) {
int arr[] ={4,2,1,5,3};
System.out.println("Array Before Bubble Sort");
for(int x=0; x < arr.length; x++){
System.out.print(arr[x] + " ");
}
System.out.println();
bubbleSort(arr);
System.out.println("Array After Bubble Sort");
for(int x=0; x < arr.length; x++){
System.out.print(arr[x] + " ");
}
}
}

出力:

注: a[i]>= a[i+1 ] を使用した場合、無限ループに陥る可能性があります。これは、その接続が同等のコンポーネントで引き続き有効であり、常にコンポーネントを 1 つから交換するためです。要素を別の要素に変換します。

3.選択範囲の並べ替え

選択ソートは、配列をソートされていない分類の配列に分割します。ただし、今回は、ソート部分配列は、ソートされていない部分配列の最小要素をソートされた配列の末尾に交換によって挿入することによって形成されます。

1. 3 5 12 4
2. 15 3 2 4
3. 1 23 5 4
4. 1 2 35 4
5. 1 2 3 45
6. 1 2 3 4 5

コード:

public class SelectionSortEx {
public static void selectionSort(int[] arr){
for (int x = 0; x < arr.length - 1; x++)
{
int indx = x;
for (int y = x + 1; y < arr.length; y++){
if (arr[y] < arr[indx]){
indx = y;
}
}
int smallNumber = arr[indx];
arr[indx] = arr[x];
arr[x] = smallNumber;
}
}
public static void main(String a[]){
int[] arr1 = {3,5,1,2,4};
System.out.println("Before Sorting");
for(int x:arr1){
System.out.print(x+" ");
}
System.out.println();
selectionSort(arr1);
System.out.println("After Selection Sorting");
for(int x:arr1){
System.out.print(x+" ");
}
}
}

出力:

Note: The minimum is O(n) for the array size because all the components must be checked. For each element of the array, we must find the minimum and make the whole process O (n^2) limited.

4. Merge Sort

Merge Sort utilizes recursion to fix the issue of the divide and conquest method more effectively than earlier described algorithms.

This tree shows how the recursive calls function. Down arrow marked arrays are the arrays for which we call function while we fuse up arrow arrays. Then you follow the arrow to the tree’s edge and then return and merge. We’ve got 3 5 3 1 range, so we split it into 3 5 4 and 2 1. We split them into their parts in order to sort them. We begin fusioning and sorting them as we go when we get to the bottom.

Code:

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
public class MergeSort {
static void merge(int[] array,int lowval,int midval,int highval){
int x, y ,k;
int[] c= new int[highval-lowval+1];
k = 0;
x=lowval;
y=midval+1;
while(x<=midval && y<=highval){
if(array[x]<=array[y]){
c[k++] = array[x++];
}
else{
c[k++] = array[y++];
}
}
while(x<=midval){
c[k++] = array[x++];
}
while(y<=highval){
c[k++] = array[y++];
}
k=0;
for(x = lowval; x<=highval; x++){
array[x] = c[k++];
}
}
static void mergeSort(int[] array,int lowval, int highval){
if(highval-lowval+1>1){
int midval = (lowval+highval)/2;
mergeSort(array,lowval,midval);
mergeSort(array,midval+1,highval);
merge(array,lowval,midval,highval);
}
}
public static void main(String[] args) {
BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
int size;
System.out.println("Enter the array");
try {
size = Integer.parseInt(r.readLine());
} catch (Exception e) {
System.out.println("Please Enter valid Input");
return;
}
int[] array = new int[size];
System.out.println("Enter array elements");
int x;
for (x = 0; x < array.length; x++) {
try {
array[x] = Integer.parseInt(r.readLine());
} catch (Exception e) {
System.out.println("An error Occurred");
}
}
System.out.println("After Sorting");
System.out.println(Arrays.toString(array));
mergeSort(array,0,array.length-1);
System.out.println("Before Merge Sorting");
System.out.println(Arrays.toString(array));
}
}

In this program, we have asked the user to enter input. The output will be in sorted order based on the user’s input.

Output:

5. Heap Sort

You first must know the framework on which Heapsort operates-the heap-in order to comprehend why it operates. We will specifically speak about a binary heap, but you can also generalize this to other heap constructions. A heap is a tree that fulfills the property of the heap, namely that all its kids have relationships to each node. A heap must also be nearly finished. A near-complete d-depth binary has a d-1 subtree with the same root, and each node has a full, left subtree, with a left descending.

In other words, you get a lower and lower number (min-heap) or larger and bigger (max-heap) when moving down the tree. Here is a max-heap instance:

1. 6 1 8 3 5 2 4: Here, Both children’s numbers are smaller than the parent; hence we do not have to change anything.
2. 6 1 8 3 52 4: Here, 5 > 1, we need to swap them. We need to heapify for 5.
3. 6 5 8 3 12 4: Both of the children’s numbers are smaller; everything remains the same.
4. 6 5 83 1 2 4: Here, 8 > 6, hence we should swap them.
5. 8 5 6 3 1 2 4: After this iteration, we will get this result.

After Repeating this process again, we will get the following results:

• 8 5 6 3 1 2 4
1. 4 5 6 3 1 2 8: Swapping
2. 6 5 4 3 1 2 8: Heapify
3. 2 5 4 3 1 6 8: Swapping
4. 5 2 4 2 1 6 8: Heapify
5. 1 2 4 2 5 6 8: Swapping

Code:

public class HeapSort
{
public void sort(int arr[])
{
int n = arr.length;
for (int x = n / 2 - 1; x >= 0; x--)
heapify(arr, n, x);
for (int x=n-1; x>=0; x--)
int tmp = arr[0];
arr[0] = arr[x];
arr[x] = tmp;
heapify(arr, x, 0);
}
}
void heapify(int arr[], int n, int x)
{
int largest = x;
int L = 2*x + 1;
int r = 2*x + 2;
if (L < n && arr[L] > arr[largest])
largest = L;
if (r < n && arr[r] > arr[largest])
largest = r;
if (largest != x)
{
int swap = arr[x];
arr[x] = arr[largest];
arr[largest] = swap;
heapify(arr, n, largest);
}
}
static void printArray(int arr[])
{
int n = arr.length;
for (int x=0; x<n; ++x)
System.out.print(arr[x]+" ");
System.out.println();
}
public static void main(String args[])
{
int arr[] = {6,1,8,3,5,2,4};
int n = arr.length;
System.out.println("Before Sorting:");
printArray(arr);
HeapSort ob = new HeapSort();
ob.sort(arr);
System.out.println("After Heap Sorting:");
printArray(arr);
}
}

Output:



You can view it from point to level of the graph, from left to right. We achieved here that when we have the kth component in the array, the position of its children is 2\*k+1 and 2\*k+2 (assuming that indexing begins at 0). You can monitor this. The position of the parent is always (k-1)/2 for the kth component. You can readily “max heap up” any range because you know that. Check whether one of its kids is lower than that for each component. If so, pair one parent and repeat this step recursively with the parent.

Note: Since iterating for-loops across the entire array makes heapSort) (obviously O(N), it would create Heapsort O’s overall complexity(nlog n). Heapsort has an on-the-spot type, which means that it requires O(1) more room than Merge Sort, but it has some disadvantages, such as parallels that are hard.

Conclusion – Sorting Algorithms in Java

Sorting is a very prevalent procedure with datasets, whether for further analysis, speeding search with more effective algorithms relying on sorted information, filtering information, etc. Several languages endorse sorting, and often the interfaces obscure what the programmer does.

以上がJava のソートアルゴリズムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。