Quick Sort not sorting iterative solution

Question

I currently have the below code for my quick sort. As you can see it is not producing the correct output. Any help will be greatly appreciated. I need the pivot to be the first item in the array. As you can also see i am measuring the time it takes to run, but please ignore that for the time being.

edit: to be specific it works correctly when i have a list in descending order and ascending order(already sorted), but when i try a random list it does not work.

Output:

QuickSort:
Quick Sort Took 181023 nanoseconds
Quick Sort Took 0 milliseconds
Sorted Quick Sort: 25, 12, 17, 13, 20, 7, 5, 16, 11, 26, 24, 18, 9, 4, 21, 1, 23, 27, 15, 19, 28, 14, 8, 22, 6, 3, 2, 10, 29, 40, 37, 32, 44, 38, 35, 41, 39, 31, 42, 30, 43, 36, 34, 33, 45, 46, 47, 48, 49, 50, 

Code:

class QuickSort {

  public static int Partition(int[] numbers, int left, int right){


    //selects the first item at position [0] as the pivot
    //left is given 0 when the method is called 
    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;
          }
    }
 }
  //method to check for special cases
  public static void QuickSort_Check(int[] numbers, int left, int right)
  {
     //special case of 2 items to be sorted
     if(right == 1){
        if(numbers[0] >= numbers[1]){
           System.out.print("This is a special case of 2 inputs: ");
           System.out.print(numbers[1] + ", " + numbers[0]);
           System.exit(0);
        }
        else {
           System.out.print("This is a special case of 2 inputs: ");
           System.out.print(numbers[0] + ", " + numbers[1]);
           System.exit(0);
        }
        System.exit(0);
     }   

     //special case of 1 item to be sorted
     else if (right == 0){
        System.out.print("This is a special case of 1 input: ");
        System.out.print(numbers[0]);
        System.exit(0);
     }
     else {
        QuickSort_Iterative(numbers, left, right);
     }

  }

 public static class QuickPosInfo
 {
    public int left;
    public int right;
 };

  public static QuickPosInfo spot = new QuickPosInfo();

  public static void QuickSort_Iterative(int[] numbers, int left, int right)
 {

    if(left >= right)
        return; // Invalid index range


        LinkedList<QuickPosInfo> list = new LinkedList< QuickPosInfo>();

    spot.left = left;
    spot.right = right;
        list.add(spot);

    while(true)
    {
        if(list.size() == 0)
            break;

              left = list.get(0).left;
              right = list.get(0).right;
              list.remove(0);

        int pivot = Partition(numbers, left, right);   

        if(pivot > 1)
        {
            spot.left = left;
            spot.right = pivot - 1;
            list.add(spot);
        }

        if(pivot + 1 < right)
        {
            spot.left = pivot + 1;
            spot.right = right;
            list.add(spot);
        }
    }
 }

 }

Answer 1

I don't know that will help you out or not you can also try the below code for same.

public class Demo {

 private int array[];
    private int length;

    public void sort(int[] inputArr) {

        if (inputArr == null || inputArr.length == 0) {
            return;
        }
        this.array = inputArr;
        length = inputArr.length;
        quickSort(0, length - 1);
    }

    private void quickSort(int lowerIndex, int higherIndex) {

        int i = lowerIndex;
        int j = higherIndex;

        int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2];

        while (i <= j) {

            while (array[i] < pivot) {
                i++;
            }
            while (array[j] > pivot) {
                j--;
            }
            if (i <= j) {
                exchangeNumbers(i, j);
                i++;
                j--;
            }
        }

        if (lowerIndex < j)
            quickSort(lowerIndex, j);
        if (i < higherIndex)
            quickSort(i, higherIndex);
    }

    private void exchangeNumbers(int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public static void main(String a[]){

        Demo sorter = new Demo();
        int[] input = {8,693,29,3,2,8,29,82,4,26,2,62,82,6,52,9,42,6,52,66,2,8};
        sorter.sort(input);
        for(int i:input){
            System.out.print(i);
            System.out.print(" ");
        }
    }
}

Answer 2

This partition method correctly sorted half the array, then did not sort the other half so I believe the problem is in your QuickSort_Iterative(); when the pivot equals 21 it just infinitely swaps 20 and 21.

 private static int partition(int[] arr,int left,int right) {
        int pivot = arr[right];
        int small = left-1;
        for(int k = left;k < right;k++)
        {
            if(arr[right] <= pivot)
            {
                small++;
                swap(arr,right,small);            
            }


        }
        swap(arr,right,small+1);
        System.out.println("Pivot= "+arr[small+1]);//prints out every sort
        System.out.println(Arrays.toString(arr));
        return small+1;


    }

    private static void swap(int[] arr, int k, int small) {//easy swap method
        int temp;
        temp = arr[k];
        arr[k] = arr[small];
        arr[small] = temp;

    }    

UPDATE

Here is the requested method. I believe that the problem with your original one is that you are not modifying that values of left and right properly as the array is sorted.

void QuickSort(int arr[], int left, int right)
{
    // create auxiliary stack
    int stack[] = new int[right-l+1];

    // initialize top of stack
    int top = -1;

    // push initial values in the stack
    stack[++top] = left;
    stack[++top] = right;

    // keep popping elements until stack is not empty
    while (top >= 0)
    {
        // pop right and l
        right = stack[top--];
        left = stack[top--];

        // set pivot element at it's proper position
        int p = partition(arr, left, right);

        // If there are elements on left side of pivot,
        // then push left side to stack
        if ( p-1 > left )
        {
            stack[ ++top ] = l;
            stack[ ++top ] = p - 1;
        }

        // If there are elements on right side of pivot,
        // then push right side to stack
        if ( p+1 < right )
        {
            stack[ ++top ] = p + 1;
            stack[ ++top ] = right;
        }
   }
}