Рекомбинируя QuickSort в C#

Question

Я начал изучать алгоритмы, и я пытаюсь реализовать Quicksort в C#. Это мой код:

class QuickSortDemo 
{ 
    public void Swap(ref int InputA, ref int InputB) 
    { 
     InputA = InputA + InputB; 
     InputB = InputA - InputB; 
     InputA = InputA - InputB; 
    } 

    public int Partition(int[] InputArray, int Low, int High) 
    { 
     int Pivot = InputArray[Low]; 
     int LoopVariable1 = Low - 1; 
     int LoopVariable2 = High + 1; 
     while (true) 
     { 

      while (InputArray[--LoopVariable2] > Pivot) ; 

      while (InputArray[++LoopVariable1] < Pivot) ; 


      if (LoopVariable1 < LoopVariable2) 
      { 
       Swap(ref InputArray[LoopVariable1], ref InputArray[LoopVariable2]); 
       for (int LoopVariable = Low; LoopVariable <= High; LoopVariable++) 
       { 
        Console.Write(InputArray[LoopVariable] + " "); 
       } 
       Console.WriteLine(); 

      } 
      else 
      { 
       for (int LoopVariable = Low; LoopVariable <= High; LoopVariable++) 
       { 
        Console.Write(InputArray[LoopVariable] + " "); 
       } 
       Console.WriteLine(); 
       return LoopVariable2; 
      } 
     } 
    } 

    public void QuickSort(int[] InputArray,int Low, int High) 
    { 
     if (Low < High) 
     { 
      int Mid = Partition(InputArray, Low, High); 
      QuickSort(InputArray, Low, Mid); 
      QuickSort(InputArray, Mid + 1, High); 
     } 
    } 
    public static void Main() 
    { 
     int[] InputArray = { 10, 5, 6, 8, 23, 19, 12, 17 }; 
     QuickSortDemo Demo = new QuickSortDemo(); 
     for (int LoopVariable = 0; LoopVariable < InputArray.Length; LoopVariable++) 
     { 
      Console.Write(InputArray[LoopVariable]+" "); 
     } 
     Console.WriteLine(); 

     Demo.QuickSort(InputArray, 0, InputArray.Length - 1); 
     for (int LoopVariable = 0; LoopVariable < InputArray.Length; LoopVariable++) 
     { 
      Console.Write(InputArray[LoopVariable] + " "); 
     } 
     Console.WriteLine(); 
    } 
} 

По некоторым причинам я не могу получить эту работу, когда я беру крайний правый элемент в массиве в качестве опоры. Я не знаю, что я делаю неправильно. Было бы очень полезно, если бы кто-нибудь мог объяснить мне, почему это не работает, когда я беру на себя самый правый элемент. Из того, что я узнал, это должно работать на любой вход и любой элемент поворота. Поправьте меня, если я ошибаюсь. Спасибо.

Answer 1

Я все еще не совсем уверен, что понимаю вопрос. Но я был в состоянии воспроизвести проблему (зацикливание) при изменении строки кода в методе Partition() от int pivot = inputArray[low]; к int pivot = inputArray[high];, и делает это, кажется, в соответствии с описательной:

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

Если я правильно понял вопрос, то основная проблема заключается в том, что при изменении где вы получаете стержень, вы должны принять это во внимание при возвращении новой медианы. В настоящее время, вы возвращаетесь loopVariable2, который является правильным, выбирая стержень из нижнего конца массива. Но если вы переключитесь на сбор стержня с верхнего конца массива, вам нужно вернуть loopVariable2 - 1.

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

Вот правильная версия метода Partition(), где стержень выбирается с помощью high вместо low:

public int Partition(int[] inputArray, int low, int high) 
    { 
     int pivot = inputArray[high]; 
     int loopVariable1 = low; 
     int loopVariable2 = high; 
     while (true) 
     { 

      while (inputArray[loopVariable2] > pivot) loopVariable2--; 

      while (inputArray[loopVariable1] < pivot) loopVariable1++; 


      if (loopVariable1 < loopVariable2) 
      { 
       Swap(ref inputArray[loopVariable1], ref inputArray[loopVariable2]); 
       for (int loopVariable = low; loopVariable <= high; loopVariable++) 
       { 
        Console.Write(inputArray[loopVariable] + " "); 
       } 
       Console.WriteLine(); 

      } 
      else 
      { 
       for (int loopVariable = low; loopVariable <= high; loopVariable++) 
       { 
        Console.Write(inputArray[loopVariable] + " "); 
       } 
       Console.WriteLine(); 
       return loopVariable2 - 1; 
      } 
     } 
    } 

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

Кстати, и для чего это стоит, я бы не реализовал Swap(), как и у вас. Это интересный трюк, чтобы сделать замену без temp-переменных, но практической пользы от этого не существует, в то время как он не требует значительных затрат на обслуживание и понимание кода. Кроме того, он будет работать только с целочисленными числовыми типами; что, если вы хотите расширить свою сортировку для обработки других типов? Например. которые реализуют IComparable или где вы позволяете вызывающему абоненту реализовать реализацию IComparer?

ИМХО лучше Swap() метод выглядит следующим образом:

public void Swap<T>(ref T inputA, ref T inputB) 
    { 
     T temp = inputA; 

     inputA = inputB; 
     inputB = temp; 
    } 

Answer 2

быстрой сортировки:

static public int Partition(int [] numbers, int left, int right) 
    { 
     int pivot = numbers[left]; 
      while (true) 
      { 
      while (numbers[left] < pivot) 
       left++; 

      while (numbers[right] > pivot) 
       right--; 

      if (left < right) 
       { 
       int temp = numbers[right]; 
       numbers[right] = numbers[left]; 
       numbers[left] = temp; 
       } 
       else 
       { 
         return right; 
       } 
      } 
    } 

    static public void QuickSort_Recursive(int [] arr, int left, int right) 
    { 
     // For Recusrion 
     if(left < right) 
     { 
      int pivot = Partition(arr, left, right); 

      if(pivot > 1) 
       QuickSort_Recursive(arr, left, pivot - 1); 

      if(pivot + 1 < right) 
       QuickSort_Recursive(arr, pivot + 1, right); 
     } 
    }