Bubble sorting and that's it
Everyone knows very well that from the class of exchange sorts the fastest method is the so-called quick sort. Dissertations are written about it, many articles on Habré are devoted to it, and complex hybrid algorithms are invented based on it. But today we will not talk about quick sort, and about another exchange method - the good old bubble sort and its improvements, modifications, mutations and variations.
The practical benefits from these methods are not so great, and many habra users went through all this in 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'll talk about the simplest exchange sortings.
If anyone is interested, I will say that there are other classes - selection sort, insertion sort, merge sort, distribution sorting, hybrid sortings And parallel sorts. By the way, there is also esoteric sortings. These are various fake, fundamentally unrealizable, comic and other pseudo-algorithms, about which I will 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 sortings. There are also a lot of exchange sortings themselves (I know more than a dozen), so we will look at the so-called bubble sort and some others 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 the article with implementations in any programming languages. Those interested can easily find code examples on Rosetta, Wikipedia or elsewhere.
But let's return 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 elements being compared 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 select pairs for comparison.
Let's start not with the standard bubble sort, but with an algorithm called...
Stupid sort
Sorting is truly stupid. We look through the array from left to right and compare neighbors along the way. If we encounter a pair of mutually unsorted elements, we swap them and return to square one, that is, to the very beginning. We go through and check the array again, if we again encounter an “incorrect” pair of neighboring elements, then we change places and start all over again. We continue until the array is little by little sorted.“Any fool can sort like that,” you will say, and you will be absolutely right. This is why sorting is called “stupid”. In this lecture we will consistently improve and modify this method. Now he has temporary difficulty O(n 3), having made one correction, we will already bring it to O(n 2), then we’ll speed it up a little more, then a little more, and in the end we’ll get O(n log n) – and it won’t be “Quick Sort” at all!
Let's make one single improvement to the stupid sorting. Having discovered two adjacent unsorted elements during the passage and swapped them, we will not roll back to the beginning of the array, but will calmly continue traversing it 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 operation is simple: we traverse the array from beginning to end, simultaneously swapping unsorted neighboring elements. As a result of the first pass, the maximum element will “float” to the last place. Now we again traverse 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 second to last place. Continuing in the same spirit, we will traverse the ever-decreasing unsorted part of the array, pushing the found maxima to the end.If we not only push the maximums to the end, but also push the minimums to the beginning, then we succeed...
Shaker sorting
She's the same shuffle sort, she's the same cocktail sorting. The process begins as in a “bubble”: we squeeze out the maximum to the very back. After this, we turn around 180 0 and go in the opposite direction, while rolling back to the beginning not the maximum, but the minimum. Having sorted the first and last elements in the array, we do a somersault again. After going back and forth several times, we eventually end the process, finding ourselves in the middle of the list.Shaker sorting works a little faster than bubble sorting, since both maximums and minimums alternately migrate through the array in the required directions. The improvements, as they say, are obvious.
As you can see, if you approach the enumeration process creatively, then pushing out heavy (light) elements to the ends of the array happens faster. Therefore, the craftsmen proposed another non-standard “road map” to get around the list.
Even-odd sorting
This time we will not scurry back and forth across the array, but will again return to the idea of a systematic walk around from left to right, but we will only take a wider step. On the first pass, elements with an odd key are compared with their neighbors based in even places (the 1st is compared with the 2nd, then the 3rd with the 4th, the 5th with the 6th, and so on). Then, on the contrary, we compare/change “even” elements with “odd” ones. Then again “odd-even”, then again “even-odd”. The process stops when, after two consecutive passes through the array (“odd-even” and “even-odd”), not a single exchange has occurred. So, they sorted it.In a regular “bubble”, during each pass we systematically squeeze the current maximum to the end of the array. If you jump along even and odd indices, then all the more or less large elements of the array are simultaneously pushed to the right one position in one run. It works faster this way.
Let's look at the last one redecorated* For Sortuvannya bulbashka** - Sorting by comb***. This method organizes very quickly, O(n 2) is its worst difficulty. On average over time we have O(n log n), and the best, you won’t even believe it, O(n). That is, a very worthy competitor to all sorts of “quick sorts” and this, mind you, without the use of recursion. However, I promised that today we will not delve into cruising speeds, so I’ll stop talking and go directly to the algorithm.
It's all the turtles' fault
A little background. In 1980, Włodzimierz Dobosiewicz explained why bubble sort and its derivatives work so slowly. It's all because of the turtles. “Turtles” are small elements that are located 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-value elements at the beginning of the list. They move very briskly towards the finish line. But slow reptiles crawl to the start reluctantly. You can customize the tortilla using combs.image: guilty turtle
Comb sorting
In “bubble”, “shaker” and “odd-even”, when iterating through an array, neighboring elements are compared. The main idea of the “comb” is to initially take a sufficiently large distance between the elements being compared and, as the array is ordered, to narrow this distance down to the minimum. In this way, we sort of comb the array, gradually smoothing it into increasingly neat strands.It is better to take the initial gap between the compared elements not just any, 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, of course, is rounded to the nearest integer). Then, after traversing 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 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 province of IBM scientists and engineers, but was already rapidly gaining mass popularity, the method was rediscovered, researched and popularized in 1991 by Stephen Lacy and Richard Box.
That’s actually all I wanted to tell you about bubble sorting and others like it.
- Notes
* shortened ( Ukrainian) - improvement
** Sorted by bulb ( Ukrainian) – Bubble sort
*** Sorting by comb ( Ukrainian) – Comb sorting
Today we will touch on the topic of sorting in Pascal. There are quite a lot of different methods, most of them are not widely known, and in principle, knowledge of them 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 - bubble sort, which is also called simple exchange sort.
First, what is sorting in Pascal and why is it needed? Sorting is a method of ordering an array (usually in ascending or descending order). In problems there are such lines as “arrange the elements of the array, starting from the minimum (maximum)” . Keep in mind that this is the same thing.
Let's return to bubble sort. Why was she named that way? The point is that this is an analogy. Imagine a regular array arranged 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 let's talk more about the algorithm itself. It's quite simple:
1. For sorting, 2 cycles are used, one nested within 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. Let me 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 larger than the next one, 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 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 that is being worked with. The third step repeats the second and so on until the array is sorted. For a more convenient understanding, I will give a clear example. Let's take an array consisting of 7 elements: 2,5,11,1,7,8,3. Let's take a look.(Click on the picture to enlarge the image)
Let's move directly to the code. As already mentioned, we need two cycles. This is what it will look like
const
m = 7; (number of elements in the array)
var
msort: array of integer; (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 elements of an array. The fact is that in Pascal there is no special function that would perform such an action. Therefore, you have to paint it yourself, adding an additional element for exchange. This article is finished with the bubble sorting method, the next articles will be published within the next week (or maybe earlier).
It has been estimated that up to a quarter of the time of centralized computers is spent sorting data. This is because it is much easier to find a value in an array that has been pre-sorted. Otherwise, the search is a bit like looking for a needle in a haystack.
There are programmers who spend all their working time studying and implementing sorting algorithms. This is because the vast majority of business software involves database management. People search databases for information all the time. This means that search algorithms are in high demand.
But there is one "but". Search algorithms work much faster on databases that are already sorted. In this case, only linear search is required.
While the computers are without users at some points in time, the sorting algorithms continue to operate on the databases. Searchers come again, and the database is already sorted based on one or another search purpose.
This article provides examples of implementations of standard sorting algorithms.
Selection sort
To sort an array in ascending order, you must find the element with the largest value at each iteration. With it you need to swap the last element. The next element with the highest value is placed in second to last place. This should happen until the elements in the first places in the array are in the proper order.
C++ code
void SortAlgo::selectionSort(int data, int lenD) ( int j = 0; int tmp = 0; for (int i=0; i
Bubble sort
Bubble sort compares adjacent elements and swaps places if the next element is smaller than the previous one. Multiple passes through the data are required. During the first pass, the first two elements in the array are compared. If they are not in order, they are swapped and then the elements in the next pair are compared. Under the same condition, they also change places. Thus, sorting occurs in each cycle until the end of the array is reached.
C++ code
void SortAlgo::bubbleSort(int data, int lenD) ( int tmp = 0; for (int i = 0;i Insertion sort splits the array into two regions: ordered and unordered. Initially, the entire array is an unordered region. In the first pass, the first element from the unordered region is removed and placed in the correct position in the ordered region. On each pass, the size of the ordered region increases by 1, and the size of the disordered region decreases by 1. The main loop runs from 1 to N-1. At the jth iteration, element [i] is inserted into the correct position in the ordered region. This is done by shifting all elements of the ordered region that are greater than [i] one position to the right. [i] is inserted into the space between those elements that are less than [i] and those that are greater than [i]. C++ code
void SortAlgo::insertionSort(int data, int lenD) ( int key = 0; int i = 0; for (int j = 1;j C++ code
void SortAlgo::mergeSort(int data, int lenD) ( if (lenD>1)( int middle = lenD/2; int rem = lenD-middle; int * L = new int; int * R = new int; for ( int i=0;i Quicksort uses a divide and conquer algorithm. It begins by splitting the original array into two areas. These parts are to the left and right of the marked element, called the support. At the end of the process, one part will contain elements smaller than the reference, and the other part will contain elements larger than the reference. C++ code
void SortAlgo::quickSort(int * data, int const len) ( int const lenD = len; int pivot = 0; int ind = lenD/2; int i,j = 0,k = 0; if (lenD>1) ( int * L = new int ; int * R = new int ; pivot = data; for (i=0;i Insertion sort
Merge sort
Quick sort
