可変任意の値を変更する

Question

だから、今日私はCで挿入ソートアルゴリズムを実装していましたが、THIS (video)という奇妙なバグで自分自身を見つけました。

整数変数arraySizeは、ループ中に独自の値を変更するだけで、毎回発生することもなく、完全にランダムで、arraySize値を変更するときは、初期化時にコードの先頭にあります値10

コード：出力の

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 


int main() { 
    int y = 0, arraySize = 10, array[1000]; 
    srand(time(NULL)); 
    for (int i = 0; i < arraySize; i++) { 
    array[i] = rand() % 1000; 
    } 
    for (int i = 1; i < arraySize; i++) { 
    for (int j = i; array[j] <= array[j - 1]; j--) { 
     y = array[j - 1]; 
     array[j - 1] = array[j]; 
     array[j] = y; 
    } 
    printf("for externo i = %d, arraySize = %d \n", i, arraySize); 
    } 
    for (int i = 0; i < arraySize; i++) { 
    printf("%d. i = %d ", array[i], i); 
    } 
    printf("\n"); 
    return 0; 
} 

例この正確なプログラムが与えた - 私を、単純な "GCCのinsertionSort.c"

for externo i = 1, arraySize = 10 
for externo i = 2, arraySize = 10 
for externo i = 3, arraySize = 10 
for externo i = 4, arraySize = 5 
10. i = 0 22. i = 1 233. i = 2 343. i = 3 592. i = 4 

for externo i = 1, arraySize = 10 
for externo i = 2, arraySize = 10 
for externo i = 3, arraySize = 10 
for externo i = 4, arraySize = 10 
for externo i = 5, arraySize = 10 
for externo i = 6, arraySize = 10 
for externo i = 7, arraySize = 10 
for externo i = 8, arraySize = 10 
for externo i = 9, arraySize = 10 
54. i = 0 239. i = 1 312. i = 2 313. i = 3 438. i = 4 465. i = 5 827. i = 6 839. i = 7 874. i = 8 935. i = 9 

for externo i = 1, arraySize = 10 
for externo i = 2, arraySize = 10 
for externo i = 3, arraySize = 10 
for externo i = 4, arraySize = 10 
for externo i = 5, arraySize = 10 
for externo i = 6, arraySize = 10 
for externo i = 7, arraySize = 10 
for externo i = 8, arraySize = 10 
for externo i = 9, arraySize = 6 
10. i = 0 58. i = 1 135. i = 2 316. i = 3 411. i = 4 442. i = 5 

してコンパイルされた後、

私はxubuntu 16.04を使用しています。これらはgccの設定です。

組み込み仕様を使用しています。 COLLECT_GCCは= GCC COLLECT_LTO_WRAPPER =は/ usr/libに/ GCC/x86_64の-LinuxベースのGNU/5/LTO-ラッパー ターゲット：で設定x86_64の-LinuxベースGNU ：../src/configure -v --with-pkgversion = 'Ubuntu 5.4.0-6ubuntu1〜16.04.4' --with-bugurl = file：///usr/share/doc/gcc-5/README.Bugs --enable-languages = c、ada、C++、java/lib/lib/lib/lib/lib/lib/lib/lib/lib/lib/lib/lib/-libdir =/usr/lib --enable-nls --with-sysroot =/--enable-clocale = gnu --enable-libstdcxx-debug --enable-threads = libstdcxx-time = yes --with-default-libstdcxx-abi = new --enable-gnu-unique-object --disable-vtable-verify --enable-libmpx --enable-plugin --with-system-zlib - -disable-browser-plugin --enable-java-awt = gtk --enable-gtk-cairo --with-java-home =/usr/lib/jvm/java-1.5.0-gcj-5-amd64/jre --enable-java-home --with-jvm-root-dir =/usr/lib/jvm/java-1.5.0-gcj-5- amd64 - with-arch-directory = amd64 --with-ecj-jar =/usr/share/java/eclipse-ecj.jar - イネーブル - objc-gc - イネーブル - マルチarch - ディセーブル - エラー--with-arch- 32 = i686 --with-abi = m64 --with-multilib-list = m32、m64、mx32 - 有効マルチビット--with-tune =汎用 - イネーブルチェック= release --build = x86_64-linux- GNU --host = x86_64版 - のlinux-gnuの--target = x86_64版 - のlinux-gnuの スレッドモデル：POSIX gccのバージョン5.4.0 20160609（Ubuntuの5.4.0-6ubuntu1〜16.04.4）

Answer 1

この行で -

for (int j = i; array[j] <= array[j - 1]; j--) 

jは、潜在的にバインドされたアクセスものアウトを引き起こすことになる、0未満に行くことができます未定義の振る舞いにつながります。

私はUBを理解したくありませんが、スタック上の他の値を変更すると、arraySizeのようになります。このため

一つの簡単な修正は次のようになります - 代わりに、前述したラインの

for (int j = i; j > 0 && array[j] <= array[j - 1] ; j--) //Short circuiting prevents UB here. 

。

この条件があなたのロジックに適しているかどうか、つまりこれを把握することができます。

Answer 2

このループ：

for (int j = i; array[j] <= array[j - 1]; j--) { 

は、未定義の動作が得られ、（jが0未満になる）配列の先頭をオフに実行することができます。ループ終了条件を評価すると、jが正確にゼロの場合でもUBがすべて発生しますが、別の変数の値を変更する可能性が最も高い原因は、ループ本体で実行される配列の範囲外の変更です。

並べ替えが配列の先頭で停止するようにする必要があります。