MMGames
Automatic version identification
SpineViewer
It's easy to tell by looking at it.
Response Time Checker
I can leave my computer on and do it.
Mouse cleaning time
I can leave my computer on and do it.
Mouse cleaning time
C language learned by suffering
C language learned by suffering
bubble sort
What is sorting?
Sorting is the process of rearranging randomly sorted data into the correct order.
For example, sort as follows
In this case, sorting with smaller values toward the left is called ascending order.
Conversely, sorting with smaller values to the right is descending order.
In addition, sorting sometimes requires stability.
Stability means that the order of data with the same value does not change after sorting.
For example, suppose the following are the results of a quiz for a certain class.
Sorting this in a stable manner yields the following
The back and forth relationship between Takeshi Gouda and Suneo Konekawa, who have the same score, is the same as before sorting.
Next, we sort them in a non-stable way.
The same score, Takeshi Gouda and Suneo Konekawa, are swapped back and forth.
In some cases, the order of people with the same score must be retained, and
In such cases, a stable method must be used.
For example, sort as follows
| Before sorting | 23 | 9 | 7 | 15 | 3 | 1 | 30 | 19 |
|---|---|---|---|---|---|---|---|---|
| After sorting | 1 | 3 | 7 | 9 | 15 | 19 | 23 | 30 |
In this case, sorting with smaller values toward the left is called ascending order.
Conversely, sorting with smaller values to the right is descending order.
In addition, sorting sometimes requires stability.
Stability means that the order of data with the same value does not change after sorting.
For example, suppose the following are the results of a quiz for a certain class.
| Student Name | Points |
|---|---|
| Nobita Nohi | 0 |
| Shizuka Minamoto | 90 |
| Takeshi Gouda | 50 |
| Suneo Konekawa | 50 |
Sorting this in a stable manner yields the following
| Student Name | Points |
|---|---|
| Nobita Nohi | 0 |
| Takeshi Gouda | 50 |
| Suneo Konekawa | 50 |
| Shizuka Minamoto | 90 |
The back and forth relationship between Takeshi Gouda and Suneo Konekawa, who have the same score, is the same as before sorting.
Next, we sort them in a non-stable way.
| Student Name | Points |
|---|---|
| Nobita Nohi | 0 |
| Suneo Konekawa | 50 |
| Takeshi Gouda | 50 |
| Shizuka Minamoto | 90 |
The same score, Takeshi Gouda and Suneo Konekawa, are swapped back and forth.
In some cases, the order of people with the same score must be retained, and
In such cases, a stable method must be used.
Sort Purpose
If they were originally arranged in a random order, why not just leave them as they are?
The reason for sorting is to speed up the search process.
When the data is aligned, it is easier to find where the desired value is located.
The search is quicker than if the data were arranged in a random order.
The reason for sorting is to speed up the search process.
When the data is aligned, it is easier to find where the desired value is located.
The search is quicker than if the data were arranged in a random order.
bubble sort
While there are a great many different algorithms that have been devised for sorting
Among these, bubble sort is often discussed because of its ease of programming.
However, it is not an excellent method because of its slow speed.
First, compare the first and second data, and if the second is smaller, exchange data.
Next, the second and third are compared and exchanged. This is repeated until the end of the data.
When you reach the end of the data, repeat the comparison and exchange again, starting from the first one.
Repeat this process for as many times as the number of data, and the data will be aligned.
In this way, the reordering between the two pieces is repeated until the reordering is complete, which is the bubble sort.
The following is a programmatic implementation of bubble sort.
To see how it works, it is easy to pass a character array with the type of array as char.
Bubble sort uses a double loop, so the number of calculations is O(N^2).
This would be equivalent to the third arithmetic quantity from the right in the calculation quantity guideline.
Bubble sort is an algorithm that is computationally expensive in its own right and is not very good.
Among these, bubble sort is often discussed because of its ease of programming.
However, it is not an excellent method because of its slow speed.
The idea is simple.
First, compare the first and second data, and if the second is smaller, exchange data.
Next, the second and third are compared and exchanged. This is repeated until the end of the data.
When you reach the end of the data, repeat the comparison and exchange again, starting from the first one.
Repeat this process for as many times as the number of data, and the data will be aligned.
| Comparison of the first and second | (23) | ( 9) | 7 | 15 | 3 | 1 | 30 | 19 |
|---|---|---|---|---|---|---|---|---|
| The second one is too small to be replaced | ( 9) | (23) | 7 | 15 | 3 | 1 | 30 | 19 |
| Comparison of the second and third | 9 | (23) | ( 7) | 15 | 3 | 1 | 30 | 19 |
| Third one is too small to replace. | 9 | ( 7) | (23) | 15 | 3 | 1 | 30 | 19 |
In this way, the reordering between the two pieces is repeated until the reordering is complete, which is the bubble sort.
The following is a programmatic implementation of bubble sort.
Source Code
/*
Usage
SortBubble(array to sort, number to sort);
*/
void SortBubble(int array[], int n)
{
int i, j, temp;
for (i = 0; i < n - 1; i++)
{
for (j = 0; j < n - 1; j++)
{
if (array[j + 1] < array[j])
{
temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}To see how it works, it is easy to pass a character array with the type of array as char.
Bubble sort uses a double loop, so the number of calculations is O(N^2).
This would be equivalent to the third arithmetic quantity from the right in the calculation quantity guideline.
computational complexity
1, log2n, n, nlog2n, n^2, 2^n, n!
Bubble sort is an algorithm that is computationally expensive in its own right and is not very good.
About this Site
The C language (bitter C), which is learned by suffering, is
This is the definitive C language introductory site.
It systematically explains the basic functions of the C language and
It is as complete as or more complete than any book on the market.