問題
ポイント
- 挿入ソート、バブルソートと同様に、「ソード済みの部分列」「未ソートの部分列」に分けられる。
- 計算量は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,イメージできた
- 実装はしてない