Quick Sort

Choosing first element as pivot

import java.util.Arrays;
public class QuickSort{
    
    private int partition(int[] a, int lower, int upper){
        int i, j;               
        i = lower;
        j = upper+1;
        int pivot = a[lower];           
        while (i<j) {
            while (a[++i] < pivot){
                if (i == upper) break;
            }
            while (a[--j] >= pivot) {
                if (j == lower) break;
            }
            if(i <j) {
                swap(a,i,j);
            }
        }           
        swap(a, lower,j);
        return j;
    }
    private void quicksort(int[] a, int lower, int upper) {
        
        if (upper <= lower) {
            return;         
        } 
        else {
            int i= partition(a,lower,upper);            
            quicksort(a,lower, i-1);
            quicksort(a,i+1, upper);
        }
    }
    private void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i]=arr[j];
        arr[j] = temp;
        
    }
    public int[] sort(int[] a){
        quicksort(a,0, a.length-1);
        return a;
    }
    public static void main(String[] args){
        QuickSort qs = new QuickSort();
        int[] input = {2,2,435,33,3,3,3,56,6,6,7,8,3,6,9,8,6};
        
        System.out.println("Before: "+Arrays.toString(input));
        int[] output = qs.sort(input);      
        System.out.println("After: "+Arrays.toString(output));      
    }

}
/*
Output 
Before: [2, 2, 435, 33, 3, 3, 3, 56, 6, 6, 7, 8, 3, 6, 9, 8, 6]
After: [2, 2, 3, 3, 3, 3, 6, 6, 6, 6, 7, 8, 8, 9, 33, 56, 435]
*/

Choosing last element as pivot

import java.util.Arrays;
public class QuickSort{
    
    private int partition(int[] a, int lower, int upper){
        int i, j;               
        i = lower-1;
        j = upper;
        int pivot = a[upper];           
        while (i<j) {
            while (a[++i] <= pivot){
                if (i == upper) break;
            }
            while (a[--j] > pivot) {
                if (j == lower) break;
            }
            if(i <j) {
                swap(a,i,j);
            }
        }           
        swap(a, upper,i);
        return i;
    }
    private void quicksort(int[] a, int lower, int upper) {
        
        if (upper <= lower) {
            return;         
        } 
        else {
            int i= partition(a,lower,upper);            
            quicksort(a,lower, i-1);
            quicksort(a,i+1, upper);
        }
    }
    private void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i]=arr[j];
        arr[j] = temp;
        
    }
    public int[] sort(int[] a){
        quicksort(a,0, a.length-1);
        return a;
    }
    public static void main(String[] args){
        QuickSort qs = new QuickSort();
        int[] input = {2,2,435,33,3,3,3,56,6,6,7,8,3,6,9,8,6};
        
        System.out.println("Before: "+Arrays.toString(input));
        int[] output = qs.sort(input);      
        System.out.println("After: "+Arrays.toString(output));          
    }
}
/*
Output 
Before: [2, 2, 435, 33, 3, 3, 3, 56, 6, 6, 7, 8, 3, 6, 9, 8, 6]
After: [2, 2, 3, 3, 3, 3, 6, 6, 6, 6, 7, 8, 8, 9, 33, 56, 435]
*/

Choosing median of three as pivot

import java.util.Arrays;
public class QuickSort{
    
    private int partition(int[] keyArray, int lower, int upper){
        int lowPtr, highPtr;        // these are the moving pointers into the array
            //locate position of pivot
            int pivotPos = medianOfThree(keyArray,lower,upper);
            
            //swap pivot to last position
            swap(keyArray,pivotPos,upper);
            
            //pivot is now in rightmost slot
            int pivot = keyArray[upper];
            
            //define the pointers
            lowPtr = lower-1;
            highPtr = upper;
            
            //use the pointers to create the partitions in the array            
            while (lowPtr<highPtr) {
                while (keyArray[++lowPtr] < pivot) {
                    if (lowPtr == upper) break;
                }
                while (keyArray[--highPtr] > pivot){
                    if (highPtr == lower) break;
                }
                //if(lowPtr == highPtr) return lowPtr;
                if(lowPtr <highPtr) {
                    swap(keyArray, lowPtr,highPtr);
                }
            }               
            //restore pivot to correct spot
            swap(keyArray, upper,lowPtr);
            return lowPtr;
    }

    private void qsort(int[] keyArray, int lower, int upper) {
        
        if (upper <= lower) {
            return;         // base case
        } 
        else {
             int lowPtr= partition(keyArray,lower,upper);
            
            
            qsort(keyArray,lower, lowPtr-1);
            qsort(keyArray,lowPtr+1, upper);
        }
    }
    private void swap(int[] arr, int i, int j){
        if(arr == null || i == j || i >= arr.length || j >=arr.length) return;
        int temp = arr[i];
        arr[i]=arr[j];
        arr[j] = temp;
        
    }
    /** returns the position of the median of first, last, and middle array elements */
    private int medianOfThree(int[] arr, int left, int right){
        if(right-left < 2) return left;
        int center = (left+right)/2;
        //arrange the three
        if(arr[center] < arr[left]) swap(arr,center,left);
        if(arr[right] < arr[left]) swap(arr,right,left);
        if(arr[right] < arr[center]) swap(arr,right,center);
        return center;
        
    }
    //public sorting method
    public int[] sort(int[] arr){
        qsort(arr,0, arr.length-1);
        return arr;
    }
    
    
    public static void main(String[] args){
        QuickSort qs = new QuickSort();
        int[] input = {2,2,435,33,3,3,3,56,6,6,7,8,3,6,9,8,6};
        
        System.out.println("Before: "+Arrays.toString(input));
        int[] output = qs.sort(input);      
        System.out.println("After: "+Arrays.toString(output));      
    }

}
/*
Output 
Before: [2, 2, 435, 33, 3, 3, 3, 56, 6, 6, 7, 8, 3, 6, 9, 8, 6]
After: [2, 2, 3, 3, 3, 3, 6, 6, 6, 6, 7, 8, 8, 9, 33, 56, 435]
*/