Quicksort w/ duplicates error

I am having some trouble with my Quicksort algorithm. It works great on an array without duplicate values. But once I have an array with 2+ duplicates, it gets stuck in a endless loop. For instance, if my array is:

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);
   }

Thanks in advance for any help.

Solved:

   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 <= ri开发者_JS百科ght)
         {  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);
   }

---

Well, with duplicates, you can get (left < right) but data[left] == pivot == data[right].

And in this case, your loop doesn't increment left or decrement right, it just swaps the elements, again and again... (also interesting that you "swap" even when left==right)

---

Consider what happens when data[left] == data[right] == pivot.