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:
| ソート前 | 23 | 9 | 7 | 15 | 3 | 1 | 30 | 19 |
|---|---|---|---|---|---|---|---|---|
| ソート後 | 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.
| 生徒名 | 点数 |
|---|---|
| James | 0 |
| Olivia | 90 |
| Michael | 50 |
| Emma | 50 |
Here's a stable sort in the following order:
| 生徒名 | 点数 |
|---|---|
| James | 0 |
| Michael | 50 |
| Emma | 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.
| 生徒名 | 点数 |
|---|---|
| James | 0 |
| Emma | 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.
もともとでたらめに並んでいたのならそのままにしておけばよいのに、
わざわざそれをソートする理由は、ズバリSearchの高速化のためIt is.
データがそろえられていると、目的の値がどこにあるか見当がつき、
It can be searched faster than if the data were arranged arbitrarily.
わざわざそれをソートする理由は、ズバリSearchの高速化のためIt is.
データがそろえられていると、目的の値がどこにあるか見当がつき、
It can be searched faster than if the data were arranged arbitrarily.
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.
| 1つ目と2つ目の比較 | (23) | ( 9) | 7 | 15 | 3 | 1 | 30 | 19 |
|---|---|---|---|---|---|---|---|---|
| 2つ目が小さいので交換 | ( 9) | (23) | 7 | 15 | 3 | 1 | 30 | 19 |
| 2つ目と3つ目の比較 | 9 | (23) | ( 7) | 15 | 3 | 1 | 30 | 19 |
| 3つ目が小さいので交換 | 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
/*
使用法
SortBubble(ソートするarray、ソートする個数);
*/
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.
