データの昇順について：コードの一部の意味を教えてください。

Question

データの昇順についてです。
**で囲まれている部分の意味が理解できません。

➀ｎ＝0から始まり、入力されたデータを読み込める間、ｎに+1し続ける
　という部分は分かるのですが、その後の
➁ｋ＝ｎ-1から始まり～～の部分からが分かりません。

データの数？だと思うのですが、いまいち理解できず、困っています。
どなたか教えていただけますでしょうか。よろしくお願いいたします。


#include<stdio.h>
#include<string.h>

int main(int argc, char *argv[]){
    
#define TABLESIZE 10000
int x;
int table[TABLESIZE]; int n;
int k;

**for(n= 0; scanf("%d",&x)==1; n++){
  for(k= n-1; k>=0 && x<table[k]; k--){
    table[k+1]= table[k];
  }
  table[k+1]= x;**
}
for(k= 0; k!=n; k++){
  printf("%d\n",table[k]);
}
return 0;
}

Answer 1

**で囲まれている部分の意味が理解できません。

そういうときは，落ち着いて，

n=0, 1, 2, ... のときの入力値を適当に { 5, 80, 11, ... } とかした時にどのように動いていくのか？
を紙とペンで追ってみればよいです．

要は，そのコードをあなたが忠実に実行（シミュレート）してみる．
そうすればやってることが見えてくるでしょう．
一個データが入力されるたびに，配列をどのように更新しているのか，というのが．
（まぁ，「どのように」＝「昇順」なわけだが）

---

コードが読めない(?)とのことなので，
件の２重forの部分を処理順が分かりやすい（つもりの）形に書き換えてみました．

• ループをwhileに置き換えて，for(A; B; C) の{A,B,C}の処理順を明確化
• ループ条件をwhileに書くのではなく，ループ内で「ループを抜ける条件」としてbreakする形に書いた．

n=0;
while( 1 )//※とにかく無条件にループ
{
  if( scanf("%d",&x) != 1 )break;  //※このループを抜ける条件
  
  //-----↓内側のforの部分↓
  k = n-1;
  while( 1 )//※とにかく無条件にループ
  {
    if( k<0 )break;  //※この内側ループを抜ける条件(1)
    if( x>=table[k] )break;  //※この内側ループを抜ける条件(2)

    table[k+1]= table[k];

    k--;
  }
  //-----↑内側のforの部分↑
  
  table[k+1] = x;
  
  n++;
}

Comments

[za-to]

申し訳ございません。
紙の上に書いて考えたのですが、考え方はわかりました。
しかし、コードと考え方が一致せず、根本的に理解できていない状態です。
コードが読めないという初歩的なつまづきです。。

お手数ですが、コードの詳細を教えて頂けたらと思います。

重ね重ね申し訳ございません。

[fana]

とりあえず読みやすいと思う形に書き替えてみたコードを追記したが，どうかな．

[fana]

本当にちまちまとみていけば良いよ．

最初は n=0 で，とりあえずxに5が入力されたとして，
そうすると k=n-1 だから kの値は-1で，内側のループは if(k<0)break; ですぐに抜けて，
そうすると table[k+1] = x; というのは table[0]に5を代入するわけだ．
なので，この時点での table[] の中身は { 5, 不明, 不明, ... } という状態になるわけだ．
その後 n++; で nの値は1になる．

で，次はxに80がが入力されたとして，
今回は nの値は1なんだから，kの値は0．
内側のループの１個目のifの条件には引っかからない．
２個目のifについてはどうだろうか？
xは80で，table[k]ってのはtable[0]であり，この値は今は5だから，条件を満たす．だから内側ループを抜ける．
table[k+1]=x; ってのは table[1]にxを代入するんだから，
table[] の中身は { 5, 80, 不明, ... } という状態になる．
nを2にして，以下繰り返し…

という形で．
で，内側のループの２つのifの条件を満たさない入力の場合に何が起こるのか？　というのも
コードに忠実に table の中身がどうなるのかを追っていけばいい．
nが5とか6くらいになるあたりまで見てみれば意味がつかめるんじゃないかな？

[za-to]

丁寧な説明ありがとうございます。
とてもわかりやすくて、感動しました。

おかげさまで、最初のコードの何がどの部分を表して処理しているのか理解することが出来ました。

自分もfanaさんのように、分かりやすく説明できるようになりたいと思います！

ありがとうございました！

[fana]

「このコードは何をやってるんだろう？　どう動くんだろう？」となった場合には，
誰でも多かれ少なかれ，このような感じで脳内（だけで無理なら紙上とか）でシミュレーションを行うんじゃないかな，と思います．

また，実際に動作させることができるならば，例えば各所にprintfを仕込んでその時々の変数の値とか，そのprintfを書いた場所をいつ通るのか？等を観察してみる等してみると理解の助けになるかもしれません．
（これは，自分の書いたコードがうまく動かない場合にやることと一緒．「うまく動かん＝どう動いてるのかわからん」なので）

Answer 2

for(k= n-1; k>=0 && x<table[k]; k--){
table[k+1]= table[k];
}
table[k+1]= x;

k=n-1にてtableの末尾(前回までに入力した数-1)を取得します。
このとき、table[k]は現在入力されている最大の数になります。
これよりもxが小さいのであればtable[k]を後ろにズラす必要があります。
kを小さくしていき先頭までズラすか、xよりtable[k]が小さいのであればその次にxを挿入します

Comments

[za-to]

回答ありがとうございます。
初歩的で申し訳ないのですが、kを小さくしていき、table[k]を後ろにずらすとは、どういう仕組みでしょうか？

日本語で説明していただくとわかるのですが、コードが説明のどの部分を表しているのか分からず、根本的に理解できていないです。。

お手数ですが、詳細を教えて頂けたらと思います。

[asm]

> for(k= n-1; k>=0 && x<table[k]; k--){
初期化式: k=n-1 訳: kを現在入力済みの領域の末尾に設定 (末尾から)
条件式: k>=0 && x<table[k] 訳: kが0よりも大きく、かつ、xがtable[k]よりも小さい間は
更新式: k-- 訳: 1ずつ減らしながら(先頭へ向かって)

> table[k+1] = table[k];
table[k]のデータをtable[k+1]へコピー
(ひとつ後ろへずらす)

> table[k+1] = x;
table[k+1]へxを入れる
注: k+1はループ最終段でのk

[za-to]

回答ありがとうございます。

一つずつ減らして更新、一つ後ろにずらすという意味の違いを理解することが出来ました。

申し訳ないのですが、ベストアンサーは、自分の文章理解に、しっくりきたということで、別の方にしました。

回答して頂いたのに申し訳ございません。本当にありがとうございます。

Answer 3

なかなか壮絶に意味不明なコードですね。
tableが初期化されてないなど、致命的な間違いがあるのでこのコードを理解しようとするのはやめときましょう

Comments

[fana]

> tableが初期化されてないなど、致命的な間違いがある

配列 table[] は入力された値を格納していく場所っぽいので，別に中身が初期化されてなくてもよいのでは．

[kazuma-s]

このコードは挿入ソートのコードであり、意味不明なコードではありません。