６月２８日オンライン分
====== ソーティング まとめ中 ======
・ソーティング（整列）\\
データをルールに従って並び替える作業 [5,3,2,6,1,4]\\
データが小さいほうから大きいほうに：昇順 [1,2,3,4,5,6]\\
データが大きいほうから小さいほうに：降順 [6,5,4,3,2,1]\\
・一番小さいソート\\
データとデータの交換\\
int a = 1, b = 5;\\
a:1 a:5 \\
b:5 b:1\\
1 5
①a = b; a:5, b:5
②b = a; b:5, a:5
5 5
temporary変数（一時的な作業用変数）をつかう。
int tmp=0;//当たり障りない値で初期化
①tmp = a;
②a = b;
③b = tmp;
これで、一番小さいソート＝２個のデータの入れ替えができる。\\
int a[6] ={5,3,2,6,1,4}; //→1,2,3,4,5,6に並べ替えたい（整列問題）
min c c
[5] [0] [5,3,2,6,1,4] c=0の初期状態
c m
[1] [0] [5,3,2,6,1,4] 最小値探索（index ０～５）
[1] [0] [1,3,2,6,5,4] cm交換
c o c
[1] [1] [1,3,2,6,5,4] cを１増やす
c o c
[3] [1] [1,3,2,6,5,4] c=1の初期状態
c o c m
[3] [1] [1,3,2,6,5,4] 最小値探索(index １～５）
c o
[3] [1] [1,2,3,6,5,4] cm交換
c o o
[3] [2] [1,2,3,6,5,4] cを１増やす
c o o c
[3] [2] [1,2,3,6,5,4] c=2の初期状態
c o o cm
[3] [2] [1,2,3,6,5,4] 最小値探索
c o o
[3] [2] [1,2,3,6,5,4] cm交換（動かず）
c o o o c
[3] [3] [1,2,3,6,5,4] c++
c o o o c
[6] [3] [1,2,3,6,5,4] c=3の初期状態
c o o o c m
[6] [3] [1,2,3,6,5,4] 最小値探索
c o o o o
[6] [3] [1,2,3,4,5,6] cm交換
c o o o o c
[6] [4] [1,2,3,4,5,6] c++
c o o o o o o
[6] [4] [1,2,3,4,5,6] cm交換（動かず）（省略）
上の方法：最小値を選択し、左から順番にソート済み列として並べていく方法（**選択ソート**）\\
単純選択法、素朴な方法、基本選択法、逐次決定法（Selection Sort)\\
効率は、当然よくない。\\
データが、１０個のソート。\\
１回目線形探索 １０個＋入れ替え１\\
２回目線形探索 ９個＋入れ替え１\\
８回目線形探索 ８個＋入れ替え１\\
… \\
１０回目線形探索 １個＋入れ替え１\\
N個のデータ-> N+(N-1)+(N-2)+ ... + 1\\
・ソーティングアルゴリズムには速い遅いがある。\\
・メモリを多く使うものと、少なく使うものがある。\\
著名なソートアルゴリズム\\
・選択ソート\\
・バブルソート\\
・挿入ソート\\
・シェルソート ↑あまり効率よくない\\
---------------- \\
・マージソート ↓早いと噂のソート\\
・クイックソート\\
（↑情報処理技術者試験でよく出るソートアルゴリズム）\\
時間計算量\\
・比較、代入等の操作の回数＝計算の手数の事（計算ステップ数）\\
空間計算量\\
・メモリにどのぐらいアクセスして、どのぐらいメモリを占有するか？\\
時間計算量が少ない（計算ステップが少なく速い）アルゴリズム＝＞メモリを大量に使う\\
↑逆の関係になることが多い\\
メモリを大量に使う ＝＞ 計算ステップは少ない\\
計算ステップが多い ＝＞ メモリ使用量は少ない\\
\\
（時間と空間の）トレードオフの関係という\\
\\
プログラムを見てみる\\
\\
変数の有効範囲＝スコープ（scope)＝変数がどこから見えて、どこから見えないか\\
同じ有効範囲内には、同じ名前の変数は作れない。\\
有効範囲が異なる{}内では同じ名前が使用できて、一番近い宣言のものが優先される\\
{
int b=0;
{
//変数を宣言した場所から｝まで変数は有効
//float b=10;
//同じ名前の変数がなければ、自分のいるかっこの外（上で宣言済みなら）の変数は見える。
//ここでint b=0は参照可能 float b=10がある場合は参照できない（名前がかぶってるので、内側優先）
} //float b=10;はここまで有効
//この位置では、float b=10は参照できない
}//int b=0はここまで有効
int main()
{
int a=10,b=20;
int tmp;
tmp = a;
a = b;
b = tmp;
//a:20 b:10
}
関数内での値の入れ替えはアドレス参照で、解決可能
0x12 0x13 0x14
| 10 | 20 |???|
a b tmp
変数のアドレスを入れ替えるか、アドレスの先の値を直接入れ替えるかする \\
変数のアドレスを入れておく変数 ＝ ポインタ \\
int *a = nullptr;
int *b = nullptr;
a = &va;
b = &vb;