C# fonksiyonel quicksort ben linq kullanarak C# kullanarak işlevsel bir tarzda quicksort uygulamaya çalışıyorum

Question

başarısız olduğunu ve rastgele çalışan bu kodu/çalışmıyor ve neden bilemiyorum.
Önemli: Bunu bir dizide veya listede çağırdığımda, düzgün çalışıyor. Ama üzerinde bilinmeyen-ne o-gerçekten-edilir, bu (değerleri veya çöküyor, genellikle bazen çalışır kaybeder..) Deli IEnumerable gider
kodu:

public static IEnumerable<T> Quicksort<T>(this IEnumerable<T> source) 
     where T : IComparable<T> 
    { 
     if (!source.Any()) 
      yield break; 
     var pivot = source.First(); 
     var sortedQuery = source.Skip(1).Where(a => a.CompareTo(source.First()) <= 0).Quicksort() 
          .Concat(new[] { pivot }) 
          .Concat(source.Skip(1).Where(a => a.CompareTo(source.First()) > 0).Quicksort()); 
     foreach (T key in sortedQuery) 
      yield return key; 
    } 

Eğer herhangi bir hataları bulabilir Bu, bunun başarısız olmasına neden olur mu?

Düzenleme

: Bazı daha iyi bir test kodu: SQL veya Varlık Çerçeve sorguları Linq tarafından döndürülen gibi

 var rand = new Random(); 
     var ienum = Enumerable.Range(1, 100).Select(a => rand.Next()); 
     var array = ienum.ToArray(); 
     try 
     { 
      array.Quicksort().Count(); 
      Console.WriteLine("Array went fine."); 
     } 
     catch (Exception ex) 
     { 
      Console.WriteLine("Array did not go fine ({0}).", ex.Message); 
     } 
     try 
     { 
      ienum.Quicksort().Count(); 
      Console.WriteLine("IEnumerable went fine."); 
     } 
     catch (Exception ex) 
     { 
      Console.WriteLine("IEnumerable did not go fine ({0}).", ex.Message); 
     } 

Answer 1

Bazı enumerable örnekleri, sadece bir kez iterated üzere tasarlanmıştır. Kodunuz, birden çok yineleme gerektirir ve bu tür durumlarda garip ya da garip davranır. Bu numaralandırmaları ToArray() ile veya ilk olarak benzer bir yöntemle gerçekleştirmelisiniz. Ayrıca pivot böylece birinci ve kalan elemanları yineleme tutmak zorunda kalmamasıdır yeniden edilmelidir

. Bu sorunu tamamen çözmek olmayabilir, ama bazı durumlarda yardım edeceğiz: (. Ayrıca sortedQuery aracılığıyla yinelemek gerekmez - sadece geri, zaten bir IEnumerable<T> var)

public static IEnumerable<T> Quicksort<T>(this IEnumerable<T> source) 
    where T : IComparable<T> 
{ 
    if (!source.Any()) 
     return source; 
    var pivot = source.First(); 
    var remaining = source.Skip(1); 
    return remaining 
     .Where(a => a.CompareTo(pivot) <= 0).Quicksort() 
     .Concat(new[] { pivot }) 
     .Concat(remaining.Where(a => a.CompareTo(pivot) > 0).Quicksort()); 
} 

İlgili bir notta, neden bu işlevselliği yeniden uygulama gereği duyuyorsunuz? Enumerable.OrderBy zaten sizin için yapıyor.

---

Tepki güncellemek için: test yanlış değil, algoritma olduğu için

Kişisel testler başarısız oluyor.

Random, deterministik olmayan bir girdi kaynağıdır ve yukarıda açıkladığım gibi sıralama yönteminin, aynı sıra üzerinde birden çok yineleme gerçekleştirmesi gerekir. Dizi tamamen rastgele ise, sonraki iterasyonlarda farklı değerler elde edilir. Esasen, elemanları değişmeye devam eden bir diziyi çabuklaştırmaya çalışıyorsunuz!

Testin başarılı olmasını istiyorsanız, numaralı numaralı girdiyi girmeniz gerekir. rasgele sayı üreteci için tohum kullanın:

static IEnumerable<int> GetRandomInput(int seed, int length) 
{ 
    Random rand = new Random(seed); 
    for (int i = 0; i < length; i++) 
    { 
     yield return rand.Next(); 
    } 
} 

Ardından:

static void Main(string[] args) 
{ 
    var sequence = GetRandomInput(248917, 100); 
    int lastNum = 0; 
    bool isSorted = true; 
    foreach (int num in sequence.Quicksort()) 
    { 
     if (num < lastNum) 
     { 
      isSorted = false; 
      break; 
     } 
     lastNum = num; 
    } 
    Console.WriteLine(isSorted ? "Sorted" : "Not sorted"); 
    Console.ReadLine(); 
} 

O sıralanmış geri gelecektir.