I'm working on a sorting visualiser project in JavaFX. I have managed to get a bubble sort and insertion sort working however I am having issues with implementing the quicksort.
the code below is my quick sort implementation. The logic works when removing the visual side.
private void quickSort(int[] arr, int high) {
new Thread(() -> {
enableButton(true);
quickSortHelper(arr, 0, high);
}).start();
}
private void quickSortHelper(int[] arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSortHelper(arr, low, pi - 1);
quickSortHelper(arr, pi + 1, high);
}
}
private void qSwapHelper(int[] arr, int i, int j) {
CountDownLatch latch = new CountDownLatch(1);
Platform.runLater(() -> {
swapBarsWithAnimation((Rectangle) mainAPane.getChildren().get(i), (Rectangle) mainAPane.getChildren().get(j), latch);
});
try {
latch.await();
} catch (Exception _) {
}
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
private int partition(int[] arr, int low, int high) {
// choose the pivot
int pivot = arr[high];
int i = low-1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
qSwapHelper(arr, i, j);
}
}
qSwapHelper(arr, i+1, high);
return (i+1);
}
below is how I manage the animations. I'm using 2 translation transitions which run simultaneously with a parallel transition. On completion, the anchors are updated in the anchor pane and the bars are removed before being readded in their swapped positions to reflect the visual state logically.
private void swapBarsWithAnimation(Rectangle bar1, Rectangle bar2, CountDownLatch latch) {
double bar1Pos = AnchorPane.getLeftAnchor(bar1);
double bar2Pos = AnchorPane.getLeftAnchor(bar2);
TranslateTransition bar1ToBar2Transition = new TranslateTransition(Duration.millis(DURATION_TIME), bar1);
bar1ToBar2Transition.setByX(bar2Pos - bar1Pos);
TranslateTransition bar2ToBar1Transition = new TranslateTransition(Duration.millis(DURATION_TIME), bar2);
bar2ToBar1Transition.setByX(bar1Pos - bar2Pos);
ParallelTransition pt = new ParallelTransition(bar1ToBar2Transition, bar2ToBar1Transition);
Double finalBar2Pos = bar2Pos;
Double finalBar1Pos = bar1Pos;
pt.setOnFinished(_ -> {
AnchorPane.setLeftAnchor(bar1, finalBar2Pos);
AnchorPane.setLeftAnchor(bar2, finalBar1Pos);
ObservableList<Node> children = mainAPane.getChildren();
int indexOfBar1 = children.indexOf(bar1);
int indexOfBar2 = children.indexOf(bar2);
children.removeAll(bar1, bar2);
children.add(indexOfBar1, bar2);
children.add(indexOfBar2, bar1);
bar1.setTranslateX(0);
bar2.setTranslateX(0);
latch.countDown();
});
pt.play();
}
my understanding is that anything visual needs to run on the JavaFX main thread so I've used Platform.RunLater() to achieve this. As mentioned before my bubble sort and insertion are working great so it must be something to do with the use of recursion maybe?
I was thinking add the transitions to a queue or list then executing them, this way they would definitely run in order?
I am intending to add more sorts including merge sort and I assume I'll have to same issue.
Any help is greatly appreciated I'm a bit stuck.
From the comments:
from debugging, i've noticed the index of bar 1 and 2 is often the same in the quick sort
This will cause an "duplicate child error". If the indexes are the same, then the two references to the bars refer to the same node: i.e. bar1 == bar2. Then
children.removeAll(bar1, bar2);
will just remove the one (and only) bar,
children.add(indexOfBar1, bar2);
will add the bar back in, and
children.add(indexOfBar2, bar1);
will attempt to add it a second time, throwing the exception.
Note also that if i > j, this will fail in a different way, as children.add(indexOfBar1, bar2); will add bar2 at the wrong location in the list.
It feels as though the situation where i >= j should never arise, but Quick Sort is a pretty complicated algorithm, and it's possible that, at least, i == j may be a valid scenario in some implementations of the partition*.
A more robust way to swap the bars is to create a temporary list, swap them in the temporary list, then copy the temporary list back to the child list:
pt.setOnFinished(_ -> {
AnchorPane.setLeftAnchor(bar1, finalBar2Pos);
AnchorPane.setLeftAnchor(bar2, finalBar1Pos);
ObservableList<Node> children = mainAPane.getChildren();
int indexOfBar1 = children.indexOf(bar1);
int indexOfBar2 = children.indexOf(bar2);
//children.removeAll(bar1, bar2);
//children.add(indexOfBar1, bar2);
//children.add(indexOfBar2, bar1);
List<Node> bars = new ArrayList<>(children);
Node temp = bars.get(indexOfBar1);
bars.set(indexOfBar1, bars.get(indexOfBar2));
bars.set(indexOfBar2, temp);
children.setAll(bars);
bar1.setTranslateX(0);
bar2.setTranslateX(0);
latch.countDown();
});
* If I may be allowed an anecdote, my father's first ever job was to write an Algol compiler, and his boss was Tony Hoare. This was around the time that Hoare had just invented Quick Sort. My dad said that he and his colleagues spent a lot of time trying to understand how and why Quick Sort worked, but none of them could ever really explain why it was so efficient in the majority of cases. They speculated that Tony Hoare never really understood his own algorithm either (though I doubt this is the case).