sorts

Class Quicksort2311

java.lang.Object

sorts.Quicksort2311

public class Quicksort2311
extends java.lang.Object

Written: 9/30/2017 Last updated: 9/30/2017

Requirement: Class must be in sorts package and exercises.* and java.lang.* must be imported.

Javadoc: javadoc -author -version -private -classpath .;algs4_sts.jar; -d .\javadoc Quicksort2311.java

Compilation: javac -cp .;algs4_sts.jar; Quicksort2311.java

Execution 1: java -cp ../;.;algs4_sts.jar; sorts.Quicksort2311 <quicksort.txt

Execution 2: java -cp ../;.;algs4_sts.jar; sorts.Quicksort2311 <qsShuffled.txt

Summary: QuickSort uses the divide and conquer method to sort a list of values. However, instead of dividing the array in half, it identifies a pivotValue, which is used to find a partition, and enforce the rules below. The partition is used to sort the left and right subarrays:

1. The entry a[rtScanIndex] is in its final place in the array
2. No entry on the leftside of the array (a[lo]-a[rtScanIndex-1]) is greater than a[rtScanIndex].
3. No entry on the right side of the array (a[rtScanIndex+1] through a[hi]) is less than a[rtScanIndex].

Initialize the leftScanIndex with the lo value, and initialize the rightScanIndex with the hi+1 value. The pivotValue is initially set to the array's first index value (a[lo]), however, this is not the partition value. The pivotValue is the sentinel value that is exchanged anytime a value less than it is found during the left or right scan. The left scan starts from 0 and is preincremented. The right scan starts at hi+1 and is predecremented. The increment and decrement occur while the leftIndexScan value is less than the pivotValue, and the pivotValue is less than the rightIndexScan value. If the leftIndexScan reaches the end of the array, or the rightIndexScan reaches the beginning of the array, break out of the inner while loops. However, if the rightIndexScan value is less than the pivotValue or the leftIndexScan value is greater than the pivotValue, we know that the array elements are out of order, and they should be exchanged, so the inner loop condition fails, and the program execution is returned to the first condition after the inner while loops. Condition: If (leftIndex crossed/equals rightIndex) leftScanIndex >= rightScanIndex, then break out of the outer loop. If the condition is false, then only the value of a[leftScanIndex] is exchanged with a[rtScanIndex]. This is the isRTIndexExchanged and LTIndexExchanged conditions, which is highlighted in red and blue, respectively. However, if the condition is true, the outer while loop is exited, and the pivotValue in a[lo] must be swopped with the value in a[rightIndexScan], because all the values have been compared. Thus, the lowest value is pushed from the right side, and is currently in the rtScanIndex element and the highest value has been pushed from the left side, and is currently in the ltScanIndex element. This is the hasRTCrossedLTIndex and hasLTCrossedRTIndex conditions, which are highlighted in magenta and cyan, respectively. So, a[rtIndexScan] becomes the (new pivotValue) partitionValue. This is the isPartitionFound condition, which is highlighted in orange (Note: the partitionValue will show as orange/cyan because the two conditions overlap). Then the partition method returns the partitionValue to the main program, which can then be used to recursively sort the left and right half of the array, and since the rules above hold true, once both halves are sorted, the whole array is sorted.

Methods:

1. partion() method finds the partition for the array to be divided on and formats the array, so it complies with the 3 rules for quicksort.
2. sort() method sorts the subarray.
3. isRTIndexExchanged() and isLTIndexExchanged() - If the leftScanIndex is less than the rightScanIndex, a[lo] is exchanged with a[rightScanIndex-1]. The output characters are hightlighted in the red and blue colors, respectively.
4. hasRTCrossedLTIndex() and hasLTCrossedLTIndex() - If the leftScanIndex is greater than or equal to rightScanIndex, a[leftScanIndex] is exchanged with a[rightScanIndex]. The output characters are hightlighted in magenta and cyan, respectively.
5. isPartitionFound() - Highlights the first partition found in orange, as it is the partition for the complete array.

Files: Contains a 15+ char array to be sorted.

Version:

1.7

Author:

Tony Lockhart

Field Summary

Fields

Modifier and Type	Field and Description
static java.lang.Comparable[]	a
static boolean	exchange
static boolean	exchange2
static int	leftIncrementCtr
static int	leftScanIndex
static int	partitionCtr
static int	rightDecrementCtr
static int	rightScanIndex
static int	tableHeight
static int	tableWidth
static double	yOffset

Constructor Summary

Constructors

Constructor and Description
Quicksort2311()

Method Summary

Methods

Modifier and Type	Method and Description
static void	copyArray(java.lang.Comparable[] destination, java.lang.String[] source)
static void	drawBlack(int tableHeight)
static void	drawBlue(int tableHeight)
static void	drawCyan(int tableHeight)
static void	drawGray(int tableHeight)
static void	drawGreen(int tableHeight)
static void	drawMagenta(int tableHeight)
static void	drawOrange(int tableHeight)
static void	drawRed(int tableHeight)
static void	drawWhite(int tableHeight)
private static void	dualPrint(java.lang.Comparable[] a, int lo, int ltToRtIndexPtr, int rtToLtIndexPtr, boolean exchange, boolean exchange2, boolean leftScanIncremented, boolean rightScanDecremented, int leftIncrementCtr, int rightDecrementCtr, int partitionCtr)
private static void	exch(java.lang.Comparable[] a, int leftIndex, int rightIndex)
private static void	graph(java.lang.Comparable[] a, int lo, int ltToRtIndexPtr, int rtToLtIndexPtr, boolean exchange, boolean exchange2, boolean leftScanIncremented, boolean rightScanDecremented, int leftIncrementCtr, int rightDecrementCtr, int partitionCtr)
static boolean	hasLtCrossedRtIndex(int lo, double loIndexPtrValue, double rtToLtIndexPtrValue, int rtToLtIndexPtr, int k, int ltToRtIndexPtr, boolean isLTIndexExchanged, boolean isRTIndexExchanged, boolean exchange, boolean exchange2)
static boolean	hasRtCrossedLtIndex(int lo, int rtToLtIndexPtr, int k, int ltToRtIndexPtr, boolean isLTIndexExchanged, boolean isRTIndexExchanged, double rtToLtIndexPtrValue, double loIndexPtrValue, boolean exchange, boolean exchange2)
static boolean	isInitialArraySet(int ltToRtIndexPtr, int rtToLtIndexPtr, boolean exchange, boolean leftScanIncremented, boolean rightScanDecremented)
static boolean	isLTIndexExchanged(int k, int rtToLtIndexPtr, int ltToRtIndexPtr, boolean exchange, boolean leftScanIncremented, double rtToLtIndexPtrValue, double ltToRtIndexPtrValue)
static boolean	isMultLTIndexFound(java.lang.String charConvert, int k, int leftIncrementCtr, int ltToRtIndexPtr, boolean exchange, boolean leftScanIncremented)
static boolean	isMultRTIndexFound(java.lang.String charConvert, int k, int rightDecrementCtr, int rtToLtIndexPtr, boolean exchange, boolean rightScanDecremented)
static boolean	isNoIndexFound(boolean isInitialArraySet, boolean isMultLTIndexFound, boolean isMultRTIndexFound, boolean isRTIndexExchanged, boolean isLTIndexExchanged, boolean hasRTCrossedLTIndex, boolean hasLTCrossedRTIndex)
static boolean	isPartitionFound(int lo, double loIndexPtrValue, double rtToLtIndexPtrValue, int rtToLtIndexPtr, int k, int ltToRtIndexPtr, boolean isNoIndexFound, boolean isMultiLTIndexFound, boolean isMultiRTIndexFound, boolean isRTIndexExchanged, int partitionCtr)
static boolean	isRTIndexEqual2Zero(int k, int rtToLtIndexPtr, boolean exchange, boolean exchange2, boolean isInitialArraySet)
static boolean	isRTIndexExchanged(int k, int rtToLtIndexPtr, int ltToRtIndexPtr, boolean exchange, boolean rightScanDecremented, double rtToLtIndexPtrValue, double ltToRtIndexPtrValue)
static boolean	isSorted(java.lang.Comparable[] a)
private static boolean	less(java.lang.Comparable v, java.lang.Comparable w)
static void	main(java.lang.String[] args)
private static int	partition(java.lang.Comparable[] a, int lo, int hi)
static void	printArray(java.lang.Comparable[] array)
private static void	show(java.lang.Comparable[] a)
static void	sort(java.lang.Comparable[] a)
static void	sort(java.lang.Comparable[] a, int lo, int hi)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

tableHeight

public static final int tableHeight

See Also:

Constant Field Values

yOffset

public static double yOffset

tableWidth

public static final int tableWidth

See Also:

Constant Field Values

exchange

public static boolean exchange

exchange2

public static boolean exchange2

a

public static java.lang.Comparable[] a

leftScanIndex

public static int leftScanIndex

rightScanIndex

public static int rightScanIndex

leftIncrementCtr

public static int leftIncrementCtr

rightDecrementCtr

public static int rightDecrementCtr

partitionCtr

public static int partitionCtr

Constructor Detail

Quicksort2311

public Quicksort2311()

Method Detail

sort

public static void sort(java.lang.Comparable[] a)

sort

public static void sort(java.lang.Comparable[] a,
        int lo,
        int hi)

partition

private static int partition(java.lang.Comparable[] a,
            int lo,
            int hi)

less

private static boolean less(java.lang.Comparable v,
           java.lang.Comparable w)

exch

private static void exch(java.lang.Comparable[] a,
        int leftIndex,
        int rightIndex)

show

private static void show(java.lang.Comparable[] a)

dualPrint

private static void dualPrint(java.lang.Comparable[] a,
             int lo,
             int ltToRtIndexPtr,
             int rtToLtIndexPtr,
             boolean exchange,
             boolean exchange2,
             boolean leftScanIncremented,
             boolean rightScanDecremented,
             int leftIncrementCtr,
             int rightDecrementCtr,
             int partitionCtr)

graph

private static void graph(java.lang.Comparable[] a,
         int lo,
         int ltToRtIndexPtr,
         int rtToLtIndexPtr,
         boolean exchange,
         boolean exchange2,
         boolean leftScanIncremented,
         boolean rightScanDecremented,
         int leftIncrementCtr,
         int rightDecrementCtr,
         int partitionCtr)

isRTIndexEqual2Zero

public static boolean isRTIndexEqual2Zero(int k,
                          int rtToLtIndexPtr,
                          boolean exchange,
                          boolean exchange2,
                          boolean isInitialArraySet)

isNoIndexFound

public static boolean isNoIndexFound(boolean isInitialArraySet,
                     boolean isMultLTIndexFound,
                     boolean isMultRTIndexFound,
                     boolean isRTIndexExchanged,
                     boolean isLTIndexExchanged,
                     boolean hasRTCrossedLTIndex,
                     boolean hasLTCrossedRTIndex)

isPartitionFound

public static boolean isPartitionFound(int lo,
                       double loIndexPtrValue,
                       double rtToLtIndexPtrValue,
                       int rtToLtIndexPtr,
                       int k,
                       int ltToRtIndexPtr,
                       boolean isNoIndexFound,
                       boolean isMultiLTIndexFound,
                       boolean isMultiRTIndexFound,
                       boolean isRTIndexExchanged,
                       int partitionCtr)

isLTIndexExchanged

public static boolean isLTIndexExchanged(int k,
                         int rtToLtIndexPtr,
                         int ltToRtIndexPtr,
                         boolean exchange,
                         boolean leftScanIncremented,
                         double rtToLtIndexPtrValue,
                         double ltToRtIndexPtrValue)

hasLtCrossedRtIndex

public static boolean hasLtCrossedRtIndex(int lo,
                          double loIndexPtrValue,
                          double rtToLtIndexPtrValue,
                          int rtToLtIndexPtr,
                          int k,
                          int ltToRtIndexPtr,
                          boolean isLTIndexExchanged,
                          boolean isRTIndexExchanged,
                          boolean exchange,
                          boolean exchange2)

isRTIndexExchanged

public static boolean isRTIndexExchanged(int k,
                         int rtToLtIndexPtr,
                         int ltToRtIndexPtr,
                         boolean exchange,
                         boolean rightScanDecremented,
                         double rtToLtIndexPtrValue,
                         double ltToRtIndexPtrValue)

hasRtCrossedLtIndex

public static boolean hasRtCrossedLtIndex(int lo,
                          int rtToLtIndexPtr,
                          int k,
                          int ltToRtIndexPtr,
                          boolean isLTIndexExchanged,
                          boolean isRTIndexExchanged,
                          double rtToLtIndexPtrValue,
                          double loIndexPtrValue,
                          boolean exchange,
                          boolean exchange2)

isInitialArraySet

public static boolean isInitialArraySet(int ltToRtIndexPtr,
                        int rtToLtIndexPtr,
                        boolean exchange,
                        boolean leftScanIncremented,
                        boolean rightScanDecremented)

isMultRTIndexFound

public static boolean isMultRTIndexFound(java.lang.String charConvert,
                         int k,
                         int rightDecrementCtr,
                         int rtToLtIndexPtr,
                         boolean exchange,
                         boolean rightScanDecremented)

isMultLTIndexFound

public static boolean isMultLTIndexFound(java.lang.String charConvert,
                         int k,
                         int leftIncrementCtr,
                         int ltToRtIndexPtr,
                         boolean exchange,
                         boolean leftScanIncremented)

drawBlack

public static void drawBlack(int tableHeight)

drawWhite

public static void drawWhite(int tableHeight)

drawRed

public static void drawRed(int tableHeight)

drawOrange

public static void drawOrange(int tableHeight)

drawCyan

public static void drawCyan(int tableHeight)

drawBlue

public static void drawBlue(int tableHeight)

drawGreen

public static void drawGreen(int tableHeight)

drawMagenta

public static void drawMagenta(int tableHeight)

drawGray

public static void drawGray(int tableHeight)

isSorted

public static boolean isSorted(java.lang.Comparable[] a)

copyArray

public static void copyArray(java.lang.Comparable[] destination,
             java.lang.String[] source)

printArray

public static void printArray(java.lang.Comparable[] array)

main

public static void main(java.lang.String[] args)