Help us understand the problem. What is going on with this article?

C言語でバブルソート

More than 1 year has passed since last update.

バブルソートとは

隣と比べて、逆順なら入れ替える。

隣接する2項を比較し、$a_{i-1} < a_i$となるように、右から左に操作(入れ替え)する。この場合、最左端が最小値となる。

サンプルコード

ここでは、int型の配列を、バブルソートを用いて小さい順に並べ替える。

bubble_sort.c
#include<stdio.h>

/* 値を入れ替える関数 */
void swap (int *x, int *y) {
  int temp;    // 値を一時保存する変数

  temp = *x;
  *x = *y;
  *y = temp;
}

/* バブルソート */
void bubble_sort (int array[], int array_size) {
  int i, j;

  for (i = 0; i < array_size - 1; i++){
    for (j = array_size - 1; j >= i + 1; j--){   // 右から左に操作
      if (array[j] < array[j-1]) { swap(&array[j], &array[j-1]); }
    }
  }
}

int main (void) {
  int array[10] = { 2, 1, 8, 5, 4, 7, 9, 0, 6, 3 };
  int i;

  printf("Before sort: ");
  for (i = 0; i < 10; i++) { printf("%d ", array[i]); }
  printf("\n");

  bubble_sort(array, 10);

  printf("After sort: ");
  for (i = 0; i < 10; i++) { printf("%d ", array[i]); }
  printf("\n");

  return 0;
}

実行結果

Before sort: 2 1 8 5 4 7 9 0 6 3
After sort: 0 1 2 3 4 5 6 7 8 9

性能

  • 比較回数
    • $i=0,1,\cdots,n-1$のそれぞれについて、$j=i+1,i+2,\cdots,n$の$n-1$回の比較を行う。
    • 比較回数は$\sum^{n-1}_{i=0}{(n-1)}=n(n-1)/2\to O(n^2)$
  • 交換回数
    • 最良の場合:0回
    • 最悪の場合:$n(n-1)/2$回$\to O(n^2)$
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした