QuickSort Stack Overflow

Question

У моего общего алгоритма QuickSort есть две проблемы, которые я не могу определить причину.

1. Список иногда не правильно отсортирован
2. При работе со списками больше, чем 20000 пунктов, я часто получаю переполнение стека, если значения повторяют много (который я полагаю, не должна быть реальной проблемой)

Список, который не сортируется правильно, является довольно редким случаем, поэтому список должен быть достаточно большим. В пасте внизу показаны первые 13 элементов 172-элементного списка установленного программного обеспечения с первым столбцом, отображающим результат после первого сортировки, и второй столбец для второго сортировки.

Adobe AIR       7-Zip 4.65 (x64 edition) 
7-Zip 4.65 (x64 edition)   Adobe AIR 
Adobe Community Help    Adobe Community Help 
Adobe Encore CS4 Codecs   Adobe Encore CS4 Codecs 
Adobe Media Encoder CS4 Exporter Adobe Media Encoder CS4 Exporter 
Adobe Media Encoder CS4 Importer Adobe Media Encoder CS4 Importer 
Adobe Media Player    Adobe Media Player 
Adobe Reader X (10.1.0)   Adobe Reader X (10.1.0) 
Adobe Setup      Adobe Setup 
Adobe Setup      Adobe Setup 
Apple Application Support   Adobe Setup 
Adobe Setup      Apple Application Support 
Apple Mobile Device Support  Apple Mobile Device Support 
...        ... 

Как вы можете видеть, первый раз он был отсортирован, есть некоторое неправильное поведение, которое фиксируется делают другой вид.

Вторая проблема с переполнением стека происходит, если я сортирую свой список журналов событий Windows с большим олом. Кажется счастливым, если я сортирую 52 000 дат, охватывающих 4 недели; но если я сортирую 52 000 идентификационных номеров, которые имеют много повторов, мой размер стека становится 998 элементов задолго до того, как он выйдет из строя. Это также происходит, если я сортирую 30 000 длинный список столбцом, который в основном «gupdate».

Теперь, насколько я вижу, счетчик стека должен быть log2 (n), потому что сумма, добавленная в стек, равна количеству разрезанной половины.

Я сделал свой случайный случайный, чтобы помочь этому эффекту, но это не сильно изменило ситуацию.

Log2 (60000) = 16. Этого недостаточно для переполнения стека!

Это код в беспокойстве:

private static void QuickSortFunction<T>(T[] array, int start, int end, Comparer<T> comparer) 
{ 
    if (end - start >= 1) 
    { 
     int leftPtr, rightPtr, pivot; 
     Random random = new Random(); 
     pivot = random.Next(start, end); 
     Swap(array, pivot, start); 
     pivot = start; 

     leftPtr = start + 1; 
     rightPtr = end; 

     while (leftPtr < rightPtr) 
     { 
      while ((comparer.Compare(array[leftPtr], array[pivot])) <= 0 && (leftPtr < rightPtr)) 
      { 
       leftPtr++; 
      } 

      while ((comparer.Compare(array[rightPtr], array[pivot])) >= 0 && (leftPtr <= rightPtr)) 
      { 
       rightPtr--; 
      } 

      if (leftPtr < rightPtr) 
      { 
       Swap(array, leftPtr, rightPtr); 
      } 
     } 
     Swap(array, pivot, rightPtr); 
     pivot = rightPtr; 

     QuickSortFunction(array, start, pivot - 1, comparer); 
     QuickSortFunction(array, pivot + 1, end, comparer); 
    } 
} 

private static void Swap<T>(T[] array, int pointer1, int pointer2) 
{ 
    T temp = array[pointer1]; 
    array[pointer1] = array[pointer2]; 
    array[pointer2] = temp; 
} 

Для тех, кто заинтересован, это исправления для глюка испорченных. В принципе, он не смог распознать массив из двух элементов, когда он вышел из строя. Например, {E, B}, который он не изменит, потому что он не будет смотреть на свой собственный стержень.

if (end - start >= 1) 
    { 
     int leftPtr, rightPtr, pivot; 
     Random random = new Random(); 
     pivot = random.Next(start, end); 
     Swap(array, pivot, start); 
     pivot = start; 

     leftPtr = start; 
     rightPtr = end; 

     while (leftPtr < rightPtr) 
     { 
      while ((comparer.Compare(array[leftPtr], array[pivot])) < 0 && (leftPtr < rightPtr)) 
      { 
       leftPtr++; 
      } 

      while ((comparer.Compare(array[rightPtr], array[pivot])) >= 0 && (leftPtr < rightPtr)) 
      { 
       rightPtr--; 
      } 

      if (leftPtr < rightPtr) 
      { 
       Swap(array, leftPtr, rightPtr); 
      } 
     } 
     Swap(array, pivot, rightPtr); 
     pivot = rightPtr; 

     QuickSortFunction(array, start, pivot - 1, comparer); 
     QuickSortFunction(array, pivot + 1, end, comparer); 
    } 

Будет обновляться после того, как я напишу решение для переполнения стека.

Answer 1

Теперь, насколько я вижу, счетчик стека должен быть log2 (n), потому что сумма, добавленная в стек, равна количеству разрезанной половины.

Это только справедливо, если вы разделяете вход на половинки одинакового размера . Если, например, вы сортировка списка, где все элементы равны, вы получаете очень неравномерное разделение, где у Вас нет никаких элементов, с одной стороны, и все, кроме поворота на другом. В этом случае вы получаете O (n) размер стека, так как каждый уровень уменьшает размер ввода на 1.

Один из способов избежать этого - вместо этого использовать трехстороннее разделение, в котором все элементы равны стержень посередине.

_{Если раскол всегда лучше, чем некоторое постоянное соотношение, вы в порядке.}

Answer 2

Давайте сначала рассмотрим проблему с нестандартным порядком. большой цикл продолжается до leftPtr >= rightPtr. Поскольку ваши тесты второго цикла для leftPtr <= rightPtr, возможно, что в конце leftPtr > rightPtr, в этом случае вы меняете (после большой петли) ось и элемент, который считается «ОК» (rightPtr указывает на то, что было передано по leftPtr)

Не уверен, что о проблеме переполнения стека, но предложение Хаммара кажется разумным, особенно, что вы сказали, что проблема возникает на больших списках многих одинаковых элементов

Answer 3

смотреть бесконечный цикл вы создали ... функция должен прекратиться, чтобы его внутренняя ценность была актуализирована в использовании.