C言語　配列の練習 配列のソート

C言語の練習はpaiza.ioで行います

https://paiza.io/projects/RII2j9rl3eyeQ3SETm7Z9w

# C言語配列　初期化
配列dは適当な値を初期化しておきます
```c:example201.c
#include <stdio.h>
int main(void){
    //配列の宣言と初期化
    int d[10]={72,28,40,9,10,14,3,-8,77,11};
    int temp,i; 
  
    //配列に格納されている値を出力
    for(i = 0 ; i < 10 ; i++){
        printf("d[%d] = %d\n",i,d[i]);
    }
}
```
結果を確認しましょう
```:結果
d[0] = 72
d[1] = 28
d[2] = 40
d[3] = 9
d[4] = 10
d[5] = 14
d[6] = 3
d[7] = -8
d[8] = 77
d[9] = 11
```

### 変数間の値の入れ替え
配列の名並び替えの前に変数間の値の入れ替え方を確認します
２つの変数の値を入れ替えるためには、もう一つ変数を用意して、一旦どちらかの値を退避させましょう
```mermaid
graph LR;
a --> |<b><font color="red">①退避|temp
b --> |②|a
temp --> |③|b
```
```c:example202.c
#include <stdio.h>
int main(void){
    int a,b,temp;
    //変数へ値の代入
    a = 10;
    b = 20;
    printf("a=%d  b=%d\n",a,b);

    //値の入れ替え
    temp = a;
    a = b;
    b = temp;
    printf("a=%d  b=%d\n",a,b);
}
```
```:結果
a=10  b=20
a=20  b=10
```

# 配列のソート（並べ替え）
配列の並べ替えにはいくつかの方法があります
次の`example203.c`では __選択ソート__ あるいは __単純選択ソート__ と呼ばれる手順を行っています
`example203.c`では、配列を小さい順・昇順で並べ替えています
この処理で理解しづらい点は 
 for(i = 0 ; __i < 9__ ; i++) と 
for(  __j = i + 1__ ; j<10 ; j++)　でしょうか 

なぜ　`i < 9`  なのでしょうか　
なぜ　`j=i+1` なのでしょうか　これら変数iとjの動きも一回ずつ見ていきましょう

```c:example203.c
#include <stdio.h>
int main(void){
    //配列の宣言と初期化
    int d[10]={72,28,40,9,10,14,3,-8,77,11};
    int temp,i,j; 
  
    //配列に格納されている値を出力
    printf("ソート前\n");
    for(i = 0 ; i < 10 ; i++){
        printf("d[%d] = %d\n",i,d[i]);
    }
    //単純選択ソート
    for(i = 0 ; i < 9 ; i++){
        for(j = i + 1 ; j<10 ; j++){
            //d[i]がd[j]より大きい場合入れ替え
            if(d[i]>d[j]){
                temp = d[i];
                d[i] = d[j];
                d[j] = temp;
            }
        }
    }
    printf("\nソート後\n");
     //配列に格納されている値を出力
    for(i = 0 ; i < 10 ; i++){
        printf("d[%d] = %d\n",i,d[i]);
    }
}
```
```:結果
ソート前
d[0] = 72
d[1] = 28
d[2] = 40
d[3] = 9
d[4] = 10
d[5] = 14
d[6] = 3
d[7] = -8
d[8] = 77
d[9] = 11

ソート後
d[0] = -8
d[1] = 3
d[2] = 9
d[3] = 10
d[4] = 11
d[5] = 14
d[6] = 28
d[7] = 40
d[8] = 72
d[9] = 77
```
#### プログラムの動き　（全て書きました)

予め配列dには適当な値が代入されています
```
d(0) d(1) d(2) d(3) d(4) d(5) d(6) d(7) d(8) d(9)
[72] [28] [40] [ 9] [10] [14] [ 3] [-8] [77] [11]
```
変数`i`が0の時`d(i)=d(0)`をターゲットとして他`9`個の要素と比較します
この時,変数`ｊ`を利用してi+1～9 まで添え字を変更します
そしてもし、`d(i)`が`d(j)`よりも大きい場合、`d(i),d(j)`を入れ替えます
```:i=0
  i    j=i+1
d(0) d(1) d(2) d(3) d(4) d(5) d(6) d(7) d(8) d(9)
[72] [28] [40] [ 9] [10] [14] [ 3] [-8] [77] [11]
  |____↑___↑_____↑____↑____↑____↑____↑____↑____↑
   連続で比較
```
全てと比較し終わると、配列中の最小値がd(0)に格納されます

次に変数iは1となります　今度は`d(i)=d(1)`をターゲットとして他`8`個の要素と比較します
この時,変数`ｊ`を利用してi+1～9 まで添え字を変更します
そしてもし、`d(i)`が`d(j)`よりも大きい場合、`d(i),d(j)`を入れ替えます
あとはこの繰り返しです
```:i=1
       i    j=i+1
d(0) d(1) d(2) d(3) d(4) d(5) d(6) d(7) d(8) d(9)
[-8] [28] [40] [ 9] [10] [14] [ 3] [72] [77] [11]
       |____↑____↑____↑____↑____↑____↑____↑____↑
 ↑d(0)は確定   残りを連続で比較
```
```:i=2
            i    j=i+1
d(0) d(1) d(2) d(3) d(4) d(5) d(6) d(7) d(8) d(9)
[-8] [ 3] [40] [ 9] [10] [14] [28] [72] [77] [11]
            |____↑____↑____↑____↑____↑____↑____↑
 ↑d(0)↑d(1)は確定   残りを連続で比較
```
```:i=3
                 i    j=i+1
d(0) d(1) d(2) d(3) d(4) d(5) d(6) d(7) d(8) d(9)
[-8] [ 3] [ 9] [40] [10] [14] [28] [72] [77] [11]
                 |____↑____↑____↑____↑____↑____↑
 ↑d(0)↑d(1)↑d(2)は確定   残りを連続で比較
```
```:i=4
                      i    j=i+1
d(0) d(1) d(2) d(3) d(4) d(5) d(6) d(7) d(8) d(9)
[-8] [ 3] [ 9] [10] [40] [14] [28] [72] [77] [11]
                      |____↑____↑____↑____↑____↑
 ↑d(0)↑d(1)↑d(2)↑d(3)は確定   残りを連続で比較
```
```:i=5
                           i    j=i+1
d(0) d(1) d(2) d(3) d(4) d(5) d(6) d(7) d(8) d(9)
[-8] [ 3] [ 9] [10] [11] [14] [28] [72] [77] [40]
                           |____↑____↑____↑____↑
 ↑d(0)↑d(1)↑d(2)↑d(3)↑d(4)は確定   残りを連続で比較
```
```:i=6
                                i    j=i+1
d(0) d(1) d(2) d(3) d(4) d(5) d(6) d(7) d(8) d(9)
[-8] [ 3] [ 9] [10] [11] [14] [28] [72] [77] [40]
                                |____↑____↑____↑
 ↑d(0)↑d(1)↑d(2)↑d(3)↑d(4)↑d(5)は確定   残りを連続で比較
```
```:i=7
                                     i    j=i+1
d(0) d(1) d(2) d(3) d(4) d(5) d(6) d(7) d(8) d(9)
[-8] [ 3] [ 9] [10] [11] [14] [28] [72] [77] [40]
                                     |____↑____↑
 ↑d(0)↑d(1)↑d(2)↑d(3)↑d(4)↑d(5)↑d(6)は確定   残りを連続で比較
```
```:i=8
                                          i    j=i+1
d(0) d(1) d(2) d(3) d(4) d(5) d(6) d(7) d(8) d(9)
[-8] [ 3] [ 9] [10] [11] [14] [28] [40] [77] [72]
                                          |____↑
 ↑d(0)↑d(1)↑d(2)↑d(3)↑d(4)↑d(5)↑d(6)↑d(7)は確定   残りを比較
```
変数iが８まで来ると残りの要素はd(9)のみなので、最後にd(8)とd(9)を比較して処理が終了になります。
```
d(0) d(1) d(2) d(3) d(4) d(5) d(6) d(7) d(8) d(9)
[-8] [ 3] [ 9] [10] [11] [14] [28] [40] [72] [77]
```
これでソートが完了しました
変数iは８まで変化すればよく　変数jはiの次の値から始まればよいことがわかります
# バブルソート

バブルソートとは下方から上方へ移動させながら並べ替える手法
泡が湧き上がってくるように下方から上方へ整列していく様子からこの名前がついています
ポイントとしては　`for(j = 9  ; j>=i+1 ; j--)`の動き方です
配列中の最小値を最上位に移動させる処理を見ながら理解しましょう

```c example204.c
#include <stdio.h>
int main(void){
    //配列の宣言と初期化
    int d[10]={72,28,40,9,10,14,3,-8,77,11};
    int temp,i,j; 
  
    //配列に格納されている値を出力
    printf("ソート前\n");
    for(i = 0 ; i < 10 ; i++){
        printf("d[%d] = %d\n",i,d[i]);
    }
    //バブルソート
    for(i = 0 ; i < 9 ; i++){
        for(j = 9  ; j>=i+1 ; j--){
            //d[l-1]がd[j]より大きい場合入れ替え
            if(d[j-1]>d[j]){
                temp = d[j];
                d[j] = d[j-1];
                d[j-1] = temp;
            }
        }
    }
    printf("\nソート後\n");
     //配列に格納されている値を出力
    for(i = 0 ; i < 10 ; i++){
        printf("d[%d] = %d\n",i,d[i]);
    }
}
```
予め配列dには適当な値が代入されています
```
d(0) d(1) d(2) d(3) d(4) d(5) d(6) d(7) d(8) d(9)
[72] [28] [40] [ 9] [10] [14] [ 3] [-8] [77] [11]
```
配列の最後尾から隣り合う２つの要素を比較してる
そしてもし、`d(j-1)`が`d(j)`よりも大きい場合、`d(j-1)とd(j)`を入れ替えます
```:i=0
                                          j-1  j
d(0) d(1) d(2) d(3) d(4) d(5) d(6) d(7) d(8) d(9)
[72] [28] [40] [ 9] [10] [14] [ 3] [-8] [77] [11]
                                          ↑____↑
                                           比較
```
```:i=0
                                     j-1  j
d(0) d(1) d(2) d(3) d(4) d(5) d(6) d(7) d(8) d(9)
[72] [28] [40] [ 9] [10] [14] [ 3] [-8] [11] [77]
                                    ↑____↑
                                     比較
```
```:i=0
                                j-1  j
d(0) d(1) d(2) d(3) d(4) d(5) d(6) d(7) d(8) d(9)
[72] [28] [40] [ 9] [10] [14] [ 3] [-8] [11] [77]
                                ↑____↑
                                 比較
```
```:i=0
                           j-1  j
d(0) d(1) d(2) d(3) d(4) d(5) d(6) d(7) d(8) d(9)
[72] [28] [40] [ 9] [10] [14] [-8] [ 3] [11] [77]
                           ↑____↑
                            比較
```
```:i=0
                      j-1  j
d(0) d(1) d(2) d(3) d(4) d(5) d(6) d(7) d(8) d(9)
[72] [28] [40] [ 9] [10] [-8] [14] [ 3] [11] [77]
                      ↑____↑
                       比較
```
```:i=0
                 j-1  j
d(0) d(1) d(2) d(3) d(4) d(5) d(6) d(7) d(8) d(9)
[72] [28] [40] [ 9] [-8] [10] [14] [ 3] [11] [77]
                 ↑____↑
                  比較
```
```:i=0
            j-1  j
d(0) d(1) d(2) d(3) d(4) d(5) d(6) d(7) d(8) d(9)
[72] [28] [40] [-8] [ 9] [10] [14] [ 3] [11] [77]
            ↑____↑
             比較
```
```:i=0
       j-1  j
d(0) d(1) d(2) d(3) d(4) d(5) d(6) d(7) d(8) d(9)
[72] [28] [-8] [40] [ 9] [10] [14] [ 3] [11] [77]
       ↑____↑
        比較
```
```:i=0
  j-1  j
d(0) d(1) d(2) d(3) d(4) d(5) d(6) d(7) d(8) d(9)
[72] [-8] [28] [40] [ 9] [10] [14] [ 3] [11] [77]
  ↑____↑
   比較
```
```:i=0
d(0) d(1) d(2) d(3) d(4) d(5) d(6) d(7) d(8) d(9)
[-8] [72] [28] [40] [ 9] [10] [14] [ 3] [11] [77]
```
配列中の最小値である`-8`が最上位に移動したことがわかります
これでd(0)は確定です　次はd(1)に入る値を調べていきます
これを繰り返して、バブルソートが完了します

ソートのアルゴリズムは、先ず動き方をしっかり覚えて、ポイントになる処理を理解しましょう

### 練習用
```c:
//配列の宣言と初期化
    int d[20]={72,28,40,9,10,14,3,-8,77,11,23,44,-9,-3,100,-100,33,5,17};

```