クイックソートアルゴリズム（C＃）

Question

このコードで実際に何が問題なのか尋ねたいと思います。その後、私は自分でそれをコード化しようとしたとここに上陸したhttp://me.dt.in.th/page/Quicksort/#disqus_thread：私はので、私はこのページに見て自分でクイックソート（2ウェイ）を理解しようとした

public void Sort(Comparison<TList> del, long l, long r) 
    { 
     // inspired by: http://me.dt.in.th/page/Quicksort/ 
     if (l >= r) return; 

     // partitioning 
     for(long i = l + 1; i <= r; i++) 
     { 
      if (del.Invoke(this[i], this[l]) < 0) 
      { 
       Swap(i, l); 
      } 
     } 

     // recursion 
     Sort(del, l, l - 1); 
     Sort(del, l + 1, r); 
    } 

その後、私が言及したウェブサイト上のコメントの中に見えました

void qsort(char *v[], int left, int right) 
{ 
    int i, last; 
    void swap(char *v[], int i, int j); 

    if (left >= right) 
     return; 
    swap(v, left, (left + right)/2); 

    last = left; 

    for (i = left + 1; i <= right; i++) 
     if (strcmp(v[i], v[left]) < 0) 
      swap(v, ++last, i); 
    swap(v, left, last); 
    qsort(v, left, last - 1); 
    qsort(v, last + 1, right); 
} 

と私のコードはまだ、この（それは仕方によってリンクされたリストに含まれています）でそれをテストし、働いている理由今私は本当に興味：

static void Main(string[] args) 
    { 
     MyList<int> obj; 

     do 
     { 
      obj = MyList.Random(100, 0, 100); 
      obj.Sort(stdc); 
      obj.Sort(stdc); 
     } while (obj.IsSorted(stdc)); 

     Log("Not sorted", obj); 

     Console.ReadKey(true); 
    } 

とこれを見つけましたこの：

public bool IsSorted(Comparison<TList> del) 
    { 
     var el = start; 

     if (el != null) 
     { 
      while (el.Next != null) 
      { 
       if (del.Invoke(el.Value, el.Next.Value) > 0) // eq. to this[i] > this[i + 1] 
        return false; 
       el = el.Next; 
      } 
     } 

     return true; 
    } 

をし、この：

public static MyList<int> Random(int num, int min = 0, int max = 1) 
    { 
     var res = new MyList<int>(); 
     var rand = new Random(); 

     while (num > 0) 
     { 
      res.Add(rand.Next(min, max)); 
      num--; 
     } 

     return res; 
    } 

Answer 1

あなたのクイックソートのコードは本当にクイックソートではなく、それが遅くなります。 recursed intoコールがl> =（l-1）を検出するため、回線

は何も行いません。ライン

 Sort(del, l + 1, r); 

は、[L + 1、R] 1つによってパーティション[L、R]の大きさを減少させるので、時間計算量は、常にはO（n^2）であろうが、それはのように見えますそれはちょうど、ゆっくりと動作します。

qsort（）関数は左と中央の値を入れ替えます。これは、データがすでにソートされているにもかかわらず、あまり多くのことを行わない場合、最悪の場合の問題を回避します。キーはそれが "last"を更新するので、パーティションが完了したときにv [last]の値がピボット値になり、 "left"の代わりに "last"を使用するか、コードの場合に再帰呼び出しが行われます、 "l"。

示されたqsortは、Lomutoパーティション方式のバリエーションです。あなたに実行しているどのような問題

https://en.wikipedia.org/wiki/Quicksort#Algorithm