[C言語] 整数を昇順でソートする

質問

このサイト(http://www.kusa.ac.jp/~kajiura/c/hairetsu/newpage3.htm)で、整数を昇順でソートするソースコードが示されています。しかし、for文の中にfor文、その中にif文を用いた箇所が何を実行しているのか全く理解できません。どのような思考を持てばこのようなソースコードに到るのだろう、と困惑しています。自力で書いてみるつもりでしたが、2時間くらい考えて書けませんでした。もっと簡単な方法はないのでしょうか。

#include <stdio.h>
#define SIZE 5
main()
{
int j, k, temp, x[SIZE];
printf("5個の整数を入力してください\n");
printf("昇順に並べ替えて出力します\n");
/* 入力 */
for(j = 0 ; j < SIZE ; j++)
{
printf("deta = ");
scanf("%d", &x[j]);
}
/* 並べ替え */
for(j = 0 ; j < SIZE - 1; j++)
for(k = j + 1; k < SIZE ; k++)
if(x[j] > x[k])
{
temp = x[j];
x[j] = x[k];
x[k] = temp;
}
/* 出力 */
for(j = 0; j < SIZE ; j++)
printf("%d\n", x[j]);
}

回答No.5

επιστημη（@episteme）

> もっと簡単な方法はないのでしょうか。

これが最も簡単な方法(のひとつ)です。
10枚のカードを昇順に並べることを考えましょう。

まず手札10枚からスタート。
1- 手札の中から最も小さいカードを見つけて場に出す。
　これにはfor-loopとif文で実装できます。ココわかりますか?
2- (1)によって手札が1枚少なくなった。手札がなくなるまで(1)を繰り返す
　これを行うにはfor-loopひとつで実装できます。

1,2をまとめると
「for文の中にfor文、その中にif文を用い」ればソートできるってことです。

これ以上簡単な手順が思いつきますか?

回答No.4

f272

#1です。

申し訳ない。#3さんの言うとおり選択ソートです。

回答No.3

επιστημη（@episteme）

厳密にはバブルソートではありませんね。
バブルソートは「隣り合う２要素の順序が逆転していたら交換」を繰り返すもの。

示されたコードは「i番目から配列の末尾までの中から最も小さい要素をi番目と交換」を繰り返しています。これは選択ソートです。

回答No.2

maiko0333

＞2時間くらい考えて
２時間？なぜ３時間考えない？なぜ４時間考えない？という先生がいましたね。
自力で解くのが勉強になるのです。

なお、このソートは要素の数が増えると２乗のオーダーで時間がかかります。
要素の数が多いときには使わないようにね。

回答No.1

f272

いわゆるバブルソートと言われるものです。
https://ja.wikipedia.org/wiki/バブルソート
if(x[j] > x[k])
{
temp = x[j];
x[j] = x[k];
x[k] = temp;
}
これはx[j]がx[k]よりも大きかったら，両者を交換しています。
これが
for(j = 0 ; j < SIZE - 1; j++)
for(k = j + 1; k < SIZE ; k++)
この2重ループの中に入っているわけです。
外側のループでjを決めます。
jを固定して考えると，今度は内側のループでそのjよりも大きいインデックスkを決めてx[j]とx[k]を比較するのです。後ろにあるx[k]の方が小さかったら交換するのですから，内側のループが終わったときにはjよりも後ろにあった要素のうちで一番小さい要素が最も前に来ているはずです。
その後外側のループでjを一つづつ増やして行くと，小さい方から順に要素が決まっていきますね。

> もっと簡単な方法はないのでしょうか。

ソートするやり方はいくつもありますが，バブルソートは最も簡単な方法の一つです。