Bubble sort of an array. Implementation of bubble sort in Java. Implementation of bubble sort in Java
Tags: Bubble sort C, Bubble sort, Bubble sort of a two-dimensional array
Bubble sort
And the idea of the algorithm is very simple. We go through the array of numbers and check the order (the next number must be greater than and equal to the previous one), as soon as we come across a violation of the order, we immediately swap the elements, reach the end of the array, and then start over.
Sort the array (1, 5, 2, 7, 6, 3)
We go through the array, check the first number and the second, they are in ascending order. Next comes a violation of order, we swap these elements
1, 2, 5, 7, 6, 3
We continue to go through the array, 7 is more than 5, but 6 is less, so we swap them
1, 2, 5, 6, 7, 3
3 breaks the order, swap places with 7
1, 2, 5, 6, 3, 7
We return to the beginning of the array and do the same
1, 2, 5, 3, 6, 7
1, 2, 3, 5, 6, 7
They say that this is similar to the “floating up” of “lighter” elements, like bubbles, which is why the algorithm got its name. void bubbleSort(int *a, size_t size) ( size_t i, j; int tmp; for (i = 1; i< size; i++) { for (j = 1; j < size; j++) { if (a[j] >a) ( tmp = a[j]; a[j] = a; a = tmp; ) ) ) )
This algorithm will always take (n-1) 2 steps, regardless of the input data. Even if the array is sorted, it will still be traversed (n-1) 2 times. Moreover, the already sorted data will be checked again.
Let's say we need to sort the array 1, 2, 4, 3
1 2 4 3
1 2 4 3
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
Once the elements a and a have been swapped, there is no longer a need to traverse this section of the array. Let's take this into account and rework the algorithm
Void bubbleSort2(int *a, size_t size) ( size_t i, j; int tmp; for (i = 1; i< size; i++) { for (j = i; j >0; j--) ( if (a[j]< a) { tmp = a[j]; a[j] = a; a = tmp; } } } }
Another implementation
Void bubbleSort2b(int *a, size_t size) ( size_t i, j; int tmp; for (i = 1; i< size; i++) { for (j = 1; j <= size-i; j++) { if (a[j] < a) { tmp = a[j]; a[j] = a; a = tmp; } } } }
In this case, there will be half as many steps, but the problem of sorting an already sorted array still remains: you need to make sure that the function looks through the sorted array once. To do this, we introduce a flag variable: it will be omitted (flag = 0) if the array is sorted. As soon as we come across a violation of the order, the flag will be raised (flag = 1) and we will begin to sort the array as usual.
Void bubbleSort3(int *a, size_t size) ( size_t i; int tmp; char flag; do ( flag = 0; for (i = 1; i< size; i++) { if (a[i] < a) { tmp = a[i]; a[i] = a; a = tmp; flag = 1; } } } while (flag); }
In this case, the complexity is also of the order of n 2 , but in the case of a sorted array there will be only one pass.
Now let's improve the algorithm. Let's write a general function to sort an array of void type. Since the type of the variable is not known, you will need to additionally pass the size of one array element and the comparison function.
Int intSort(const void *a, const void *b) ( return *((int*)a) > *((int*)b); ) void bubbleSort3g(void *a, size_t item, size_t size, int (* cmp)(const void*, const void*)) ( size_t i; void *tmp = NULL; char flag; tmp = malloc(item); do ( flag = 0; for (i = 1; i< size; i++) { if (cmp(((char*)a + i*item), ((char*)a + (i-1)*item))) { memcpy(tmp, ((char*)a + i*item), item); memcpy(((char*)a + i*item), ((char*)a + (i-1)*item), item); memcpy(((char*)a + (i-1)*item), tmp, item); flag = 1; } } } while (flag); free(tmp); }
The function looks ugly - the address of the current and previous element is often calculated. Let's highlight separate variables for this.
Void bubbleSort3gi(void *a, size_t item, size_t size, int (*cmp)(const void*, const void*)) ( size_t i; void *tmp = NULL; void *prev, *cur; char flag; tmp = malloc(item); do ( flag = 0; i = 1; prev = (char*)a; cur = (char*)prev + item; while (i< size) { if (cmp(cur, prev)) { memcpy(tmp, prev, item); memcpy(prev, cur, item); memcpy(cur, tmp, item); flag = 1; } i++; prev = (char*)prev + item; cur = (char*)cur + item; } } while (flag); free(tmp); }
Now using these functions you can sort arrays of any type, for example
Void main() ( int a = (1, 0, 9, 8, 7, 6, 2, 3, 4, 5); int i; bubbleSort3gi(a, sizeof(int), 10, intSort); for (i = 0;i< 10; i++) { printf("%d ", a[i]); } _getch(); }
Sorting a multidimensional array
Sorting a static multidimensional array is essentially no different from sorting a one-dimensional one. You can take advantage of the fact that static one-dimensional and multidimensional arrays have the same representation in memory.
Void main() ( int a = (1, 9, 2, 8, 3, 7, 4, 6, 5); int i, j; bubbleSort3gi(a, sizeof(int), 9, intSort); for (i = 0;i< 3; i++) {
for (j = 0; j < 3; j++) {
printf("%d ", a[i][j]);
}
}
}
Сортировка динамически созданного двумерного массива может быть произведена двумя способами. Во-первых, можно по определённому алгоритму находить индекс i-го и j-го элемента по порядковому номеру k от 0 до n * m.
#include
Secondly, you can first move the array to one-dimensional, sort the one-dimensional array, and then move it back to two-dimensional.
Void bubbleSort3gi2d(void **a, size_t item, size_t m, size_t n, int (*cmp)(const void*, const void*)) ( size_t size = m*n, sub_size = n*item; size_t i, j , k; void *arr = malloc(size * item); char *p1d = (char*)arr; char *p2d = (char*)a; //Copy a two-dimensional void type array into a one-dimensional one for (i = 0; i< m; i++) { memcpy(p1d + i*sub_size, *((void**)(p2d + i*item)), sub_size); } bubbleSort3gi(arr, item, size, cmp); //Копируем одномерный массив обратно в двумерный for (i = 0; i < m; i++) { memcpy(*((void**)(p2d + i*item)), p1d + i*sub_size, sub_size); } }
If you are confused by this function, then use the typed one. Call, from previous example
Hi all!
Today we will look at bubble sorting. This algorithm is often taught in schools and universities, so we will use Pascal. So, what is sorting? Sorting is the ordering of elements from smallest to largest (ascending sort) or from largest element to smallest (descending sort). Arrays are usually sorted.
There are various sorting algorithms. Some are good at sorting a large number of elements, others are more efficient with a very small number of elements. Our bubble method is characterized by:
Pros:
- Ease of implementation of the algorithm
- Beautiful name
- One of the slowest sorting methods (Execution time depends quadratically on the length of the array n 2)
- Almost not used in real life (used mainly for educational purposes)
Algorithm: We take an element of the array, compare it with the next one, if our element is greater than the next element, then we swap them. After going through the entire array, we can be sure that the maximum element will be “pushed out” - and will be the very last one. Thus, one element is already exactly in its place. Because we need to put them all in their places, therefore, we must repeat this operation as many times as we have array elements minus 1. The last element will stand automatically if the rest are in their places.
Let's return to our array: 3 1 4 2
We take the first element “3” and compare it with the next “1”. Because "3" > "1", then swap places:
1 3 4 2
Now we compare “3” and “4”, three is not more than four, which means we do nothing. Next, compare “4” and “2”. Four is more than two - so we change places: 1 3 2 4. The cycle is over. This means that the largest element should already be in place!! We see that this is what happened here. Wherever “4” (our largest element) is located, it will still be the last one after the loop has traversed the entire array. An analogy - just as an air bubble floats up in water, so does our element float up in an array. That's why the algorithm is called "Bubble Sort". To position the next element, it is necessary to start the cycle all over again, but the last element can no longer be considered, because it is in its place.
We compare “1” and “3” - we don’t change anything.
We compare “3” and “2” - Three is more than two, which means we change places. It turns out: 1 2 3 4 . The second cycle is completed. We have already completed two cycles, which means we can say with confidence that our last two elements have already been sorted. All we have to do is sort the third element, and the fourth will fall into the right place automatically. Once again, we compare the first element and the second - we see that we already have everything in its place, which means that the array can be considered sorted in ascending order of elements.
Now all that remains is to program this algorithm in Pascal. const n = 4; (We set up a constant, this will be the length of the array) var i, j, k:integer; (Two variables for the nested loop, one for swapping elements) m:array of integer; (We create an array) begin (We will request the array from the keyboard:) Writeln("Enter an array:"); for i:=1 to n do begin Writeln(i, " element:"); Readln(m[i]); end; (The outer loop is responsible for the fact that we must repeat the inner loop as many times as we have array elements minus 1.) for i:=1 to n-1 do begin (The inner loop already iterates through the elements and compares with each other.) for j :=1 to n-i do begin (If the element is greater than the next one, then swap places.) if m[j]>m then begin k:=m[j]; m[j]:=m; m:=k; end; end; end; (Print the result:) for i:=1 to n do Write(m[i], " "); end.
Here's the result: 
Here's a video tutorial
Not only is it not considered the fastest method, moreover, it closes the list of the slowest ordering methods. However, it also has its advantages. So, bubble sorting is the most logical and natural solution to the problem if you need to arrange elements in a certain order. An ordinary person, for example, will use it manually - simply by intuition.
Where did such an unusual name come from?
The name of the method was invented using an analogy with air bubbles in water. This is a metaphor. Just as small air bubbles rise to the top - after all, their density is greater than that of 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 works like this:
- first pass: elements of the array of numbers are taken two at a time and also compared in pairs. If in some pair of elements the first value is greater than the second, the program swaps them;
- therefore ends up at the end of the array. While all other elements remain as they were, in a chaotic order and require further sorting;
- that is why a second pass is necessary: it is performed by analogy with the previous one (already described) and has the number of comparisons - minus one;
- Passage number three has one fewer comparisons than the second, and two less than the first. And so on;
- Let's summarize that each pass has (total values in the array, a specific number) minus (pass number) comparisons.
Even more briefly, the algorithm of the future program can be written as follows:
- the array of numbers is checked until any two numbers are found, and the second of them must be greater than the first;
- The program swaps array elements that are incorrectly positioned in relation to each other.
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 massiv[i]>massiv
(swap the values);
End
Of course, here simplicity only aggravates the situation: the simpler the algorithm, the more all the shortcomings appear in it. The time consumption is too great even for a small array (relativity comes into play here: for the average person, the amount of time may seem small, but in the business of a programmer, every second or even millisecond counts).
A better implementation was needed. For example, taking into account the swapping of values in an array:
Procedure Sortirovka_Puzirkom;
Start
sortirovka = true;
cycle so far sortirovka = true;
sortirovka = false;
loop for i from initial_index before konechii_index-1;
If massiv[i]>massiv(the first element is greater than the second), then:
(swap elements);
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 it take to make a bubble?
The execution time is calculated from the square of the number of numbers in the array - the final result is proportional to it.
In the worst case scenario, the array will be traversed the same number of times as there are elements in it minus one value. This happens because eventually there is only one element left with nothing to compare with, and the last pass through the array becomes a useless action.
In addition, the simple exchange sorting method, 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 program failure.
Advantages
Bubble sort is quite simple to understand. In the curricula of technical universities, when studying the ordering of array elements, it is covered first. The method is easily implemented in both the Delphi programming language (D) and C/C++ (C/C plus plus), an incredibly simple algorithm for arranging values in the correct order, and Bubble Sort is ideal for beginners.
Due to its shortcomings, the algorithm is not used for extracurricular purposes.
Visual sorting principle
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
Example of bubble sort 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(array[a]);
for a:=1 to kol_mas-1 do begin
for b:=a+1 to kol_mas do begin
if massiv[a]>massiv[b] then begin
k:=array[a]; massiv[a]:=massiv[b]; array[b]:=k;
end;
writeln("after sort");
for a:=1 to kol_mas do writeln(massiv[a]);
Example of bubble sort in C language
#include
#include
int main(int argc, char* argv)
int massiv = (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],massiv);
if (ff == 0) break;
getch(); // screen delay
When working with data arrays, the task often arises sorting in ascending or descending order, i.e. ordering. This means that the elements of the same array must be arranged strictly in order. For example, in the case of ascending sort, the preceding element must be less than (or equal to) the subsequent one.
Solution
There are many sorting methods. Some of them are more effective, others are easier to understand. Sorting is fairly easy to understand 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 sorting, lighter (smaller value) elements gradually “float” to the beginning of the array, and heavier ones, one after another, fall to the bottom (to the end of the array).
The algorithm and features of this sorting are as follows:
- During the first pass through the array, the elements are compared with each other in pairs: the first with the second, then the second with the third, then the third with the fourth, etc. If the previous element is larger than the subsequent one, then they are swapped.
- It is not difficult to guess that gradually the largest number turns out to be the last. The rest of the array remains unsorted, although there is some movement of lower value elements to the beginning of the array.
- 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, there is no longer any need 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 an array, when there are only two elements left to compare, only one comparison is performed.
- After this, there is nothing to compare the first element to, and therefore a final pass through the array is unnecessary. In other words, the number of passes through the array is m-1, where m is the number of elements in the array.
- The number of comparisons in each pass is equal to m-i, where i is the number of passes through the array (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 ; begin 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 .