問題
概要
- 安定なソート
- 順番が逆になっている隣接要素がなくなるまで、次の処理を繰り返す。
- 配列の末尾から隣接する要素を順番に比べていき、大小関係が逆ならば交換する。
- バブルソートの交換回数は反点数、または転倒数と呼ばれ、列の乱れ具合を示す。
コード
#include <stdio.h>
static void swap(int *a, int *b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
static void print_array(int array[], int array_len)
{
for (int i = 0; i < array_len; i++)
{
printf("%d", array[i]);
if (i != array_len - 1)
printf(" ");
}
printf("\n");
}
/* バブルソート */
int bubble_sort_count(int A[], int N)
{
int count = 0;
for (int i = 0; i < N - 1; i++)
for (int j = 0; j + 1 < N - i; j++)
if (A[j] > A[j + 1])
{
swap(&A[j], &A[j+ 1]);
count++;
}
print_array(A, N);
return count;
}
int main(void)
{
int N;
int A[100];
scanf("%d", &N);
for (int i = 0; i < N; i++)
scanf("%d", &A[i]);
printf("%d\n", bubble_sort_count(A, N));
return 0;
}
ポイント
A[j] < A[j-1]
を
A[j] <= A[j-1]としてしまうと、安定ではなくなる。
所感
バブルソート勘違いしていて、別のやり方をずっとバブルソートだと思っていた。隣り合う値を交換していく。
自分なりの書き方とか試行していると、時間かかる。
所要時間80分
【復習】
- 2020/04/05
- OK、イメージ持ててた
- 実装はしてない