Created
April 4, 2017 23:11
-
-
Save developerjake/6266218d6130a2b6f732069626b62fd4 to your computer and use it in GitHub Desktop.
Partitioning class with various print statements for clarity
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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