I'm building a sorting algorithm visualizer in processing (extension of java with extra libraries for visualization) and i'm very much stuck on this problem which I think others will be able to help me solve. In processing there is a function called draw() that is being called 60 times each second. It's here that I want to execute, each time draw() is called, one step of the insertion algorithm. I already implemented it with a bubble sort. (see code below). updateBubble() is being called in draw() and 'colors' is the name of the arraylist I use to keep the different values of colors to sort.
picture to get a better understanding: [![visualisation algorithm preview][1]][1]
...
int j = 0
...
void updateBubble() {
bubble.sort(j);
j++;
if (i<bubble.colors.size()) {
if (j >= bubble.colors.size()-i-1) {
j = 0;
i++;
}
} else {
bubble.sorted = true;
}
}
and here is the function in the class BubbleSort (bubble is an object of this class)
void sort(int j) {
if (j<colors.size()-1) {
if (colors.get(j) > colors.get(j+1))
{
int temp = colors.get(j);
colors.set(j, colors.get(j+1));
colors.set((j+1), temp);
}
}
}
This way I was able to slow down the visualization process to the the pace of the framerate which I can control myself without using loops which would execute the sorting algorithm immediately. Now I also wanted to make a similar implementation for the insertion sort algorithm but i feel like i'm stuck because I don't seem to be able to use a similar implementation that works or there might be a better way to do this? What I have at the moment executes it immediately as expected, without being able to see the process.
void updateInsertion() {
insertion.sort();
}
void sort() {
int n = colors.size();
for (int i = 1; i < n; ++i) {
int key = colors.get(i);
int j = i - 1;
while (j >= 0 && colors.get(j) > key) {
colors.set(j+1, colors.get(j));
j = j - 1;
}
colors.set(j+1, key);
}
}
this is what i got now: which is still wrong but is getting closer and clearifies what i'm trying to reach, making a function that only works with increments and if statements instead of whiles and fors so each different step is being executed with each call of the method.
// i resembles for loop variable
if (i<insertion.colors.size()) {
if (j<0 || insertion.colors.get(j) <= insertion.colors.get(i)) { // negative check to go out of while loop
insertion.colors.set(j+1, keap);
if(notSortedYet()){
i++;
keap = insertion.colors.get(i);
j = i - 1;
}
} else { // resembles being in the while loop
insertion.colors.set((j+1), insertion.colors.get(j));
j = j - 1;
}
}
}
EDIT: I fixed it and you can find my solution beneath :) everytime updateInsertion() is called, my code will execute exact one step in the algorithm! thanks to everyone who put effort into commenting, I dont know if this is best practise, so keep me updated on that if you want!
void updateInsertion() {
// i resembles for loop variable
if (i<insertion.colors.size()) {
if (j>=0 && insertion.colors.get(j) > firstUnsorted) {
int temp = insertion.colors.get(j+1);
insertion.colors.set((j+1), insertion.colors.get(j));
insertion.colors.set(j,temp);
j = j - 1;
} else {
insertion.colors.set(j+1, firstUnsorted);
if (i<insertion.colors.size()-1) {
i++;
}
firstUnsorted = insertion.colors.get(i);
j = i - 1;
}
}
}