package algorithms;


/**
 * An array based implementation of Quick-sort.
 * 
 * @author joeytawadrous
 */
public class QuickSortArray  
{
	private static int[] numbers;
	private static int number;

	public static void main(String[] args) 
	{
		int[] values = {3, 1, 4, 2};
		
		sort(values);
		
		for(int value: values)
		{
			System.out.println(value);
		}
	}
	
	
	public static void sort(int[] values) 
	{
		// check for empty or null array
	    if (values ==null || values.length == 0) { return; }
	    
	    numbers = values;
	    number = values.length;
	    quicksort(0, number - 1);
	}

	private static void quicksort(int low, int high) 
	{
		int i = low, j = high;
	    // Get the pivot element from the middle of the list
	    int pivot = numbers[low + (high-low)/2];

	    // Divide into two lists
	    while (i <= j) 
	    {
	    	// If the current value from the left list is smaller than the pivot
	    	// element then get the next element from the left list
	    	while (numbers[i] < pivot) 
	    	{
	    		i++;
	    	}
	    	
	    	// If the current value from the right list is larger then the pivot
	    	// element then get the next element from the right list
	    	while (numbers[j] > pivot) 
	    	{
	    		j--;
	    	}

	    	// If we have found a values in the left list which is larger then
	    	// the pivot element and if we have found a value in the right list
	    	// which is smaller then the pivot element then we exchange the
	    	// values.
	    	// As we are done we can increase i and j
	    	if (i <= j) 
	    	{
	    		exchange(i, j);
	    		i++;
	    		j--;
	    	}
	    }
	    
	    // Recursion
	    if (low < j)
	    	quicksort(low, j);
	    if (i < high)
	    	quicksort(i, high);
	  }

	  private static void exchange(int i, int j) 
	  {
		  int temp = numbers[i];
		  numbers[i] = numbers[j];
		  numbers[j] = temp;
	  }
}