Проблема с алгоритмом быстрой сортировки

Question

Я работаю над алгоритмом быстрой сортировки в C #, но сталкиваюсь со странной проблемой, которая заключается в том, что при 10-кратном выполнении алгоритма по случайным числам я получил 2 или 3 неправильных ответа на сортировку.

Я имею в виду: этот код может сортировать около 7 из 10 примеров; Зачем? Я не мог понять, в чем проблема, вы можете мне помочь?

  public void quicksort(int[] data, int first, int n)
   { 
       int pivotIndex, n1, n2;
       if (n > 1)
       {
           pivotIndex= partition(data, first, n);
           n1 = pivotIndex-first;
           n2 = n -n1 -1;
           quicksort(data, first, n1);
           quicksort(data, pivotIndex+ 1, n2);
       }
   }

   private int partition(int[] data, int first, int n)
   {
       int t;
       int pivot= data[first], tooBigIndex=first+1, tooSmallIndex=first+n-1;
       while (tooBigIndex<= tooSmallIndex)
       {
        while( (tooBigIndex < n) && (data[tooBigIndex] <= pivot) )
                tooBigIndex++;
       while (data[tooSmallIndex] > pivot) 
            tooSmallIndex--;
           if (tooBigIndex< tooSmallIndex) 
           {
            t = data[tooBigIndex];
            data[tooBigIndex] = data[tooSmallIndex];
            data[tooSmallIndex] = t;
            tooSmallIndex--;
            tooBigIndex++;
           }
       }
       t= data[0];
       data[0]= data[tooSmallIndex] ;
       data[tooSmallIndex]=t;
       return tooSmallIndex;

   }
}

Answer 1

Я удивлен тем, что вы отправили код когда-либо работает - или даже завершается . Тест:

(tooBigIndex < n) &&

должно быть явно

(tooBigIndex < first + n) &&

и индекс в строках:

   t= data[0];
   data[0]= data[tooSmallIndex];
   data[tooSmallIndex]=t;

должно быть first, , а не 0 (делая первую строку бесполезной, так как вы можете опустить ее и использовать pivot вместо t в третьей строке - но это избыточность, две другие ужасные ошибки; -).

Я думаю это все ошибки, но я тестировал только на случайных массивах; -).

Answer 2

Если это домашний вопрос, вы должны пометить его как таковой, чтобы мы могли лучше ориентироваться на помощь (больше толчков в правильном направлении, чем на прямые решения).

Если это не домашняя работа, вам следует подуматьиспользуя интерфейс IComparable с Array.sort ().Для целых чисел, которые предоставляют интерфейс IComparable, вы должны иметь возможность просто использовать что-то вроде:

int[] valArray = new int[6] { 1, 5, 2, 6, 9, 7 };
Array.Sort (valArray);                            // <-- This is all you need.
String s = "";
foreach (int val in valArray)
    s += "," + val;
MessageBox.Show (s.Substring(1));

, что приводит к:

1,2,5,6,7,9

, и я почти уверен, что он используетБыстрая сортировка под одеялом.Повторно изобретать колесо - плохая идея, отлично подходит для образовательных целей, но если цель (как вы указываете) состоит в том, чтобы просто иметь возможность сортировать массив, использовать предоставляемые языком функции и сэкономить свои усилия.