When I surfed the internet, I happened to find the following URL, so I wanted to study bubble sort.
URL:http://www.mkyong.com/java/java-bubble-sort-example/
Bubble sort is the simplest sorting algorithm, it compares the first two elements, if the first is greater than the second, swaps them, continues doing (compares and swaps) for the next pair of adjacent elements. It then starts again with the first two elements, compares, swaps until no more swaps are required.
-> Compare the values of two adjacent elements in the array Alignment algorithm that exchanges according to conditions (whether the value is large or small)
For example If the input is 1597253, The output is 1235579 depending on the program that implements bubble sort.
I thought about the algorithm I would implement, First, Compare the size of the first number and the second number from the left side, If the number on the left is large-> Swap the position with the number on the right If the number on the right is large-> you don't have to replace it
Also, Compare the size of the second and the third, Decide whether to replace the position or not, In the same way 3rd VS 4th, 4th VS 5th. .. .. Compared to the 6th and 7th sizes, the first round is over.
And The second round begins. Compare the size with the first and second, Compare the sizes of the second and third. .. .. In the same way, compare the size with the 6th and 7th, The second round is over.
In the same flow As it is, the third round and the fourth round. .. .. The last is the sixth round
public class BubbleSort {
public static void main(String[] args) {
int[] test = new int[]{2, 1, 3, 2, 5, 4};
int[] a= sort(test);
for(int t:a){
System.out.print(t);
}
}
static int[] sort(int[] input){
int length = input.length; // array length // IF Number before> Number after //数字の位置を交換する際、前の数字を暫く保存するためのVariable int temp;
//配列の中各数字を比べる必要があり、 // You also need to execute each round written above and write a double loop for(int i=0;i<length;i++){
for(int j=0;j<length-1;j++){
// if before> after exchange position if(input[j]>input[j+1]){
temp = input [j]; // Save the previous number to Variable for a while input [j] = input [j + 1]; // Move the last number to the position of the previous number input [j + 1] = temp; // Move the previous number (saved in Variable) to the back
}
}
}
return input;
}
}
test results:
122345, accurate
Calculate the number of exchanges of numbers by doing the following ・ Calculate and print the number of times to exchange the position of numbers -Print the array after replacement
static int[] sort(int[] input){
int count = 0;
int length = input.length;
int temp;
for(int i=0;i<length;i++){
for(int j=0;j<length-1;j++){
if(input[j]>input[j+1]){
temp = input[j];
input[j] = input[j+1];
input[j+1] = temp;
count++;
//交換後の配列の元素をプリント System.out.print("count:" + count + " "); for(int a:input){ System.out.print(a); } System.out.println();
}
}
}
System.out.println(count);
return input;
}
Output：
count:1 123254 count:2 122354 count:3 122345
3 = Number of exchanges:
In the worst case, The order of the numbers in the array is 543221, and it is always exchanged when comparing the size of the numbers. Since there are 6 numbers in the array, the number of exchanges is First round: 5 Second round: 4 Third round: 3 Fourth round: 2 Fifth round: 1 Total: 15
By the way, In this case, the number of comparisons and the number of exchanges are the same.
I noticed one here, The program I wrote above is actually inefficient.
The cause is Although the array is already in ascending order There is still the possibility of comparing the size of the numbers.
You can find out by calculating the number of comparisons.
public class BubbleSort {
public static void main(String[] args) {
int[] test = new int[]{2, 1, 3, 2, 5, 4};
int[] a= sort(test);
for(int t:a){
System.out.print(t);
}
}
static int[] sort(int[] input){
int length = input.length; // array length // IF Number before> Number after //数字の位置を交換する際、前の数字を暫く保存するためのVariable int temp;
//比較回数を計算用 int count = 0;
//配列の中各数字を比べる必要があり、 //上記書いた各ラウンドも実行する必要があり二重ループを書く for(int i=0;i<length;i++){
for(int j=0;j<length-1;j++){
//数字大きさ比較する際、配列の元素をプリント count++; System.out.print("count:" + count + " "); for(int a:input){ System.out.print(a); } System.out.println();
// if before> after exchange position if(input[j]>input[j+1]){
temp = input [j]; // Save the previous number to Variable for a while input [j] = input [j + 1]; // Move the last number to the position of the previous number input [j + 1] = temp; // Move the previous number (saved in Variable) to the back
}
}
}
return input;
}
}
Output:
count:1 213254 count:2 123254 count:3 123254 count:4 122354 count:5 122354 count:6 122345 count:7 122345 count:8 122345 count:9 122345 count:10 122345 count:11 122345 count:12 122345 count:13 122345 count:14 122345 count:15 122345 count:16 122345 count:17 122345 count:18 122345 count:19 122345 count:20 122345 count:21 122345 count:22 122345 count:23 122345 count:24 122345 count:25 122345 count:26 122345 count:27 122345 count:28 122345 count:29 122345 count:30 122345 122345
Even though the sequences are already in ascending order after comparing three times The program is still ongoing and inefficient.
The solution is Check if the array is in ascending order.
Check the method with the URL and Variable with boolean is_sorted; was used.
Looking at the explanation, // is sorted? then break it, avoid useless loop. If the situation is sorted, terminate the program and Avoid unnecessary loops.
public class BubbleSort {
public static void main(String[] args) {
int[] test = new int[]{2, 1, 3, 2, 5, 4};
int[] a= sort(test);
for(int t:a){
System.out.print(t);
}
}
static int[] sort(int[] input){
int length = input.length; // array length // IF Number before> Number after //数字の位置を交換する際、前の数字を暫く保存するためのVariable int temp;
//比較回数を計算用 int count = 0;
Boolean is_sorted;
//配列の中各数字を比べる必要があり、 //上記書いた各ラウンドも実行する必要があり二重ループを書く for(int i=0;i<length;i++){
//ラウンドが始まる前にTrueに設定、もし比較する行為をしない場合ループ終止 is_sorted = true;
for(int j=0;j<length-1;j++){
//数字大きさ比較する際、配列の元素をプリント count++; System.out.print("count:" + count + " "); for(int a:input){ System.out.print(a); } System.out.println();
// if before> after exchange position if(input[j]>input[j+1]){
temp = input [j]; // Save the previous number to Variable for a while input [j] = input [j + 1]; // Move the last number to the position of the previous number input [j + 1] = temp; // Move the previous number (saved in Variable) to the back
//交換行為をしたらFalseに変更、 //配列がまだ昇順になってないとのこと is_sorted = false;
}
}
if (is_sorted) break;
}
return input;
}
}
Output： count:1 213254 count:2 123254 count:3 123254 count:4 122354 count:5 122354 count:6 122345 count:7 122345 count:8 122345 count:9 122345 count:10 122345 122345
If there are N numbers At least N comparisons in the first round The number of comparisons in the second round is at least N times
Time complexity (worst case) = O (n²)
Others: If I'm a foreigner and the Japanese expression is strange, I would be grateful if you could tell me.
2019/2/16 Corrected the time complexity and the number of comparisons of numbers with the algorithm I thought of.
Recommended Posts