There are a fairly 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 variety, the simplest algorithm is deservedly bubble sort, which can be implemented in any programming language. Despite its simplicity, it underlies many fairly complex algorithms. Its other no less important advantage is its simplicity, and, therefore, it can be remembered and implemented immediately, without having any additional literature before your eyes.
Unlike a computer program, sorting will not be difficult for you, because you are able to see the whole picture and immediately be able to figure out which hero needs to be moved where in order for sorting by height to be successful. You probably already guessed that to sort this data structure in ascending order, it is enough to swap the Hulk and Iron Man:
is somewhat dumb 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 put 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:
After you go through the entire list with such an algorithm in one pass, the sorting will not be done completely. But instead, the largest element in the list will be moved to the rightmost position. This will always happen, because as soon as you find the largest element, you will keep changing its 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:
That is why this algorithm is called bubble sort, because as a result of its work, the largest element in the list is 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 above five steps 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 exactly in the rightmost position:
So the program should have two loops. For more clarity, before we move on to the consideration of the program code, follow this link to see the visualization of the work of bubble sort: Visualization of the work of bubble sort
IntelliJ IDE. It will be parsed below:
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 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, besides, as mentioned earlier, it is the basis for more complex algorithms. jgd!
Introduction
The entire modern Internet is a huge number of different types of data structures collected in databases. They store all sorts of information, from personal user data 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 looking up any information in the database, and knowledge of sorting algorithms is extremely important 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 version of this task to make it more clear. Well, we, as an example, will sort the Avengers by height:Done!
And on this sorting will be successfully completed. However, the computer, unlike you,- Compare two elements;
- Swap or copy one of them;
- Move to the next element;
Bubble sort algorithm
Bubble sort 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 at one time. You would most likely do the following (best practice):- You move to the zero element 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 where they are;
- Make a transition to the position to the right and repeat the comparison (compare the Hulk with the Captain)
Implementation of Bubble Sort in Java
To demonstrate how sorting works in Java, here is a program code that:- creates an array with 5 elements;
- loads into it the growth of the avengers;
- displays the contents of the array;
- implements bubble sort;
- re-displays the sorted array.
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 will describe 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. For this, a temporary variable is useddummy
, in which the value of the first number is written, and the value from the second number is written in place of the first. After that, the contents of the temporary variable is written to the second number. This is the standard trick of swapping two elements;and finally the main method:
-
bubbleSorter
- which does the main work and sorts the data stored in the array, we will give it again separately: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 } } }
out
, and internal in
. The external counterout
starts iterating over values from the end of the array and gradually decreases by one with each new pass. The variable out
is shifted to the left with each new pass so as not to affect the values already sorted to the right side of the array. The internal counterin
starts iterating over values from the beginning of the array and gradually increases by one on each new pass. The increment in
continues until it reaches out
(the last parsed element in the current pass). The inner loop in
compares two neighboring cells in
and in+1
. If in
a larger number is stored in than inin+1
, then the method is called toSwap
, which swaps these two numbers.
GO TO FULL VERSION