Bubble sort is that simple
In my freshman year, I taught myself C language and data structure, and I was exposed to bubble sort (written in C language at that time). Now that I am a junior, I will review the knowledge of data structures and algorithms if I want to find an internship in the summer vacation.
Sorting is not new to us at all, there will be ranks when you play King of Glory, there will be ranks when you play Dota. From top to bottom, the ranking is regular, it’s a sort of ranking.
I started out with bubble sort, so this post is all about bubble sort.
Bubble sort implementation
Source BCO:
Bubble Sort is a simple sorting algorithm. It repeatedly walks through the sequence to be sorted, comparing two elements at a time and swapping them if they are in the wrong order. The task of visiting an array is repeated until no more exchanges are needed, that is, the array has been sorted. The algorithm gets its name from the fact that larger elements slowly “float” to the top of the list through swapping.
Algorithm description:
iStarting at zero,iwithi+1Compare, ifi>i+1, then swapiAnd it keeps increasing untili<n-1N is the number of elements in the array,n-1Is the last element in the array), after a trip, you can make the maximum value of the array element at the end of the array
To start with, we create an array with five digits:
int[] arrays = {2.5.1.3.4};
Copy the codeOne, the first sequence
Here we are checking the code according to the description of the algorithm **(first sort)** :
// Use temporary variables to make the two numbers interchangeable
int temp;
// First and second
if (arrays[0] > arrays[1]) {
/ / exchange
temp = arrays[0];
arrays[0] = arrays[1];
arrays[1] = temp;
}
// The second and third place
if (arrays[1] > arrays[2]) {
temp = arrays[1];
arrays[1] = arrays[2];
arrays[2] = temp;
}
// The third and the fourth place
if (arrays[2] > arrays[3]) {
temp = arrays[2];
arrays[2] = arrays[3];
arrays[3] = temp;
}
// The fourth and the fifth place
if (arrays[3] > arrays[4]) {
temp = arrays[3];
arrays[3] = arrays[4];
arrays[4] = temp;
}
Copy the codeIf the previous digit is larger than the next digit, swap until all the elements of the array have been compared!
After our first comparison, we can see that the largest value is at the end of the array!
First, the second order
The second sort is the same as the first sort, comparing the previous one to the next one, and if the previous one is bigger than the next one, switch. Note that there is no need to compare to the last digit, because the last digit is already the largest by the end of the first sorting. Similarly, after the second sorting, the second to last number is also the second largest number.
The code for the second sort is as follows:
// First and second
if (arrays[0] > arrays[1]) {
/ / exchange
temp = arrays[0];
arrays[0] = arrays[1];
arrays[1] = temp;
}
// The second and third place
if (arrays[1] > arrays[2]) {
temp = arrays[1];
arrays[1] = arrays[2];
arrays[2] = temp;
}
// The third and the fourth place
if (arrays[2] > arrays[3]) {
temp = arrays[2];
arrays[2] = arrays[3];
arrays[3] = temp;
}
// The fourth bit does not need to be compared with the fifth bit, because the fifth bit is the largest at the end of the first sort.
Copy the codeResult: our second largest number is already second to last
Iii. Code simplification
It is worth noting that the above results appear to be sorted, but in fact my data was not sufficiently cluttered at the time of testing. If the data was cluttered enough, it would have required 4(n-1) sorts!
But we can see from the above code: the first and second comparison, exchange code is repeated, and our comparison is dead (0,1,2,3,4), not universal!
Our array has five digits
- The first trip requires four comparisons
- The second trip requires three comparisons
We can infer from the above rules that:
- The third trip requires two comparisons
- The fourth lie needs to be compared once
We can sum up the above rule: 5 digit array needs 4 lie sorted, after each lie sorted by 1(because the previous row has determined the maximum number of previous row)!
So we can simplify the above code with respect to the for loop and variables:
int temp;
// The outer loop is the number of sorts
for (int i = 0; i < arrays.length - 1 ; i++) {
// The inner loop is the number of times the current number of runs needs to be compared
for (int j = 0; j < arrays.length - i - 1; j++) {
// If the former is larger than the latter, swap
if (arrays[j] > arrays[j + 1]) {
temp = arrays[j];
arrays[j] = arrays[j + 1];
arrays[j + 1] = temp; }}}Copy the codeFourth, bubble sorting optimization
As we can see from the above example, if the data is sufficiently cluttered, it takes a 4 lie comparison to get the array sorted completely. But we already have the sorted array after the second lie comparison.
However, our program still performs a third and fourth sort after the second sort. This is not necessary, so we can optimize it:
- If there is no swap in a lie sort, the array is considered sorted.
- This is not hard to understand, because the purpose of each sort is to replace the largest number in the current sort with the corresponding position, and the permutation specification is already sorted.
The code is as follows:
// Load temporary variables
int temp;
// Record whether a substitution took place. 0 indicates that no substitution took place and 1 indicates that a substitution took place
int isChange;
// The outer loop is the number of sorts
for (int i = 0; i < arrays.length - 1; i++) {
// reinitialize to 0 every time you compare
isChange = 0;
// The inner loop is the number of times the current number of runs needs to be compared
for (int j = 0; j < arrays.length - i - 1; j++) {
// If the former is larger than the latter, swap
if (arrays[j] > arrays[j + 1]) {
temp = arrays[j];
arrays[j] = arrays[j + 1];
arrays[j + 1] = temp;
// If it goes in here, it's a permutation
isChange = 1; }}// If there is no substitution after the comparison, then the order is sorted and no further execution is required
if (isChange == 0) {
break; }}Copy the code
5. Read more
C language implementation of the first way:
void bubble ( int arr[], int n)
{
int i;
int temp;
for (i = 0; i < n - 1; i++) {
if (arr[i] > arr[i + 1]) {
temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp; }}}void bubbleSort ( int arr[], int n)
{
int i;
for (i = n; i >= 1; i--) { bubble(arr, i); }}Copy the codeC implements the second kind of recursion:
void bubble ( int arr[], int L, int R)
{
if (L == R) ;
else {
int i;
for (i = L; i <= R - 1; i++)// I can only reach r-1
if (arr[i] > arr[i + 1]) {
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
bubble(arr, L, R - 1);// The first round has been lined up}}Copy the codeTest code:
int main (a)
{
int arr[] = {2.3.4.511.66.777.444.555.9999};
bubbleSort(arr, 8);
for (int i = 0; i < 9; i++)
cout << arr[i] << endl;
return 0;
}
Copy the code5.1 Understanding of Time Complexity:
- www.zhihu.com/question/21…
- www.jianshu.com/p/f4cca5ce0…
If the article has the wrong place welcome to correct, everybody exchanges with each other. Students who are used to reading technical articles on wechat and want to get more Java resources can follow the wechat public account :Java3y