# 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