learn through suffering C language
learn through suffering C language
Bubble sort
What is sorting?
Sorting is the process of arranging randomly ordered data into a sequential order.
For example, sort like this:
At this time, we call a sort that becomes smaller as you go left an ascending sort.
Conversely, a sort where values decrease as you go right is in descending order.
Sometimes, stability is required in sorting.
Stability means that the relative order of elements with equal values is preserved after sorting.
For example, let's say this is the result of a pop quiz for one class.
Here's a stable sort in the following order:
The relative order of Takeshi Goda and Suneo Bonegawa, who have the same score, remains the same after sorting.
Next, we'll sort it unstably.
Takeshi Goda and Susumu Honekawa, who had the same score, have switched places.
In some cases, it's necessary to preserve the original order of people with the same score.
In that case, we must use a stable method.
For example, sort like this:
| Before sorting | 23 | 9 | 7 | 15 | 3 | 1 | 30 | 19 |
|---|---|---|---|---|---|---|---|---|
| After sorting | 1 | 3 | 7 | 9 | 15 | 19 | 23 | 30 |
At this time, we call a sort that becomes smaller as you go left an ascending sort.
Conversely, a sort where values decrease as you go right is in descending order.
Sometimes, stability is required in sorting.
Stability means that the relative order of elements with equal values is preserved after sorting.
For example, let's say this is the result of a pop quiz for one class.
| Student Name | Score |
|---|---|
| James | 0 |
| Olivia | 90 |
| Michael | 50 |
| Thomas | 50 |
Here's a stable sort in the following order:
| Student Name | Score |
|---|---|
| James | 0 |
| Michael | 50 |
| Thomas | 50 |
| Olivia | 90 |
The relative order of Takeshi Goda and Suneo Bonegawa, who have the same score, remains the same after sorting.
Next, we'll sort it unstably.
| Student Name | Score |
|---|---|
| James | 0 |
| Thomas | 50 |
| Michael | 50 |
| Olivia | 90 |
Takeshi Goda and Susumu Honekawa, who had the same score, have switched places.
In some cases, it's necessary to preserve the original order of people with the same score.
In that case, we must use a stable method.
The purpose of sorting.
If the data was originally arranged randomly, it would be fine to leave it as is. The reason we go out of our way to sort it is, quite simply, to speed up searches. When data is organized, we can estimate where the target value is located, allowing us to search more quickly than when the data is arranged randomly.
Bubble sort
There are indeed a wide variety of sorting algorithms that have been devised.
Among these, Bubble Sort is often discussed due to its ease of understanding.
However, due to its slow speed, it's not a particularly efficient method.
The concept is simple.
First, compare the first and second data points, and if the second is smaller, swap the data.
Next, compare and swap the second and third.We will repeat this until the end of the data.
Once you reach the end of the data, repeat the comparison and exchange from the beginning.
If you repeat this process as many times as the number of data points, the data will be sorted.
This is how Bubble Sort works: repeatedly comparing and swapping adjacent elements until the entire list is sorted.
The implementation of bubble sort as a program is as follows.
For verification purposes, it's often easier to pass a character array by treating the array type as char.
Bubble sort uses a nested loop, resulting in a time complexity of O(N^2).
This corresponds to the third-highest computational complexity estimate.
Bubble sort is an algorithm with a relatively high computational cost and isn't particularly efficient.
Among these, Bubble Sort is often discussed due to its ease of understanding.
However, due to its slow speed, it's not a particularly efficient method.
The concept is simple.
First, compare the first and second data points, and if the second is smaller, swap the data.
Next, compare and swap the second and third.We will repeat this until the end of the data.
Once you reach the end of the data, repeat the comparison and exchange from the beginning.
If you repeat this process as many times as the number of data points, the data will be sorted.
| Comparison of the first and second | (23) | ( 9) | 7 | 15 | 3 | 1 | 30 | 19 |
|---|---|---|---|---|---|---|---|---|
| The second one is small, so replace it. | ( 9) | (23) | 7 | 15 | 3 | 1 | 30 | 19 |
| Comparison of the second and third | 9 | (23) | ( 7) | 15 | 3 | 1 | 30 | 19 |
| The third one is small, so replace it. | 9 | ( 7) | (23) | 15 | 3 | 1 | 30 | 19 |
This is how Bubble Sort works: repeatedly comparing and swapping adjacent elements until the entire list is sorted.
The implementation of bubble sort as a program is as follows.
Source code
/*
Usage
SortBubble(Array to sort, number of elements 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;
}
}
}
}For verification purposes, it's often easier to pass a character array by treating the array type as char.
Bubble sort uses a nested loop, resulting in a time complexity of O(N^2).
This corresponds to the third-highest computational complexity estimate.
Computational complexity
1、log2n、n、nlog2n、n^2、2^n、n!
Bubble sort is an algorithm with a relatively high computational cost and isn't particularly efficient.
About This Site
Learning C language through suffering (Kushi C) isThis is the definitive introduction to the C language.
It systematically explains the basic functions of the C language.
The quality is equal to or higher than commercially available books.
