ソーティング　まとめ中

・ソーティング（整列）
データをルールに従って並び替える作業 [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;