6．1 ソートの考え方
番号 以下をクリックすると，該当箇所にジャンプします （１） ソートとは （２） ソートの安定性 （３） 内部ソートと外部ソート --- 確認用プログラムの枠組み （１）ソートとは 与えられたデータの集合を キーとなる項目の大小関係により， 一定の順序に並び替えることを整列（ソート：sorting）といいます。 　　　　 キーの小さい順に並べることを昇順（ascending order）， 大きい順に並べることを降順（descending order）といいます。 （２）ソートの安定性 等しいキーを持つデータの位置関係が， ソート後も維持されるソートを安定な（stable）ソートといいます。 　　　　 （３）内部ソートと外部ソート ソート対象のデータがメモリ内に格納できる場合と， 大量すぎてメモリに格納できない場合で ソートの処理は異なることになります。 そこで次のように分類することができます。 ■内部ソート 　対象とするデータがメモリ上に格納できる場合 ■外部ソート 　対象とするデータが大量すぎて，メモリに格納できない場合 ただし，外部ソートは， 部分的に内部ソートした結果を作業ファイルに出力し 内部ソートした結果と作業ファイルとのマージによって 実現することができます。 すなわち，内部ソートが基本的なソートとなりますので， 以下，内部ソートについて説明します。 番号 以下をクリックすると，該当箇所にジャンプします （１） ソートとは （２） ソートの安定性 （３） 内部ソートと外部ソート --- 確認用プログラムの枠組み [確認用プログラムの枠組み] 以下，様々なソートのプログラムを示します。 その確認用プログラムの共通ルーチンやデータ宣言等を 以下に示します。 ［フォーム定義］ 　　　　　　　 処理本体は，それぞれの節で示します。以下は，枠組みのみです。 private int[] Data=new int[8]; private void swap(ref int A,ref int B) { int X=A; A=B; B=X;} private void ソート後表示() { 　listBox2.Items.Clear(); 　for(int i=0;i<Data.Length;i++) 　　　 listBox2.Items.Add(i.ToString()+" : "+Data[i].ToString()); } private void Form1_Load(object sender, System.EventArgs e) { 初期設定(); } private void 初期設定()　// 確認用データは，乱数発生により生成する { 　　int i; 　　Random myRandom = new Random(); 　　for(i=0;i<Data.Length;i++)Data[i]=myRandom.Next(10,99); 　　listBox1.Items.Clear(); 　　for(i=0;i<Data.Length;i++) 　　　　listBox1.Items.Add(i.ToString()+" : " +Data[i].ToString()); 　　listBox2.Items.Clear(); } private void button1_Click(object sender, System.EventArgs e) {　　バブルソート(); ソート後表示(); } private void button2_Click(object sender, System.EventArgs e) {　　 初期設定();} private void button3_Click(object sender, System.EventArgs e) {　　バブルソート改良版();　ソート後表示();} private void button4_Click(object sender, System.EventArgs e) {　　単純選択法();　ソート後表示();} private void button5_Click(object sender, System.EventArgs e) {　　単純挿入法();　ソート後表示();} private void button6_Click(object sender, System.EventArgs e) {　　シェルソート();　ソート後表示();} private void button7_Click(object sender, System.EventArgs e) {　　シェルソート改良版();　ソート後表示();} private void button8_Click(object sender, System.EventArgs e) {　　クイックソート();　ソート後表示(); } private void button9_Click(object sender, System.EventArgs e) {　　非再帰クイックソート();　ソート後表示(); } private void button10_Click(object sender, System.EventArgs e) {　　ヒープソート();　ソート後表示();　} private void button11_Click(object sender, System.EventArgs e) {　　マージソート();　ソート後表示(); } private void button12_Click(object sender, System.EventArgs e) {　　度数ソート();　　ソート後表示(); } 番号 以下をクリックすると，該当箇所にジャンプします （１） ソートとは （２） ソートの安定性 （３） 内部ソートと外部ソート --- 確認用プログラムの枠組み 1. 基本的なアルゴリズム 2. 基本的なデータ構造 3. 操作を伴うデータ構造 4. 探索 5. 再帰的アルゴリズム 6. ソート 7. 集合 8. 文字列処理 9. 色々なアルゴリズム 上のタイトルをクリックします