LoginSignup
0
0

More than 3 years have passed since last update.

C言語 ALDS1_2_B Selection Sort

Last updated at Posted at 2020-04-03

問題

ポイント

  • 挿入ソート、バブルソートと同様に、「ソード済みの部分列」「未ソートの部分列」に分けられる。
  • 計算量はO(n^2)
  • 不安定なソート

コード

#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");
}

/* 選択ソート */
static int selection_sort_count(int A[], int N)
{
    int min_index = 0;
    int count = 0;

    for (int i = 0; i < N - 1; i++)
    {
        min_index = i;
        for (int j = i; j < N; j++)
            if (A[j] < A[min_index])
                min_index = j;
        if (i != min_index)
        {
            swap(&A[i], &A[min_index]);
            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", selection_sort_count(A, N));

    return 0;
}

所感

indexを使って交換回数を減らしている。
コード自体はもやもや違和感がある。

所要時間30分

【復習】

  • 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