Optimize bubble sorting (JAVA)

algorithm

As the most basic and simple sorting algorithm, bubble sorting is essentially a comparison between two adjacent elements. If it is ordered, it will skip, if it is out of order, it will exchange. At most, n-1 sorting is required, and n-i comparison is required for the i-th. So the time complexity is o(n*n), which is a sort algorithm with low efficiency. But for beginners, it is an algorithm that must be mastered.
There is a little improvement in bubble sorting, which may not be noticed by beginners. When the sequence has been ordered as a whole, there is no need to make unnecessary comparisons. A boolean variable can be set to jump out of the loop directly when there is no exchange after a trip, which can improve the sorting efficiency.

Codes

package com.fairy.InnerSort;

import java.util.Scanner;
/**
 * Bubble sorting
 * @author Fairy2016
 *
 */
public class BubbleSort {
    
    public static void sort(int a[], int n) {
        boolean flag = false;
        for(int i = 1; i <= n-1; i++) {
            flag = false;
            for(int j = 1; j <= n-i; j++) {
                if(a[j] > a[j+1]) {
                    //Exchange a[j] and a[j+1]
                    a[0] = a[j];
                    a[j] = a[j+1];
                    a[j+1] = a[0];
                    //Tag swapped
                    flag = true;
                }
            }
            //If no exchange occurs, exit directly and the sorting is completed
            if(!flag) {
                break;
            }
        }
    }

    public static void Print(int a[], int n) {
        for(int i = 1; i <= n; i++) {
            System.out.print(a[i]+" ");
        }
    }

    public static void main(String args[]) {
        int n;
        int a[];
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNext()) {
            n = scanner.nextInt();
            if(n > 0) {
                a = new int[n+1];
                for(int i=1; i <= n; i++) {
                    a[i] = scanner.nextInt();
                }
                sort(a, n);
                Print(a, n);
            }
        }
        scanner.close();
    }
}

Tags: Java

Posted on Mon, 04 May 2020 21:38:05 -0700 by russellpehrson