1.単純交換法(Bubble Sort、バブルソート)とは
単純交換法(Bubble Sort、バブルソート)とは、決定項が先頭に向かって泡(Bubble)のように浮き上がるとこから、名前が付けられました。
このソート法は集合体の最後尾からスキャンして、隣接する項の大小関係が反対ならば交換していくという単純なソート法です。
そして計算量はソートする項の個数の二乗になります。
単純交換法(Bubble Sort、バブルソート)は安定しているソートアルゴリズムです。
このソート法は集合体の最後尾からスキャンして、隣接する項の大小関係が反対ならば交換していくという単純なソート法です。
そして計算量はソートする項の個数の二乗になります。
単純交換法(Bubble Sort、バブルソート)は安定しているソートアルゴリズムです。
2.単純交換法(Bubble Sort、バブルソート)の実装
1.ソートをしていない項を「0 〜 最後尾未満」まで、以下を繰り返す。
2.初期値を最後尾とし、判定する項がソート済みの項未満まで以下を繰り返す
3.判定する項と隣の項と比べ、大小関係が反対ならば交換する
*ptrはint型変数の配列への先頭ポインタ、nはデータの個数です。
void bubble_sort(int *ptr, int n)
{
int i, j;
for(i=0; i<n-1; i++){
for(j=n-1; j>i; j--){
if(*(ptr+j-1) > *(ptr+j)){
swap((ptr+j-1), (ptr+j));
}
}
}
}
void swap(int *ptr1, int *ptr2)
{
int w;
w = *ptr1;
*ptr1 = *ptr2;
*ptr2 = w;
}
また、
if(*(ptr+j-1) > *(ptr+j)){
を
if(*(ptr+j-1) < *(ptr+j)){
のように、判定条件を変更すると降順になります。
今回のサンプルソースは昇順です。