アルゴリズム クイックソート
意外とソート系っていっぱいあるのね
理論上だいたい最速のソート
バブルソート 端からバッシバッシ入れ替える系ソート
選択ソート
挿入ソート
ハッシュ探索
二分探索
static void Main(String args)
{
int data = Generate();
Dump(data, 0, data.Length - 1, 0, 0, 0);
QSort(data, 0, data.Length - 1);
Console.In.Read();
}
メインの所、
int data = Generate(); のGenerate()ってなんだろ？
もしかして、メソッドの宣言かなー？
後の方に、
private static int Generate()
{
return ary.ToArray();
}
リストコレクションのToArray()で戻り値を返しているし。
検索でも出てこない
Dump(data, 0, data.Length - 1, 0, 0, 0);
QSort(data, 0, data.Length - 1);
配列。なのか？
console.In.Read は出力じゃなくて読み込みか
C# Console.Read();とConsole.ReadLine(); の違い - C#を勉強しています。か... - Yahoo!知恵袋
List<int> ary = new List<int>(length);
List<>
要素を順番に保持するコレクションクラス.
List<型名>
Listを作成する
using System.Collections.Generic;
// Listを生成する（string型）
List<string> list = new List<string>();
ary.Add(r.Next(length));
配列とは何が違うんだろう？
そもそもコレクションって
どれだけのデータを格納するかわかってい無いときに使用されるクラス群。
using System.Collections.Generic;
んで、一番使用頻度が高いのがさっき書いた
List クラス
配列との違いは、
・途中にデータを挿入できる
・長さを自由に変更できる
List<int> a = new List<int>(); // 値を順に挿入 a.Add(3); a.Add(2); a.Add(1);こんなんだと、
int 型で List a をつくって、
１番目 ３
2番目 2
３番目 1
a.Insert(1, 4);だと一番目に４を挿入。
。大量のデータを扱う際に配列だと、格納するデータが決まっている。（知らなかった・・・とりあえず、同じ型なら増やせるとおもって）
計算式はまぁ、割りとそのまま。
private static void QSort(int[] data, int low, int high)
int P = data[(low + high + 1) / 2];
int[] data = Generate();
メソッド Generaete
で戻り値をセットした上で、
int P に引数としてワス。
private static bool Scan(int[] data, int P, ref int i, ref int j)
ref
→参照渡し
参考にしたコード
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace QuickSort
{
class Program
{
static void Main(String[] args)
{
int[] data = Generate();
Dump(data, 0, data.Length - 1, 0, 0, 0);
QSort(data, 0, data.Length - 1);
Console.In.Read();
}
private static int[] Generate()
{
const int length = 10;
Random r = new Random();
List<int> ary = new List<int>(length);
for (int i = 0; i < length; i++)
{
ary.Add(r.Next(length));
}
return ary.ToArray();
}
private static void QSort(int[] data, int low, int high)
{
// 要素数が1以下の領域ができた場合、その領域は確定とする。
if (high - low < 1)
return;
// 1. ピボットとして一つ選びそれをPとする。
int P = data[(low + high + 1) / 2];
// 2. 左から順に値を調べ、P以上のものを見つけたらその位置をiとする。
// 3. 右から順に値を調べ、P以下のものを見つけたらその位置をjとする。
// 4. iがjより左にあるのならばその二つの位置を入れ替え、2に戻る。ただし、次の2での探索はiの
int i = low - 1;
int j = high + 1;
while (Scan(data, P, ref i, ref j))
{
Swap(data, i, j);
Dump(data, low, high, P, i, j);
}
// 5. 2に戻らなかった場合、iの左側を境界に分割を行って2つの領域に分け、そのそれぞれに対し
QSort(data, low, i -1);
QSort(data, i, high);
}
private static bool Scan(int[] data, int P, ref int i, ref int j)
{
while (data[++i] < P) ;
while (data[--j] > P) ;
return i < j;
}
private static void Dump(int[] data, int low, int high, int P, int i, int j)
{
foreach (int d in data)
Console.Write("{0}", d);
Console.WriteLine("Low:[0] High:{1} Pivot:{2} Left:{3} Right:{4}", low, high, P, i, j);
}
private static void Swap(int[] data, int i, int j)
{
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}
}
