LoginSignup
0
0

More than 3 years have passed since last update.

C言語 ALDS1_2_A Bubble Sort

Last updated at Posted at 2020-04-03

問題

概要

  • 安定なソート
  • 順番が逆になっている隣接要素がなくなるまで、次の処理を繰り返す。
    • 配列の末尾から隣接する要素を順番に比べていき、大小関係が逆ならば交換する。
  • バブルソートの交換回数は反点数、または転倒数と呼ばれ、列の乱れ具合を示す。

コード

#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、イメージ持ててた
    • 実装はしてない
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0