Почему быстрая сортировка работает с 10 или менее целыми числами, но не более?

Question

Я пытаюсь отсортировать целочисленный массив. Мой алгоритм быстрой сортировки работает нормально с 10 или менее числами, но как только я добавляю больше, он не сортирует их правильно?

Он работает так же, с Shuffle или без (слева, справа), поэтому яне думаю, что проблема есть. Я собираюсь использовать код для сортировки большого количества чисел, и я думаю, что быстрая сортировка - самый эффективный выбор для моих данных.

   private static int[] intArray;

   static void Main(string[] args)
   {
       data = new int[] { 1, 9, 10, 2, 4, 5, 6, 3, 257, -6 };
       int N = data.Length;
       intArray = new int[N];

       long before = Environment.TickCount;
       long after = Environment.TickCount;

       QuickSort(0, N - 1);

       for (int i = 0; i < data.Length; i++)
       {
           Console.WriteLine(data[i]);
       }
   }

   private static int Pivot(int left, int right)
   {
       int pivot = data[left];
       while (true)
       {
           while (data[left] < pivot)
           {
               left++;
           }

           while (data[right] > pivot)
           {
               right--;
           }

           if (left < right)
           {
               if (data[left] == data[right])
               {
                   return right;
               }

               int temp = data[left];
               data[left] = data[right];
               data[right] = temp;
           }
           else
           {
               return right;
           }
       }
   }

   private static void QuickSort(int left, int right)
   {
       Shuffle(left, right);
       if (left < right)
       {
           int pivot = Pivot(left, right);

           if (pivot > 1)
           {
               QuickSort(left, pivot - 1);
           }
           else if (pivot + 1 < right)
           {
               QuickSort(pivot + 1, right);
           }
       }
   }

Answer 1

Исправления отмечены в комментариях. Перемешивание делает его относительно медленным:

    private static int[] data;          // fix

    private static int Pivot(int left, int right)
    {
        int pivot = data[left];
        while (left <= right)
        {
            while (data[left] < pivot)
            {
                left++;
            }

            while (data[right] > pivot)
            {
                right--;
            }

            if (left <= right)          // fix
            {
                                        // fix deleted 4 lines
                int temp = data[left];
                data[left] = data[right];
                data[right] = temp;
                left++;                 // fix
                right--;                // fix
            }
        }
        return right;                   // fix
    }

    private static void QuickSort(int left, int right)
    {
        Shuffle(left, right);
        if (left < right)
        {
            int pivot = Pivot(left, right);
            QuickSort(left,    pivot);  // fix
            QuickSort(pivot+1, right);  // fix
        }
    }

    public static void Shuffle(int lo, int hi)
    {
        Random rand = new Random();
        for (int i = lo; i <= hi; i++)
        {
            int r = i + rand.Next(hi + 1 - i);
            int t = data[i]; data[i] = data[r]; data[r] = t;
        }
    }

    static void Main(string[] args)
    {
        data = new int[] { 1, 9, 10, 2, 4, 5, 6, 3, 257, -6 }; // fix

        long before = Environment.TickCount;

        QuickSort(0, data.Length - 1);

        long after = Environment.TickCount;

        for (int i = 0; i < data.Length; i++)
        {
            Console.WriteLine(data[i]);
        }
        Console.WriteLine(after - before);
    }

---

Альтернативный код, основанный на стандартной схеме разбиения Hoare, с данными, передаваемыми в качестве параметра.

    static public void Quicksort(int [] data, int lo, int hi)
    {
        if (lo >= hi)
            return;
        int p = data[(lo + hi) / 2];
        int i = lo, j = hi;
        i--;                        // partition
        j++;
        while (true)
        {
            while (data[++i] < p) ;
            while (data[--j] > p) ;
            if (i >= j)
                break;
            int t = data[i];
            data[i] = data[j];
            data[j] = t;
        }
        Quicksort(data, lo, j);        // recurse
        Quicksort(data, j + 1, hi);
    }

    static void Main(string[] args)
    {
        const int SIZE = 10*1024*1024;
        int [] data = new int[SIZE];
        Random r = new Random(1);
        Stopwatch sw = new Stopwatch();
        for (int i = 0; i < data.Length; i++)
            data[i] = r.Next(data.Length);
        sw.Start();
        Quicksort(data, 0, data.Length - 1);
        sw.Stop();
        for (int i = 1; i < data.Length; i++)
        {
            if(data[i] < data[i-1])
                Console.WriteLine("failed");
        }
        Console.WriteLine("milliseconds: {0:D}\n",sw.ElapsedMilliseconds);
    }