Bubble sort of exchange sort (java)

Posted Jun 26, 20202 min read

Bubble sort of exchange sort(java)

Blog description

The information involved in the article comes from the Internet collation and personal summary, which means personal learning and experience summary. If there is any infringement, please contact me to delete, thank you!

Description

The basic idea of Bubble Sorting is to compare the values of adjacent elements in sequence by treating the sequence from front to back(starting from the element with the smaller subscript), and exchange if there is a reverse order to make the element with the larger value Gradually move from the front to the back, like a bubble under the water gradually rising upwards.

Code

package cn.guizimo.sort;

import java.util.Arrays;

public class BubbleSort {
    public static void main(String[]args) {
        int arr[]= {3, 9, -1, 10, -2};
        int temp = 0;
        for(int i = 0; i <arr.length-1; i++) {
            for(int j = 0; j <arr.length-1-i; j++) {
                if(arr[j]> arr[j + 1]) {
                    temp = arr[j];
                    arr[j]= arr[j + 1];
                    arr[j + 1]= temp;
                }
            }
            System.out.println("No."+(i+1)+"Lay sorted array");
            System.out.println(Arrays.toString(arr));
        }
    }
}
Test

image-20200626211951798

Optimization

Reduce the number of exchanges that have never occurred

package cn.guizimo.sort;

import java.util.Arrays;

public class BubbleSort {
    public static void main(String[]args) {
        int arr[]= {3, 9, -1, 10, -2};
        System.out.println("Before sorting");
        System.out.println(Arrays.toString(arr));
        bubbledSort(arr);
        System.out.println("After sorting");
        System.out.println(Arrays.toString(arr));
    }

    public static void bubbledSort(int[]arr){
        int temp = 0;
        boolean flag = false; //The flag, whether the exchange occurs
        for(int i = 0; i <arr.length-1; i++) {
            for(int j = 0; j <arr.length-1-i; j++) {
                if(arr[j]> arr[j + 1]) {
                    flag = true;
                    temp = arr[j];
                    arr[j]= arr[j + 1];
                    arr[j + 1]= temp;
                }
            }
            if(!flag){ //No exchange occurs
                break;
            }else {
                //The next exchange
                flag = false;
            }
        }
    }
}
Test

image-20200626212910608

Test speed

package cn.guizimo.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

public class BubbleSort {
    public static void main(String[]args) {
        int max = 80000;
        int[]arr = new int[max];
        for(int i = 0; i <max; i++) {
            arr[i]=(int)(Math.random() * 8000000);
        }
        long date1 = System.currentTimeMillis();
        bubbledSort(arr);
        long date2 = System.currentTimeMillis();
        System.out.println("bubble sort"+max+"array time:"+(date2-date1));

    }

    public static void bubbledSort(int[]arr){
        int temp = 0;
        boolean flag = false; //The flag, whether the exchange occurs
        for(int i = 0; i <arr.length-1; i++) {
            for(int j = 0; j <arr.length-1-i; j++) {
                if(arr[j]> arr[j + 1]) {
                    flag = true;
                    temp = arr[j];
                    arr[j]= arr[j + 1];
                    arr[j + 1]= temp;
                }
            }
            if(!flag){ //No exchange occurs
                break;
            }else {
                //The next exchange
                flag = false;
            }
        }
    }
}

image-20200626214021562

Running time is related to own computer

thank

Shang Silicon Valley

Universal Network

And hardworking self