バブルソート (Bubble Sort)

C 言語による実装

bubblesort.c

/*
  バブルソート (Bubble Sort):
  リストにおいて基点となる要素とそれ以外の要素の値を比較して
  条件応じた交換を行う整列アルゴリズム.
  条件とは,
  (昇順): 値の小さい順
  (降順): 値の大きい順
  このソートを実行すると値の大きいまたは小さい要素が浮かび上がって
  くるようにみえるから, バブル (bubble: 泡) と呼ばれる.
*/

/*
  アルゴリズム分析:
  1. リストから要素を一つ取り出す, 基点となる要素 'A'
  2. 要素 'A' と要素 'B' の値を比較する
  3. 要素 'A' が 要素 'B' より大きいなら, 要素 'A' と 要素 'B' の値を
     交換する
  4. 要素 'A' と 要素 'C', 要素 'A' と 要素 'D' のように各要素との比較
     と交換をリストの終端まで行う
  5. リストの中で最も大きい値を持つ要素または小さい要素が基点となった位置
     へ浮かび上がる
  6. 基点となる要素を次へ進めて (要素 'B') リストの終端まで
     STEP 2 <-> STEP 6 を繰り返す
*/

#include <stdio.h>

void swap(int *x, int *y);
void bubblesort(int nums[], int array_size);

int main(void){
  int i;
  
  /* unsorted list */
  int list[10] = {10, 8, 15, 20, 10, 35, 25, 70, 6, 9};
  
  bubblesort(list, 10);
  
  for(i = 0; i < 10; i++){
    printf("%d ", list[i]);
  }
  printf("\n");
  
  return 0;
}

void swap(int *x, int *y){
  int temp;
  temp = *x;
  *x = *y;
  *y = temp;
}

void bubblesort(int nums[], int array_size){
  int i, j;
  
  for(i = 0; i < array_size; i++){
    for(j = i + 1; j < array_size; j++){
      /* 昇順の条件: > */
      /* 降順の条件: < */
      if(nums[i] > nums[j]) swap(&nums[i], &nums[j]);
    }
  }
}

bubblesort.c の実行結果は:

[cactus:~/code_c/ad]% ./bubblesort
6 8 9 10 10 15 20 25 35 70