Bubble sort class in Java

Question

I have written this class which sorts the array using bubble sort. Please let me know how can I improve it. (I don't like recurrent code in if/else statement)

public class BubbleSort {
public static void numbers(int[] array){
 numbers(array, '<');
}
public static void numbers(int[] array, char direction){
 if(direction == '<'){
 for(int i = 0; i < array.length - 1; i++){
 for(int j = 0; j < array.length - i - 1; j++){
 if(array[j] < array[j + 1]){
 int tmp = array[j];
 array[j] = array[j+1];
 array[j+1] = tmp;
 }
 }
 }
 }
 else{
 for(int i = 0; i < array.length - 1; i++){
 for(int j = 0; j < array.length - i - 1; j++){
 if(array[j] > array[j + 1]){
 int tmp = array[j];
 array[j] = array[j+1];
 array[j+1] = tmp;
 }
 }
 }
 }
}
public static void letters(char[] array){
 letters(array, '<');
}
public static void letters(char[] array, char direction){
 if(direction == '<'){
 for(int i = 0; i < array.length - 1; i++){
 for(int j = 0; j < array.length - i - 1; j++){
 if(array[j] < array[j + 1]){
 char tmp = array[j];
 array[j] = array[j+1];
 array[j+1] = tmp;
 }
 }
 }
 }
 else{
 for(int i = 0; i < array.length - 1; i++){
 for(int j = 0; j < array.length - i - 1; j++){
 if(array[j] > array[j + 1]){
 char tmp = array[j];
 array[j] = array[j+1];
 array[j+1] = tmp;
 }
 }
 }
 }
} 
}

Answer 1

Bubble Sort has an inefficient worst case. In general, you could speed things up by switching from this \$O(n^2)\$ sort to one of the \$O(n \log n)\$ sorts, e.g. Quicksort. Simplest would be to just use Arrays.sort but perhaps this is a programming exercise (tagging as reinventing-the-wheel would let reviewers know that).

 for(int i = 0; i < array.length - 1; i++){
 for(int j = 0; j < array.length - i - 1; j++){
 if(array[j] < array[j + 1]){
 int tmp = array[j];
 array[j] = array[j+1];
 array[j+1] = tmp;
 }
 }
 }

The one thing that Bubble Sort can do well is handle sorted input efficiently in \$O(n)\$ time. But you don't do that.

 for (int i = 0; i < array.length - 1; i++) {
 boolean bubbled = false;
 for (int j = 0; j < array.length - i - 1; j++) {
 if (array[j] < array[j + 1]){
 int tmp = array[j];
 array[j] = array[j+1];
 array[j+1] = tmp;
 bubbled = true;
 }
 }
 if (!bubbled) {
 return;
 }
 }

Now it will return after a single pass if the input is sorted. If the input is almost sorted, it may return on the second or third pass.

You can save a calculation an outer loop iteration if you're really trying to optimize.

 for (int i = array.length - 1; i > 0; i--) {
 boolean bubbled = false;
 for (int j = 0; j < i; j++) {
 if (array[j] < array[j + 1]){
 int tmp = array[j];
 array[j] = array[j+1];
 array[j+1] = tmp;
 bubbled = true;
 }
 }
 if (!bubbled) {
 return;
 }
 }

Now you don't have to calculate array.length - 1 - i on every outer iteration.

Note that a naive compiler might actually calculate that on each inner iteration in the original code.

Answer 2

You can remove the outer condition and put it into the inner loop. This will cause it to be calculated O(n^2) times instead of once, but you'll have one copy of your main code:
(edited! inner condition fixed)

 public static void numbers(int[] array, char direction){
 for(int i = 0; i < array.length - 1; i++){
 for(int j = 0; j < array.length - i - 1; j++){
 if(direction == '<' && array[j] < array[j + 1]
 ||
 direction == '>' && array[j] > array[j + 1]){
 int tmp = array[j];
 array[j] = array[j+1];
 array[j+1] = tmp;
 }
 }
 }
 }
 }

• GRO: This if condition isn't working because ((true && false) || true)(this condition is always true) and I don't think is good choice make code cleaner for slower algorithm.
• CiaPan: @GRO Of course, you are right! I apology, should not have posted in a hurry.
• CiaPan: Apologize. Still in hurry :-(

Answer 3

You could just sort in one direction, then check if required direction is the opposite. If yes, then reverse the existing array.

public static void numbers(int[] array, char direction){
 for(int i = 0; i < array.length - 1; i++){
 for(int j = 0; j < array.length - i - 1; j++){
 if(array[j] < array[j + 1]){
 int tmp = array[j];
 array[j] = array[j+1];
 array[j+1] = tmp;
 }
 }
 }
 if(direction=='>'){
 var reverseArray=array.clone();
 Collections.reverse(Array.asList(reverseArray));
 }
 // Now you have your ascending order in 'array' and descending order in 'reverseArray'.
}