読者です 読者をやめる 読者になる 読者になる

アルゴリズム クイックソート

意外とソート系っていっぱいあるのね

 

アルゴリズム入門講座: クイックソート

 

理論上だいたい最速のソート

blog.codebook-10000.com

 

バブルソート 端からバッシバッシ入れ替える系ソート

ヒープソート

マージソート

バブルソート

選択ソート

挿入ソート

ハッシュ探索

二分探索

 

 

        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型 - C#プチリファレンス

List<>

要素を順番に保持するコレクションクラス.

List<型名>

 

Listを作成する

using System.Collections.Generic;

// Listを生成する(string型)
List<string> list = new List<string>();



ary.Add(r.Next(length));

csharp.sevendays-study.com




配列とは何が違うんだろう?

そもそもコレクションって
どれだけのデータを格納するかわかってい無いときに使用されるクラス群。
using System.Collections.Generic;

んで、一番使用頻度が高いのがさっき書いた

List クラス

配列との違いは、
・途中にデータを挿入できる
・長さを自由に変更できる

            List<int> a = new List<int>();
            //  値を順に挿入
            a.Add(3);
            a.Add(2);
            a.Add(1);
 
こんなんだと、
int 型で List a をつくって、
1番目 3
2番目  2
3番目 1
 

            a.Insert(1, 4);
だと一番目に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
→参照渡し

参考にしたコード

ソフトウェア雑工学 : C#でクイックソートを書いてみる



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;




        }
    }
}