バブルソート

http://www.geocities.jp/ky_webid/algorithm/002.html


バブルソートとはソートアルゴリズムの中でも基本中の基本。

別名として単純交換法とか基本交換法と呼ばれるらしい。

バブルソートは、隣接する要素同士を比較し、目的の順序に並んでいなければ、その要素同士を交換します。それを配列の末尾から先頭に向かって行い、先頭まで来たら末尾に戻って同じことを繰り返します。この操作を行うと、配列の先頭から順番に並び替えが確定していくことになるのですが、これが泡が浮き上がってくるように見える(らしい)ことからバブルソートという名前が付けられたそうです。

自分で実装してみます。

#include <stdio.h>

#define ARRAY_NUM(a) (sizeof(a)/sizeof(a[0]))

void bubble_sort (int *data,int array_size) {
    int index;
    int fix_index = 0;
    int work;
    
    // 配列の末尾インデックスに変換
    array_size--;
    
    if ( array_size <= 0 ) {
        // そもそも要素数が1以下ならソートする意味がない
        return;
    }
    
    // まず末尾に移動する
    data += array_size;
    
    // 確定要素と配列の末尾インデックスが一致したら終了
    while( fix_index != array_size ) {
        for (index=0;index<array_size-fix_index;index++,data--) {
            // とりあえず降順ソート限定の処理
            if ( *data - *(data-1) > 0 ) {
                // 値の交換処理
                work = *data;
                *data = *(data-1);
                *(data-1) = work;
            }
        }
        
        // 配列をまた末尾まで移動させる
        data += array_size-fix_index++;
    }

}

int main (void) {
    int num[] = { 3,9,11,50,6,34,20,98,6,1 };
    int i;
    
    bubble_sort(num,ARRAY_NUM(num));
    
    for(i=0;i<ARRAY_NUM(num);i++){
        printf("%d ",num[i]);
    }
}

結構時間かかりました。

自分で理解も高めるためにコメント入れながら実装してみました。

とりあえず練習ということで降順ソート限定です。またデータ型もintのみです。

解答例との比較
int array[ARRAY_SIZE] = { 7, 14, 33, 10, 2, 19, 37, 20 };
int i, j, work;

for(i=0; i<ARRAY_SIZE; ++i)  /* 比較作業を止める位置の添字 */
{
    for(j=ARRAY_SIZE-1; j>i; --j) /* 比較対象となる要素の添字 */
    {
        if( array[j] < array[j-1] ) /* 目的の順番の逆になっているか */
        {
            /* 逆になっていたら、並び替えを行う */
            work = array[j];
            array[j] = array[j-1];
            array[j-1] = work;
        }
    }
}

見れば見るほど素晴らしいです。自分の書いたコードが情けないくらい。

そうか、良く考えればループの回数は固定なんですね。なんとなく総当りで調べないといけないからループの回数が不定だと勘違いしてwhileでやってしまいました。

また配列の操作もポインタの移動でやるんじゃなくて添え字でやれば良かったという点も盲点です。ポインタで受け取ったらポインタで操作しなきゃ的な先入観がありました。

やはり言語の仕様を覚えるだけでは全然だめですね。こういったアルゴリズムや実際に何かを組んで慣れていかないといけません。