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.
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. 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.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: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:
Done!
And on this sorting will be successfully completed. However, the computer, unlike you, 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 should put two numbers into 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;
- 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)
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
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.
- into - method for inserting elements into an array;
- printer - displays the contents of the array line by line;
bubbleSorter - which does the main work and sorts the data stored in the array, we will give it separately again:
public void bubbleSorter()( //BUBBLE SORT METHOD 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 } } }
toSwap - swaps elements if necessary. For this, a temporary variable dummy is used, into 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:
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, and so on. That is, in total, 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 about 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 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!
Everyone knows very well that the fastest method of the class of exchange sorts is the so-called quick sort. Dissertations are written about it, many articles on Habré are devoted to it, complex hybrid algorithms are invented on its basis. But today we're not talking about quicksort, but about another exchange method - the good old bubble sort and its improvements, modifications, mutations and varieties.
The practical output from these methods is not so hot, and many habrausers went through all this in the first grade. Therefore, the article is addressed to those who have just become interested in the theory of algorithms and are taking their first steps in this direction.
image: bubbles
Today we will talk about the simplest sorting exchanges.
If anyone is interested, I will say that there are other classes - selection sort, insertion sort, merge sort, sorting distribution, hybrid sorts and parallel sorts. By the way, there are esoteric sortings. These are various fake, fundamentally unrealizable, comic and other pseudo-algorithms, about which I will somehow write a couple of articles in the IT-humor hub.
But this has nothing to do with today's lecture, we are now only interested in simple exchange sorts. There are also quite a few exchange sorts themselves (I know more than a dozen), so we will consider the so-called bubble sort and some others that are closely related to it.
I will warn you in advance that almost all of the above methods are very slow and there will be no in-depth analysis of their time complexity. Some are faster, some are slower, but, roughly speaking, we can say that on average O(n 2). Also, I see no reason to clutter up the article with implementations in any programming languages. Those who are interested can easily find code examples on Rosetta, on Wikipedia, or somewhere else.
But back to sorting exchanges. Ordering occurs as a result of repeated sequential iteration of the array and comparison of pairs of elements with each other. If the compared elements are not sorted relative to each other, then we swap them. The only question is how exactly to bypass the array and on what basis to choose pairs for comparison.
Let's start not with the reference bubble sort, but with an algorithm called ...
Silly sort
Sorting is really stupid. We look through the array from left to right and compare neighbors along the way. If we meet a pair of mutually unsorted elements, then we swap them and return to square one, that is, to the very beginning. We go through and check the array again, if we meet again the “wrong” pair of neighboring elements, then we swap places and start all over again. We continue until the array is slowly sorted.“So any fool knows how to sort” - you will say and you will be absolutely right. That is why sorting is called "stupid". In this lecture, we will consistently improve and modify this method. Now he has time complexity O(n 3), having made one correction, we will already bring to O(n 2), then speed up a little more, then a little more, and in the end we get O(n log n) - and it won't be "Quick Sort" at all!
Let's make one single improvement to stupid sorting. Having found two adjacent unsorted elements during the passage and swapping them, we will not roll back to the beginning of the array, but will calmly continue its traversal to the very end.
In this case, we have before us nothing more than the well-known ...
bubble sort
Or sorting by simple exchanges. An immortal classic of the genre. The principle of action is simple: we go around the array from beginning to end, simultaneously swapping unsorted neighboring elements. As a result of the first pass, the maximum element will “pop up” to the last place. Now we again bypass the unsorted part of the array (from the first element to the penultimate one) and change the unsorted neighbors along the way. The second largest element will be in the penultimate place. Continuing in the same spirit, we will bypass the ever-decreasing unsorted part of the array, pushing the found maximums to the end.If we not only push the highs to the end, but also move the lows to the beginning, then we get ...
shaker sort
She is shuffle sort, she is cocktail sorting. The process begins as in a “bubble”: we squeeze the maximum to the very backyards. After that, we turn around 180 0 and go in the opposite direction, while already rolling to the beginning not a maximum, but a minimum. Having sorted the first and last elements in the array, we again do a somersault. Having gone around back and forth several times, in the end we finish the process, being in the middle of the list.Shaker sort works a little faster than bubble sort, since both highs and lows alternately migrate through the array in the right directions. Improvements, as they say, are evident.
As you can see, if you approach the iteration process creatively, then pushing heavy (light) elements to the ends of the array is faster. Therefore, the craftsmen proposed another non-standard "road map" to bypass the list.
Even-odd sort
This time we will not scurry around the array back and forth, but again return to the idea of a systematic bypass from left to right, but only take a wider step. On the first pass, elements with an odd key are compared with neighbors based on even places (the 1st is compared with the 2nd, then the 3rd with the 4th, the 5th with the 6th, and so on). Then vice versa - "even" elements are compared / changed with "odd". Then again "odd-even", then again "even-odd". The process stops when, after two successive passes through the array (“odd-even” and “even-odd”), no exchange has occurred. So, sorted out.In the usual "bubble" during each pass, we systematically squeeze out the current maximum to the end of the array. If we skip along even and odd indices, then at once all more or less large elements of the array are simultaneously pushed to the right by one position in one run. That way it gets faster.
Let's analyze the last refurbishment* for Bulb sorting** - Sorting by comber***. This method arranges very quickly, O(n 2) is its worst complexity. On average over time, we have O(n log n), and the best even, do not believe it O(n). That is, a very worthy competitor to any "quick sort" and this, mind you, without the use of recursion. However, I promised that we would not delve into cruising speeds today, so I will be silent and go directly to the algorithm.
It's all the turtles' fault
A little backstory. In 1980, Włodzimierz Dobosiewicz explained why bubble sort and its derivatives are so slow. It's all about turtles. "Turtles" are small items that are at the end of the list. As you may have noticed, bubble sorts are focused on "rabbits" (not to be confused with Babushkin's "rabbits") - large elements in value at the beginning of the list. They are very briskly moving to the finish line. But slow reptiles crawl to the start reluctantly. You can customize the "tortillo" using combs.image: guilty turtle
Comb sorting
In the “bubble”, “shaker”, and “even-odd”, when iterating over an array, adjacent elements are compared. The main idea of the "comb" is to initially take a sufficiently large distance between the compared elements and, as the array is ordered, narrow this distance down to the minimum. Thus, we, as it were, comb the array, gradually smoothing it into more and more accurate strands.It is better to take the initial gap between the compared elements not anyhow, but taking into account a special value called reducing factor, the optimal value of which is approximately 1.247. First, the distance between elements is equal to the size of the array divided by reduction factor(the result is naturally rounded to the nearest integer). Then, after going through the array with this step, we again divide the step by reduction factor and go through the list again. This continues until the index difference reaches one. In this case, the array is re-sorted with a regular bubble.
The optimal value has been established experimentally and theoretically reduction factor:
When this method was invented, few people paid attention to it at the turn of the 70s and 80s. A decade later, when programming was no longer the lot of IBM scientists and engineers, but was already rapidly gaining mass character, the method was rediscovered, researched and popularized in 1991 by Stephen Lacey and Richard Box.
That's actually all I wanted to tell you about bubble sort and others like it.
- Notes
* shortened ( Ukrainian) - improvement
** Sorting with a bulb ( Ukrainian) – Bubble sort
*** Sorting by comber ( Ukrainian) – Comb sorting
When working with data arrays, it is not uncommon for them to sorting in ascending or descending order, i.e. streamlining. This means that the elements of the same array must be arranged strictly in order. For example, in the case of sorting in ascending order, the preceding element must be less than (or equal to) the subsequent element.
Decision
There are many sorting methods. Some of them are more efficient, others are easier to understand. Simple enough to understand is sorting bubble method, which is also called simple exchange method. What is it, and why does it have such a strange name: "bubble method"?
As you know, air is lighter than water, so air bubbles float. It's just an analogy. In ascending bubble sort, lighter (lower value) elements gradually “float” to the beginning of the array, while heavier ones one by one sink to the bottom (to the end of the array).
The algorithm and features of this sort are as follows:
- During the first pass through the array, the elements are compared in pairs: the first with the second, then the second with the third, then the third with the fourth, and so on. If the previous element is greater than the next, then they are swapped.
- It is not difficult to guess that gradually the largest number is the last. The rest of the array remains unsorted, although some movement of lower value elements to the beginning of the array is observed.
- On the second pass, there is no need to compare the last element with the penultimate one. The last element is already in place. This means that the number of comparisons will be one less.
- On the third pass, it is no longer necessary to compare the penultimate and third element from the end. Therefore, the number of comparisons will be two less than in the first pass.
- After all, when iterating through the array, when there are only two elements left to compare, only one comparison is performed.
- After that, the first element has nothing to compare against, and therefore the last pass through the array is not needed. In other words, the number of passes through the array is m-1, where m is the number of array elements.
- The number of comparisons in each pass is m-i, where i is the array pass number (first, second, third, etc.).
- When exchanging array elements, a "buffer" (third) variable is usually used, where the value of one of the elements is temporarily placed.
Pascal program:
const m = 10 ; var arr: array [ 1 .. m ] of integer ; i, j, k: integer ; start randomize; write ( "Source array: ") ; for i : = 1 to m do begin arr[ i] : = random(256 ) ; write (arr[ i] : 4 ) ; end ; writeln ; writeln ; for i : = 1 to m- 1 do for j : = 1 to m- i do if arr[ j] > arr[ j+ 1 ] then begin k : = arr[ j] ; arr[ j] := arr[ j+ 1 ] ; arr[ j+ 1 ] : = k end ; write ( "Sorted array: ") ; for i := 1 to m do write (arr[ i] : 4 ) ; writeln ; readln end .
Not only is it not considered the fastest method, in fact, it closes the list of the slowest ordering methods. However, it also has its advantages. So, sorting by the bubble method is the most logical and natural solution to the problem if you need to arrange the elements in a certain order. An ordinary person manually, for example, will use it just by intuition.
Where did such an unusual name come from?
The name of the method was coined using the analogy of air bubbles in water. This is a metaphor. Just as small air bubbles rise up - after all, their density is greater than any liquid (in this case, water), so each element of the array, the smaller it is in value, the more it gradually makes its way to the beginning of the list of numbers.
Description of the algorithm
Bubble sort is done like this:
- first pass: the elements of the array of numbers are taken two by two and also compared in pairs. If in some pair of elements the first value is greater than the second, the program exchanges them;
- hence it ends up at the end of the array. While all other elements remain, as they were, in a chaotic manner and require more sorting;
- therefore, the second pass is necessary: it is performed by analogy with the previous one (already described) and has the number of comparisons - minus one;
- pass number three has one fewer comparisons than the second and two fewer comparisons than the first. Etc;
- Let's summarize that each pass has (total values in array, specific number) minus (pass number) comparisons.
Even shorter, the algorithm of the future program can be written as follows:
- an array of numbers is checked until any two numbers are found, and the second of them must be greater than the first;
- Array elements that are incorrectly located in relation to each other are interchanged by the program.
Pseudocode based on the described algorithm
The simplest implementation goes like this:
Procedure Sortirovka_Puzirkom;
Start
loop for j from initial_index before konechii_index;
loop for i from initial_index before konechii_index-1;
if array[i]>array
(replace the values);
End
Of course, here simplicity only exacerbates the situation: the simpler the algorithm, the more all the shortcomings appear in it. The time consumption is too high even for a small array (this is where relativity comes into play: for the average person, the amount of time may seem small, but in the case of a programmer, every second or even a millisecond counts).
Needed a better implementation. For example, taking into account the exchange of values in the array in places:
Procedure Sortirovka_Puzirkom;
Start
sortirovka = true;
cycle bye sortirovka = true;
sortirovka = false;
loop for i from initial_index before konechii_index-1;
if array[i]>array(the first element is greater than the second), then:
(change elements in places);
sortirovka = true; (indicated that the exchange was made).
End.
Disadvantages of the method
The main disadvantage is the duration of the process. How long does the bubble take?
The execution time is calculated from the square of the number of numbers in the array - the end result is proportional to it.
In the worst case scenario, the array will be traversed as many times as there are elements in it minus one value. This is because in the end there is only one element left with nothing to compare against, and the last pass through the array becomes a useless act.
In addition, the method of sorting by simple exchanges, as it is also called, is effective only for small arrays. It will not be possible to process large amounts of data with its help: the result will be either errors or a program failure.
Advantages
Bubble sort is very easy to understand. In the curricula of technical universities, when studying the ordering of array elements, it is passed first. The method is easily implemented in both the Delphi programming language (D (Delphi) and C / C ++ (C / C plus plus), an incredibly simple algorithm for placing values in the correct order and on Bubble sort is ideal for beginners.
Due to shortcomings, the algorithm is not used for extracurricular purposes.
Visual principle of sorting
Initial view of the array 8 22 4 74 44 37 1 7
Step 1 8 22 4 74 44 37 1 7
8 22 4 74 44 1 37 7
8 22 4 74 1 44 37 7
8 22 4 1 74 44 37 7
8 22 1 4 74 44 37 7
8 1 22 4 74 44 37 7
1 8 22 4 74 44 37 7
Step 2 1 8 22 4 74 44 7 37
1 8 22 4 74 7 44 37
1 8 22 4 7 74 44 37
1 8 22 4 7 74 44 37
1 8 4 22 7 74 44 37
1 4 8 22 7 74 44 37
Step 3 1 4 8 22 7 74 37 44
1 4 8 22 7 37 74 44
1 4 8 22 7 37 74 44
1 4 8 7 22 37 74 44
1 4 7 8 22 37 74 44
Step 4 1 4 7 8 22 37 44 74
1 4 7 8 22 37 44 74
1 4 7 8 22 37 44 74
1 4 7 8 22 37 44 74
Step 5 1 4 7 8 22 37 44 74
1 4 7 8 22 37 44 74
1 4 7 8 22 37 44 74
Step 6 1 4 7 8 22 37 44 74
1 4 7 8 22 37 44 74
Step 7 1 4 7 8 22 37 44 74
Bubble sort example in Pascal
Example:
const kol_mas=10;
var array:array of integer;
a, b, k: integer;
writeln("input", kol_mas, "elements of array");
for a:=1 to kol_mas do readln(massiv[a]);
for a:=1 to kol_mas-1 do begin
for b:=a+1 to kol_mas do begin
if array[a]>massiv[b] then begin
k:=array[a]; massiv[a]:=massive[b]; array[b]:=k;
end;
writeln("after sort");
for a:=1 to kol_mas do writeln(massiv[a]);
Bubble Sort Example in C (C)
#include
#include
int main(int argc, char* argv)
int array = (36, 697, 73, 82, 68, 12, 183, 88), i, ff;
for (; ;)(
ff = 0;
for (i = 7; i>0; i--)(
if (array[i]< massiv) {
swap(array[i],array);
if (ff == 0) break;
getch(); // screen delay
Today we will touch on the topic of sorting in Pascal. There are quite a few different methods, most of them are not widely known, and knowledge of them, in principle, is not necessary. It is enough to know the basic set and a few additional ones. In this article, I will tell you about the most famous sort - the bubble sort, which is also called the simple exchange sort.
To begin with, what is sorting in pascal and why is it needed? Sorting is a method to order an array (usually in ascending or descending order). In tasks, there are such lines "arrange the elements of the array, starting from the minimum (maximum)" . Keep in mind that it's the same.
Let's go back to bubble sort. Why was she named that way? The thing is, it's an analogy. Imagine a regular array stacked vertically. As a result of sorting, smaller elements move up. That is, here the array can be represented in the form of water, and the smaller elements in the form of a bubble that float to the top.
Now more about the algorithm itself. Everything is quite simple:
1. 2 loops are used for sorting, one is nested in the other. One is used for steps, the other for sub-steps.
2. The essence of the algorithm is a comparison of two elements. Exactly two. I explain, for example we have an array with 10 elements. Elements will be compared in pairs: 1 and 2, 2 and 3,3 and 4,4 and 5,6 and 7, etc. When comparing pairs, if the previous element is greater than the next, then they are swapped. For example, if the second element is 5 and the third is 2 , then they will swap them.
3. Bubble sort is divided into steps. In each step, a pairwise comparison is performed. As a result of each step, the largest elements begin to line up from the end of the array. That is, after the first step, the largest element of the array by value will be in last place. In the second step, work is done with all elements except the last one. Again, the largest element is found and placed at the end of the array with which the operation is performed. The third step repeats the second one and so on until the array is sorted. To make it easier to understand, let me give you a simple example. Let's take an array consisting of 7 elements: 2,5,11,1,7,8,3. We look. (Click on the picture to enlarge the image)
Let's go directly to the code. As already mentioned, we need two cycles. Here's what it will look like
const
m = 7; (number of elements in the array)
var
msort: array of integers; (actually our array)
i, j, k: integer; (i is a step, j is a sub-step)
begin
writeln("Enter array elements");
for i:= 1 to m do
read(msort[i]);
For i:= 1 to m - 1 do
for j:= 1 to m - i do
if msort[j] > msort then begin
k:= msort[j];
msort[j] := msort;
msort := k;
end;
Write("Sorted array: ");
for i:= 1 to m do
write(msort[i]:4);
end.
Notice the k element. It is needed for only one purpose: to swap two array elements in places. The matter is that in Pascal there is no special function which would carry out such action. Therefore, you have to paint it yourself, adding an additional element for the exchange. This concludes the bubble sort article, the next articles will be released within the next week (or maybe earlier).
