Быстрая сортировка с ошибками дубликатов

Question

У меня проблемы с алгоритмом быстрой сортировки. Отлично работает с массивом без повторяющихся значений. Но как только у меня есть массив с 2+ дубликатами, он застревает в бесконечном цикле. Например, если мой массив:

int[] array = {44, 53, 36, 186, 22, 162, 22};



public void quick_sort(int[] data, int low, int high)
   {  // 1 or 0 items are sorted by default
      if(high - low < 1)
         return;

      int left = low;
      int right = high;
      int pivot = data[low + (high - low) / 2];  

      while(left < right)
      {  // Increment left pointer until left >= pivot
         while(data[left] < pivot)
            left++;

         // Increment right pointer until right <= pivot
         while(data[right] > pivot)
            right--;

         // If left <= right; swap values
         if(left <= right)
         {  int temp = data[right];
            data[right] = data[left];
            data[left] = temp;
         }
      }

      // quick_sort 'lesser values'
      quick_sort(data, low, left - 1);
      // quick_sort 'greater values'
      quick_sort(data, left + 1, high);
   }

Заранее спасибо за любую помощь.

Решено:

   public void quick_sort(int[] data, int low, int high)
   {  // 1 or 0 items are sorted by default
      if(high - low < 1)
         return;

      int left = low;
      int right = high;
      int pivot = data[low + (high - low) / 2];  

      while(left <= right)
      {  // Increment left pointer until left >= pivot
         while(data[left] < pivot)
            left++;

         // Increment right pointer until right <= pivot
         while(data[right] > pivot)
            right--;

         // If left < right; swap values
         if(left <= right)
         {  int temp = data[left];
            data[left] = data[right];
            data[right] = temp;
            left++;
            right--;
         }

      }
      // quick_sort 'lesser values'
      quick_sort(data, low, right);

      // quick_sort 'greater values'
      quick_sort(data, left, high);
   }

Answer 1

Ну, с дубликатами, вы можете получить (left < right), но data[left] == pivot == data[right].

И в этом случае ваш цикл не увеличивается влево или вправо, он просто меняет элементы снова и снова... (также интересно, что вы "меняете" даже когда left==right)

Answer 2

Рассмотрим, что происходит, когда data[left] == data[right] == pivot.