Go to Qiita Advent Calendar 2024 Top
LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@mat-MUNET

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

Last updated at Posted at 2024-12-02

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

C言語配列　初期化

配列dは適当な値を初期化しておきます

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

変数間の値の入れ替え

配列の名並び替えの前に変数間の値の入れ替え方を確認します
２つの変数の値を入れ替えるためには、もう一つ変数を用意して、一旦どちらかの値を退避させましょう

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の動きも一回ずつ見ていきましょう

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)に入る値を調べていきます
これを繰り返して、バブルソートが完了します

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

練習用

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

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?