https://en.wikipedia.org/wiki/Sorting
algorithm#Bubble
sort[Bubble__sort[バブルソート]は、最も単純なソートアルゴリズムで、最初の2つの要素を比較し、最初の要素が2番目の要素よりも大きい場合は2番目の要素を比較し、2番目の要素をスワップし、 ）を次の隣接する要素のペアに適用します。最初の2つの要素で比較を開始し、スワップが必要なくなるまでスワップします。
1.説明
#unsorted data ->[99, 88, 55, 77, 1, 66]
#1 iteration.
#1.1 ->[, , 55, 77, 1, 66]->[, , 55, 77, 1, 66]#1.2 ->[88, , , 77, 1, 66]->[88, , , 77, 1, 66]#1.3 ->[88, 55, , , 1, 66]->[88, 55, , , 1, 66]#1.4 ->[88, 55, 77, , , 66]->[88, 55, 77, , , 66]#1.5 ->[88, 55, 77, 1, ,]->[88, 55, 77, 1, ,]
#2 iteration.
#2.1 ->[, , 77, 1, 66, 99]->[, , 77, 1, 66, 99]#2.2 ->[55, , , 1, 66, 99]->[55, , , 1, 66, 99]#2.3 ->[55, 77, , , 66, 99]->[55, 77, , , 66, 99]#2.4 ->[55, 77, 1, , , 99]->[55, 77, 1, , , 99]
#3 iteration.
#3.1 ->[, , 1, 66, 88, 99]->[55, 77, 1, 66, 88, 99]{no swap}
#3.2 ->[55, , , 66, 88, 99]->[55, , , 66, 88, 99]#3.3 ->[55, 1, , , 88, 99]->[55, 1, , , 88, 99]
#4 iteration.
#4.1 ->[, , 66, 77, 88, 99]->[, , 66, 77, 88, 99]#4.2 ->[, , 66, 77, 88, 99]->[1, 55, 66, 77, 88, 99]{no swap}
#5 iteration.
#5.1 ->[, , 66, 77, 88, 99]-> is__sorted = true, break;
Javaバブルソートの実装は次のとおりです。
public static void sort(int[]input) {
int inputLength = input.length;
int temp;
boolean is__sorted;
for (int i = 0; i < inputLength; i++) {
is__sorted = true;
for (int j = 1; j < (inputLength - i); j++) {
if (input[j - 1]> input[j]) {
temp = input[j - 1];
input[j - 1]= input[j];
input[j]= temp;
is__sorted = false;
}
}
//is sorted? then break it, avoid useless loop.
if (is__sorted) break;
System.out.println("\n");
}
}
2. Javaバブルソートの例
バブルソートアルゴリズムを使用して単純なデータセットをソートし、昇順または降順をサポートする方法を示す完全な例。
BubbleSortExample.java
package com.mkyong;
import java.util.Arrays;
import java.util.stream.Collectors;
public class BubbleSortExample{
public static void main(String[]args) {
int[]array = {99, 88, 55, 77, 1, 66};
System.out.print("unsorted data: ");
printArray(array);
System.out.print("ascending order: ");//1,55,66,77,88,99
bubble__sort(array);
printArray(array);
System.out.print("descending order: ");//99,88,77,66,55,1
bubble__sort(array, false);
printArray(array);
}
private static void bubble__sort(int[]input) {
bubble__sort(input, true);
}
private static void bubble__sort(int[]input, boolean ascending) {
int inputLength = input.length;
int temp;
boolean is__sorted;
for (int i = 0; i < inputLength; i++) {
is__sorted = true;
for (int j = 1; j < (inputLength - i); j++) {
if (ascending) {
if (input[j - 1]> input[j]) {
temp = input[j - 1];
input[j - 1]= input[j];
input[j]= temp;
is__sorted = false;
}
} else {
if (input[j - 1]< input[j]) {
temp = input[j - 1];
input[j - 1]= input[j];
input[j]= temp;
is__sorted = false;
}
}
}
//is sorted? then break it, avoid useless loop.
if (is__sorted) break;
}
}
private static void printArray(int[]data) {
String result = Arrays.stream(data)
.mapToObj(String::valueOf)
.collect(Collectors.joining(","));
System.out.println(result);
}
}
出力
unsorted data: 99,88,55,77,1,66 ascending order: 1,55,66,77,88,99 descending order: 99,88,77,66,55,1
