単純交換法(Bubble Sort、バブルソート)

単純交換法(Bubble Sort、バブルソート)とは、決定項が先頭に向かって泡(Bubble)のように浮き上がるとこから、名前が付けられました。

このソート法は集合体の最後尾からスキャンして、隣接する項の大小関係が反対ならば交換していくという単純なソート法です。そして計算量はソートする項の個数の二乗になります。

単純交換法(Bubble Sort、バブルソート)は安定しているソートアルゴリズムです。

ソートをしていない項を「0 ～最後尾未満」まで、以下を繰り返す。
初期値を最後尾とし、判定する項がソート済みの項未満まで以下を繰り返す。
判定する項と隣の項と比べ、大小関係が反対ならば交換する

*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)){

のように、判定条件を変更すると降順になります。今回のサンプルソースは昇順です。

以下のリンクからサンプルを閲覧又はダウンロードできます。
このサンプルはSHIFT-JISで書かれております。

閲覧またはダウンロード