Implementing bubble sort in Java

There are quite a large number of sorting algorithms, many of them are very specific and were developed to solve a narrow range of problems and work with specific types of data. But among all this diversity, the simplest algorithm is deservedly bubble sort, which can be implemented in any programming language. Despite its simplicity, it underlies many rather complex algorithms. Another equally important advantage is its simplicity, and, therefore, it can be remembered and implemented immediately, without having any additional literature in front of you.

Introduction

The entire modern Internet consists of a huge number of different types of data structures collected in databases. They store all kinds of information, from personal data of users to the semantic core of highly intelligent automated systems. Needless to say, data sorting plays an extremely important role in this huge amount of structured information. Sorting can be a mandatory step before searching for any information in the database, and knowledge of sorting algorithms plays a very important role in programming.

Sorting through machine eyes and human eyes

Let's imagine that you need to sort 5 columns of different heights in ascending order. These columns can mean any kind of information (stock prices, communication channel bandwidth, etc.); you can present some of your own versions of this task to make it more clear. Well, as an example, we will sort the Avengers by height: Unlike a computer program, sorting will not be difficult for you, because you are able to see the whole picture and can immediately figure out which hero needs to be moved where in order for the sorting by height to be completed successfully. You probably already guessed that to sort this data structure in ascending order, just swap the places of the Hulk and Iron Man:

Done!

And this will complete the sorting successfully. However, the computer, unlike you, is somewhat stupid and does not see the entire data structure as a whole. Its control program can only compare two values ​​at one time. To solve this problem, she will have to place two numbers in her memory and perform a comparison operation on them, and then move on to another pair of numbers, and so on until all the data has been analyzed. Therefore, any sorting algorithm can be very simplified in the form of three steps:

• Compare two elements;
• Swap or copy one of them;
• Go to next element;

Different algorithms can perform these operations in different ways, but we will move on to consider how bubble sort works.

Bubble Sort Algorithm

Bubble sorting is considered the simplest, but before describing this algorithm, let's imagine how you would sort the Avengers by height if you could, like a machine, compare only two heroes with each other in one period of time. Most likely, you would do the following (most optimally):

• You move to element zero of our array (Black Widow);
• Compare the zero element (Black Widow) with the first (Hulk);
• If the element at position zero is higher, you swap them;
• Otherwise, if the element at position zero is smaller, you leave them in their places;
• Move to a position to the right and repeat the comparison (compare the Hulk with the Captain)

After you go through the entire list in one pass with such an algorithm, the sorting will not be completed completely. But on the other hand, the largest element in the list will be moved to the far right position. This will always happen, because as soon as you find the largest element, you will constantly change places until you move it to the very end. That is, as soon as the program “finds” the Hulk in the array, it will move him further to the very end of the list: This is why this algorithm is called bubble sort, because as a result of its operation, the largest element in the list will be at the very top of the array, and all smaller elements will be shifted one position to the left: To complete the sort, you will need to return to the beginning of the array and repeat the five steps described above again, again moving from left to right, comparing and moving elements as necessary. But this time you need to stop the algorithm one element before the end of the array, because we already know that the largest element (Hulk) is absolutely in the rightmost position: So the program must have two loops. For greater clarity, before we move on to reviewing the program code, you can see a visualization of how bubble sort works at this link: Visualization of how bubble sort works

Implementation of bubble sort in Java

To demonstrate how sorting works in Java, here is the program code:

• creates an array of 5 elements;
• uploads the rise of the avengers into it;
• displays the contents of the array;
• implements bubble sort;
• re-displays the sorted array.

You can view the code below, and even download it into your favorite IntelliJ IDE. It will be analyzed below:

class ArrayBubble{
    private long[] a;   // array reference
    private int elems;  //number of elements in the array

    public ArrayBubble(int max){    //class constructor
        a = new long[max];          //create an array with size max
        elems = 0;                  //when created, the array contains 0 elements
    }

    public void into(long value){   // method for inserting an element into an array
        a[elems] = value;           //insert value into array a
        elems++;                    //array size increases
    }

    public void printer(){          // method for outputting an array to the console
        for (int i = 0; i < elems; i++){    //for each element in the array
            System.out.print(a[i] + " ");   // output to console
            System.out.println("");         //a new line
        }
        System.out.println("----End array output----");
    }

    private void toSwap(int first, int second){ //method swaps a pair of array numbers
        long dummy = a[first];      // put the first element into a temporary variable
        a[first] = a[second];       // put the second element in place of the first
        a[second] = dummy;          //instead of the second element, write the first from temporary memory
    }

    public void bubbleSorter(){     //МЕТОД ПУЗЫРЬКОВОЙ СОРТИРОВКИ
        for (int out = elems - 1; out >= 1; out--){  //Outer loop
            for (int in = 0; in < out; in++){       //Inner loop
                if(a[in] > a[in + 1])               //If the order of the elements is wrong
                    toSwap(in, in + 1);             // call the swapping method
            }
        }
    }
}

public class Main {
    public static void main(String[] args) {
        ArrayBubble array = new ArrayBubble(5); //Create array array with 5 elements

        array.into(163);       //fill the array
        array.into(300);
        array.into(184);
        array.into(191);
        array.into(174);

        array.printer();            //display elements before sorting
        array.bubbleSorter();       //ИСПОЛЬЗУЕМ ПУЗЫРЬКОВУЮ СОРТИРОВКУ
        array.printer();            // print the sorted list again
    }
}

Despite the detailed comments in the code, we provide a description of some of the methods presented in the program. The key methods that carry out the main work in the program are written in the ArrayBubble class. The class contains a constructor and several methods:

• into– method of inserting elements into an array;
• printer– displays the contents of the array line by line;

• toSwap– rearranges elements if necessary. To do this, a temporary variable is used dummy, into which the value of the first number is written, and in place of the first number the value from the second number is written. The contents from the temporary variable are then written to the second number. This is a standard technique for swapping two elements;

  and finally the main method:

• bubbleSorter– which does the main work and sorts the data stored in the array, we will present it separately again:

  public void bubbleSorter(){     //МЕТОД ПУЗЫРЬКОВОЙ СОРТИРОВКИ
      for (int out = elems - 1; out >= 1; out--){  //Outer loop
          for (int in = 0; in < out; in++){       //Inner loop
              if(a[in] > a[in + 1])               //If the order of the elements is wrong
                  toSwap(in, in + 1);             // call the swapping method
          }
      }
  }

Here you should pay attention to two counters: external outand internal in. The external counterout starts enumerating values ​​from the end of the array and gradually decreases by one with each new pass. outWith each new pass, the variable is shifted further to the left so as not to affect the values ​​already sorted to the right side of the array. The internal counterin starts enumerating values ​​from the beginning of the array and gradually increases by one on each new pass. The increase inoccurs until it reaches out(the last analyzed element in the current pass). The inner loop incompares two adjacent cells inand in+1. If ina greater number is stored in than in+1, then the method is called toSwap, which swaps the places of these two numbers.

Conclusion

The bubble sort algorithm is one of the slowest. If the array consists of N elements, then N-1 comparisons will be performed on the first pass, N-2 on the second, then N-3, etc. That is, the total number of passes will be made: (N-1) + (N-2) + (N-3) + … + 1 = N x (N-1)/2 Thus, when sorting, the algorithm performs about 0.5x(N ^2) comparisons. For N = 5, the number of comparisons will be approximately 10, for N = 10 the number of comparisons will increase to 45. Thus, as the number of elements increases, the complexity of sorting increases significantly: The speed of the algorithm is affected not only by the number of passes, but also by the number of permutations that need to be made. For random data, the number of permutations averages (N^2) / 4, which is about half as much as the number of passes. However, in the worst case, the number of permutations can also be N^2 / 2 - this is the case if the data is initially sorted in reverse order. Despite the fact that this is a rather slow sorting algorithm, it is quite important to know and understand how it works, and, as mentioned earlier, it is the basis for more complex algorithms. Jgd!