Navigation Menu

Skip to content

Instantly share code, notes, and snippets.

@developerjake
Created April 4, 2017 23:11
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save developerjake/6266218d6130a2b6f732069626b62fd4 to your computer and use it in GitHub Desktop.
Save developerjake/6266218d6130a2b6f732069626b62fd4 to your computer and use it in GitHub Desktop.
Partitioning class with various print statements for clarity
import java.util.Arrays;
public class Partitioning {
private static int[] theArray;
private static int arraySize;
public void partitionArray(int pivot)
{
// leftPointer sorts through array until finding a value > pivot,
// then waits for rightPointer to find a value < pivot.
// These two values are then switched.
int leftPointer = -1; // starts on left side
int rightPointer = arraySize; // starts on right side
while(true)
{
System.out.println("================== Searching for leftPointer ================\n");
// run until reaching end of array OR and item > pivot is found
// leftPointer is incremented before evaluation to become 0 (starts at -1)
while(leftPointer < (arraySize - 1) && theArray[++leftPointer] < pivot) ;
System.out.println(" >>> Value at index [" + leftPointer + "] is higher than the pivot value.\n"
+ "\n ---> i.e. " + theArray[leftPointer] + " > " + pivot
+ "\n\n >>> \"leftPointer\" value set to " + leftPointer + ".\n");
printHorzArray(leftPointer, rightPointer - 1);
System.out.println("================== Searching for rightPointer ===============\n");
while(rightPointer > 0 && theArray[--rightPointer] > pivot) ;
if(leftPointer >= rightPointer)
{
System.out.println("left and right pointer indexes have crossed over: finished!");
break;
}
System.out.println(" >>> Value at index [" + rightPointer + "] is lower than the pivot value.\n"
+ "\n ---> i.e. " + theArray[rightPointer] + " < " + pivot
+ "\n\n >>> \"rightPointer\" value set to " + rightPointer + ".\n");
printHorzArray(leftPointer, rightPointer);
System.out.println("Swapping values at indexes [" + leftPointer + "] and [" + rightPointer + "]:\n");
swapValues(leftPointer, rightPointer);
displaySwapArrows(leftPointer, rightPointer);
printHorzArray(leftPointer, rightPointer);
System.out.println("Value \"" + theArray[leftPointer] + "\" has switched position with value \""
+ theArray[rightPointer] + "\".\n");
System.out.println("\n======================= Swap complete =======================\n");
} // while(true)
} // partitionArray
Partitioning(int newArraySize) // Class Constructor
{
arraySize = newArraySize;
theArray = new int[arraySize];
generateRandomArray();
}
public void swapValues(int indexOne, int indexTwo) // Swap the values at given indexes
{
int temp = theArray[indexOne];
theArray[indexOne] = theArray[indexTwo];
theArray[indexTwo] = temp;
}
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;
}
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)
{
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 main(String[] args)
{
Partitioning partitionArray = new Partitioning(10);
System.out.println("Original randomly generated array:\n");
System.out.println(Arrays.toString(Partitioning.theArray));
System.out.println("\nPivot value set to \"35\"");
System.out.println("\n======================== Starting sort ======================\n");
// every value smaller than 35 will be on the left
// and every value larger on the right
partitionArray.partitionArray(35);
System.out.println("\n==================== Partitioning complete ===================\n");
System.out.println("Array after partitioning: \n");
System.out.println(Arrays.toString(Partitioning.theArray));
} // main
} // class
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment