練習 5（提出プログラム名：p1105a.c）※加点対象
この問題は中級クラスの受講生は必須ではない（提出しなくてもよい）が，
上級クラスの受講生は必須とする．
なお，どちらのクラスであっても適切に正解すれば加点対象として扱う．
まず，このプログラム（p1105a.c）をダウンロードしなさい．
そして，この中の関数 check_sort_time と bubble_sort を編集して
以下の実行例と同じ動きをする（秒数は各自のPCに依存）プログラムに仕上げなさい．
この関数では，以下の処理を行っている：
① 整数 n を引数として受け取り，長さ n の int 配列のメモリを確保する（下記参照）．
② ①でメモリ確保した配列に対し，先頭から n, n-1, n-2, …, 2, 1 という整数を順に書き込む．
③ バブルソートのアルゴリズム（下記参照）に従って，その配列の内容を昇順（小さい順）
に並べ替える．（関数 bubble_sort でこれを実行する）
④ 配列のメモリを解放する．
⑤ ③のソーティングにかかった時間を return する．
【編集すべき内容】
上記の手順のうち，①②に該当する内容を check_sort_time 内で完成させなさい．
あわせて，③に該当する関数 bubble_sort も完成させなさい．
（ダウンロードしたプログラムでは，④⑤に該当する部分は既に書いてあるので何もしなくてよい）
なお，n は 1 以上の整数であると仮定してプログラムを作って良い．
この問題では check_sort_time と bubble_sort の中身のみを編集し，それ以外は変更しないこと．
【①で行うメモリ確保のやり方】
講義資料の最後の部分で説明したように，配列のためのメモリ確保をプログラムの実行開始後に行うこともできます．（より高度なプログラミングではよく使います．）
具体的には，
a = malloc(sizeof(int)*n);
または
a = calloc(n, sizeof(int));
と書くと，長さ n の int 配列のメモリが確保され，その先頭アドレスがポインタ a へ代入されます．
もしもメモリ確保に失敗した場合は a の値が NULL という特別な値になりますが，今回はこのエラー処理は割愛します．
【③で実装するバブルソートのアルゴリズム】
詳しくは「データ構造とアルゴリズム」の講義で扱うことになりますが，
配列に格納されている数値を昇順または降順に並べ替える基本的な手順（アルゴリズム）
にバブルソートがあります．
＜具体的なアルゴリズム＞
いま，a[0] ～ a[n-1] に n 個の数値が格納されているとします．
この時，次の手順①～③を実行すると数値を昇順（小さい順）に並べ替えることができます．
① i を 0 以上 n 未満の範囲で 1 ずつ増やしながら以下の②～③を繰り返す：
② j を 0 以上 n-i-1 未満の範囲で 1 ずつ増やしながら③を繰り返す：
③もし a[j] > a[j+1] ならば a[j] と a[j+1] の値を入れ替える．
以上がバブルソートのアルゴリズムであり，並べ替え作業の作業量が
配列長の n の 2 乗に比例するので，n を 2 倍にすれば処理時間は 4 倍程度かかるようになります．
これを体験してもらいたいというのが本練習問題の主旨です．
- 【プログラムの実行例】（その１）※赤字は実行時にキーボードから入力する内容
※実際の計算時間は各自のマシンの性能によって変わりますので，データ数は適宜変えて試しても構いません．
配列長を入力してください：20000 20000 個の整数の並べ替えに 0.54 秒かかりました⏎
- 【プログラムの実行例】（その２）※赤字は実行時にキーボードから入力する内容
※実行例１の 2 倍のデータ数に対して，時間は約 4 倍になります．
配列長を入力してください：40000 40000 個の整数の並べ替えに 2.13 秒かかりました⏎
- 【プログラムの実行例】（その３）※赤字は実行時にキーボードから入力する内容
※実行例１の 4 倍のデータ数に対して，時間は約 16 倍になります．
配列長を入力してください：80000 80000 個の整数の並べ替えに 8.63 秒かかりました⏎
【過去にあったミス（減点となり，やり直しを命じられる）】
■ 3 種類の実行例を確認せずに提出してしまっている．
■ インデントに不備がある（VSCode 上でインデントを自動で揃える作業をやっていない）．
第１１回（Cプログラミング；3 限目の方）の練習問題は以上の５問です．
p1101a.c ～ p1105a.c を Moodle から提出してください．※ただし，p1105a.c は必須ではないです．
くれぐれも各問題で記載されている注意事項や「過去にあったミス」を見落とさないようにしてください．
なお，コンパイルエラーや無限ループになるプログラムを 1 個でも提出した場合は総合評価を 0 点とするので十分に注意すること．
なお，提出後に間違いに気付いた場合，〆切前であれば差し替え（上書き）は可能です．