Run for a console output clearly outlining the steps involved in a quick sort.

QuickSort.java

import java.util.Arrays;

public class QuickSort  // sorts by sending incrementally smaller arrays to be partitioned

{
	
	private static int depth = 0;
	
	private static String side;
	
	private static int[] theArray;
	
	private static int arraySize;
	
	QuickSort(int newArraySize)  // Class Constructor
	
	{
		arraySize = newArraySize;
		theArray = new int[arraySize];
		generateRandomArray();
	}
	
	public void quickSort(int left, int right)
	
	{
		
		if(right - left <= 0)
		{
			
			if(side != null)
				
			{
				
				System.out.print("\n=============== SORTING ");
				System.out.print(String.format("%5s", side));
				System.out.println(" SIDE AT DEPTH " + depth + " ===============\n");

			} // if
			
			else System.out.println("Sorting depth is 0.\nWe are in the original quickSort call.\n");
			
			System.out.println("                left = [" + left + "]        right = [" + right+ "]");
			System.out.println("\nThese values overlap ---> quickSort will not be run.");
			System.out.print("\n==================== EXITING ");
			System.out.print(String.format("%5s", side));
			System.out.println(" SORT =====================");
			
			return;  // finished sorting: stop.
			
		} // if(right - left <= 0)
		
		else
		
		{
			
			if(side != null)
				
			{
				
				System.out.print("\n=============== SORTING ");
				System.out.print(String.format("%5s", side));
				System.out.println(" SIDE AT DEPTH " + depth + " ===============\n");
				
			} // if
			
			else System.out.println("Sorting depth is " + depth + ".\nWe are in the original quickSort call.\n");
			
			int pivot = theArray[right];  // doesn't matter what but must be value in the array
			
			System.out.println("                left = [" + left + "]        right = [" + right+ "]\n");
			
			printHorzArray(left, right);
			
			System.out.println("Setting \"pivot\" to the value at the \"right\" index:\n");
			System.out.println(">>> Pivot = " + theArray[right]);
			
			System.out.println("\n===================== STARTING PARTITION ====================\n");
			
			int pivotLocation = partitionArray(left, right, pivot);
			
			System.out.println("Preparing for recursion.............\n");
			System.out.println("The previous partition returned a \"left\" index of [" + pivotLocation + "]\n");
			System.out.println("Setting \"pivotLocation\" to the value of \"left\":\n");
			System.out.println(">>> pivotLocation = " + pivotLocation);
			System.out.println();
			
			if(depth==0)
			{
				
				System.out.println("The next (recursive) quickSorts will run on smaller arrays"
					+ "\ncreated from the submitted array, split at index [" + pivotLocation + "]\n");
				
				System.out.println("The arrays used at depth " + (depth + 1) + " are split as shown below:\n");
				
				System.out.print(" LEFT");for(int i=0;i<50;i++)System.out.print(" ");System.out.println("RIGHT");
	
				showSplit(pivotLocation);
				
				printHorzArray(left, pivotLocation - 1);
				
				System.out.println("Keep in mind that when depth becomes 2, both the"
						+ "\nLEFT and RIGHT sides being sorted here will be further"
						+ "\nsplit into two arrays. This will happen every time"
						+ "\ndepth increases, i.e. every time quickSort is recursively"
						+ "\ncalled again on whatever part of the array we are left with.\n");
				
			} // if(depth==0)
			
			System.out.println("============ STARTING RECURSIVE SORT AT DEPTH " + (depth+1)
					+ " =============");
			
			// RECURSION SECTION
			side = "LEFT";
			depth += 1;  // increment depth as we enter recursion
			quickSort(left, pivotLocation - 1);  // partition left side
			depth -= 1; // decrement depth as we exit recursion
			side = "RIGHT";
			depth += 1;  // increment depth as we enter recursion
			quickSort(pivotLocation + 1, right); // partition right side
			
			System.out.println("\n====================== EXITING DEPTH " + depth + " ======================");
			
			depth -= 1; // decrement depth as we exit recursion
			
			
		} // else
		
	} // quickSort
	
	public int partitionArray(int left, int farRight, int pivot)
	
	{
		
		int leftPointer = left - 1;
		int rightPointer = farRight;
		
		System.out.println("Far-most right index from the array submitted to be"
				+ "\npartitioned has been saved for the final swap:"
				+ "\n\n >>> farRight = [" + farRight + "]");
		System.out.println();
		
		while(true)
			
		{
			
			System.out.println("----------------- Searching for leftPointer -----------------\n");
			
			System.out.println("Incrementing leftPointer until theArray[leftPointer] > pivot.\n");
			
			while(theArray[++leftPointer] < pivot);
			
			if(leftPointer >= rightPointer) System.out.println("No values were found before index crossover occured.\n");
			
			else
				
			{
				
				System.out.println(theArray[leftPointer] + " at index [" + leftPointer
						+ "] is HIGHER than the pivot value of " + pivot + ":");
				
				System.out.println("\n>>> leftPointer = " + leftPointer);
				
				printHorzArray(leftPointer, rightPointer);
				
				System.out.println("----------------- Searching for rightPointer ----------------\n");
				System.out.println("Decrementing rightPointer until theArray[rightPointer] < pivot.\n");

				while(rightPointer > 0 && theArray[--rightPointer] > pivot);
				
				if(!(rightPointer <= leftPointer))
					
				{
					
					System.out.println(theArray[rightPointer] + " at index [" + rightPointer
							+ "] is LOWER than the pivot value of " + pivot +":");
					
					System.out.println("\n>>> rightPointer = " + rightPointer);
					System.out.println();
					
					printHorzArray(leftPointer, rightPointer);
					
				} // if(!(rightPointer <= leftPointer))
				
				else System.out.println("No values were found before index crossover occured.\n");
				
			} // else

			if(leftPointer >= rightPointer) 
				
			{
				
				System.out.println("          leftPointer = [" + leftPointer
						+"]     rightPointer = [" + rightPointer + "]");
				
				System.out.println("\nleft and right pointer indexes have crossed over: finished!\n");
				
				break;
				
			} // if(leftPointer >= rightPointer) 
			
			else
				
			{
				
				System.out.println("Swapping values at indexes [" + leftPointer
						+ "] and [" + rightPointer + "]:\n");
				
				swapValues(leftPointer, rightPointer);
				
				displaySwapArrows(leftPointer, rightPointer);
				
				printHorzArray(leftPointer, rightPointer);
				
				System.out.println("=================== CONTINUING PARTITIONING =================\n");
				
			} // else
			
		} // while(true)
		
		System.out.println("Completing final partition swap using index in \"farRight\":\n");
		
		printHorzArray(leftPointer, farRight);
		
		System.out.println("Swapping values at indexes [" + farRight
				+ "] and [" + leftPointer + "]:");
		
		swapValues(leftPointer, farRight);
		
		displaySwapArrows(leftPointer, farRight);
		
		printHorzArray(leftPointer, farRight);
		
		System.out.println("====================== PARTITION COMPLETE ===================\n");
		
		return leftPointer;
		
	} // partitionArray
	
	public void swapValues(int indexOne, int indexTwo)  // Swap the values at given indexes
	
	{
		
		int temp = theArray[indexOne];
		
		theArray[indexOne] = theArray[indexTwo];
		
		theArray[indexTwo] = temp;
		
	} // swapValues
	
	public void generateRandomArray()  // Generate a random array with values between 10 and 59
	
	{  
		
		for (int i = 0; i < arraySize; i++) theArray[i] = (int) (Math.random() * 50) + 10;
		
	} // generateRandomArray
	
	static void printHorzArray(int i, int j)  // Print a visual representation of the Array in its current state
	
	{
		
		for (int n = 0; n < 61; n++) System.out.print("-");
		System.out.println();
		for (int n = 0; n < arraySize; n++) System.out.format("| %2s " + " ", n);
		System.out.println("|");
		for (int n = 0; n < 61; n++) System.out.print("-");
		System.out.println();
		for (int n = 0; n < arraySize; n++) System.out.print(String.format("| %2s " + " ", theArray[n]));
		System.out.println("|");
		for (int n = 0; n < 61; n++) System.out.print("-");
		System.out.println();

		if (i != -1)
		
		{

			// Number of spaces to put before the L
			int spacesBeforeFront = 2 + (6 * i);
			for (int k = 0; k < spacesBeforeFront; k++) System.out.print(" ");
			System.out.print(String.format("%2s", "L"));

			// Number of spaces to put before the R
			int spacesBeforeRear = (6 * j) - spacesBeforeFront;
			for (int l = 0; l < spacesBeforeRear; l++) System.out.print(" ");
			System.out.print(String.format("%2s", "R"));
			System.out.println("\n");

		} // if (i != -1)

	} // printHorzArray
	
	public static void displaySwapArrows(int left, int right)  // Draw arrows depicting values in the array switching places
	
	{
		
		int initialSpaces = 3 + (6 * left);
		int connectingSpaces = (6 * right) - (initialSpaces - 3);
		
		for(int i = -1; i < initialSpaces; i++) System.out.print(" ");  // 1st line, initial spaces
		for(int i = 0; i < connectingSpaces - 1; i++) System.out.print("-"); // 1st line, connecting dashes
		System.out.println();
		for(int i = 0; i < initialSpaces; i++) System.out.print(" ");  // 2nd line, initial spaces
		System.out.print("|");
		for(int i = 0; i < connectingSpaces - 1; i++) System.out.print(" "); // 2nd line, connecting spaces
		System.out.println("|");
		for(int i = 0; i < initialSpaces; i++) System.out.print(" ");  // 3rd line, initial spaces
		System.out.print("v");
		for(int i = 0; i < connectingSpaces - 1; i++) System.out.print(" "); // 3rd line, connecting spaces
		System.out.println("v");

	} // displaySwapArrows
	
	public static void showSplit(int split)  // Draw a line across the array depicting where it is split for the next sort
	{
		
		System.out.print("<");
		for(int i = (split * 6) - 1; i > 0; i--) System.out.print("-");
		System.out.print("|");
		for(int i = ((split) * 6) + 2; i < 61; i++) System.out.print("-");
		System.out.println(">");
		
	} // showSplit
	
	public static void main(String[] args)
	
	{
		
		System.out.println("\"Depth\" tracks what level of recursion we are currently\n"
				+ "sorting in, i.e. depth = 0 is the original call to quickSort.\n");
		System.out.println("If the original quickSort makes a recursive call, the depth\n"
				+ "of the new quickSort will be 1. Should the quickSort with\n"
				+ "depth=1 make another recursive call, the depth of that call\n"
				+ "would be 2. ETC.");

		System.out.println("\nThis allows us to track where we are in the code.\n");
		
		System.out.println("A great way to understand this is to draw a tree diagram:\n");
		System.out.println("Start with a single seed labelled D0 (depth = 0).");
		System.out.println("Follow the code, and when you see depth change to 1,");
		System.out.println("draw two new sorts below the seed, one on the left,");
		System.out.println("and one on the right. You can label them LD1 and RD1");
		System.out.println("for (left, depth=1) and (right, depth=1).");
		System.out.println();
		System.out.println("Also label each sort with the left and right indexes "
				+ "\nthey start their partitions with.");
		System.out.println();
		System.out.println("Watch for when the sort at LEFT DEPTH 1 starts a new"
				+ "\nquickSort, which is labelled as \"STARTING RECUSIVE SORT\","
				+ "\nthen draw the next two sorts below LD1, and label them "
				+ "\nboth appropriately as LD2 and RD2.");
		
		System.out.println("\nBy the time you finish drawing the tree, you will"
				+ "\nunderstand the quickSort inside out. Good luck!");

		
		System.out.println("\n=============================================================\n");

		QuickSort theSort = new QuickSort(10);
		
		System.out.println("Original randomly generated (unsorted) array:\n");
		System.out.println(Arrays.toString(QuickSort.theArray));
		System.out.println("\n======================== STARTING SORT ======================\n");
		
		// every value smaller than 35 will be on the left
		// and every value larger on the right
		theSort.quickSort(0, 9);
		
		System.out.println("\n============= EXITING ORIGINAL SORT AT DEPTH " + depth + " ==============");
		System.out.println("\n====================== SORTING COMPLETE =====================\n");
		System.out.println("Array after partitioning: \n");
		System.out.println(Arrays.toString(QuickSort.theArray));
		
	} // main
	
} // class