Randomized quicksort C#

Question

J'essaie d'analyser l'algorithme de tri rapide avec un pivot aléatoire sur C#. C'est le code que j'essaie de tester:

//begeeben.wordpress.com/2012/08/22/randomized-quick-sort-in-c/ using System; using System.Collections.Generic; using System.Text; using System.Diagnostics; class Quicksort { 
    public static void RandomizedQuickSort(int[] input, int left, int right) 
    { 
     if (left < right) 
     { 
      int q = RandomizedPartition(input, left, right); 
      RandomizedQuickSort(input, left, q - 1); 
      RandomizedQuickSort(input, q + 1, right); 
     } 
    } 
    private static int RandomizedPartition(int[] input, int left, int right) 
    { 
     Random random = new Random(); 
     int i = (left + random.Next()) % (right-left+1); 

     int pivot = input[i]; 
     input[i] = input[right]; 
     input[right] = pivot; 

     return Partition(input, left, right); 
    } 
    private static int Partition(int[] input, int left, int right) 
    { 
     int pivot = input[right]; 
     int temp; 

     int i = left-1; 
     for (int j = left; j < right; j++) 
     { 
      if (input[j] <= pivot) 
      { 
       i++; 
       temp = input[j]; 
       input[j] = input[i]; 
       input[i] = temp; 
      } 
     } 

     input[right] = input[i+1]; 
     input[i+1] = pivot; 

     return i; 
    } 
    static void Main(string[] args) 
    { 
     Random random = new Random(); 
     Stopwatch stopWatch; 
     int []array; 
     int size = 10; 
     for (int j = 1; j < 7; ++j) 
     { 
      stopWatch = Stopwatch.StartNew(); 
      array = new int[size]; 
      for (int i = 0; i < 10; ++i) array[i] = random.Next(0, 300); 
      stopWatch.Start(); 
      RandomizedQuickSort(array, 0, size-1); 
      stopWatch.Stop(); 
      Console.WriteLine("Number of millisec to sort " + size + " elements: " + stopWatch.ElapsedMilliseconds); 
      size = size * 10; 
     } 
    } 
} 

Tout va bien jusqu'à ce que j'essaie de trier un tableau de 10 000 000 éléments. À ce stade, je reçois une exception de dépassement de pile. J'ai essayé d'utiliser des entiers plus petits mais cela m'amène aussi à empiler des problèmes de débordement. Il semble que lorsque le code se termine, gauche et droite sont tous les deux égaux à zéro. Cependant, l'exception de tri Merge n'aurait-elle pas attrapé ceci?

~ Mise à jour: Le problème est que la taille du tableau est si grande que j'ai épuisé tout le tas! Pour résoudre ce problème, j'ai dû passer d'un algorithme récursif à un algorithme itératif.

Answer 1

C# a une taille de pile maximale de 1 Mo et vous utilisez tout cela. C'est juste une limitation intégrée des implémentations récursives.

Vous avez 3 solutions:
1) Construire une version itérative de l'algorithme (plus performant)
2) Augmentez votre taille de la pile, quelque chose comme:

Thread T = new Thread(threadEntryPoint, stackSizeInBytes); 
T.Start(); 

3) Limiter votre analyse à la liste tailles que cet algorithme peut gérer.