Reputation: 11
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;
}
}
}
Upvotes: 1
Views: 376
Reputation: 3207
I love this project.
Processing also have a millis()
method which returns how many milliseconds were spent since you've started your sketch. I sometimes use it to time my animations, which could come in handy right here. Here's an implementation of a timer class:
class Delay {
int limit;
Delay (int l) {
limit = millis() + l;
}
boolean expired () {
return (millis() > limit);
}
}
I suggest that you use this class instead of tweaking the FPS. By using the Delay to slow down your implementation of the sort, you're letting the computer work at it's own rhythm and only draw a new frame when you need it. Like this (excuse the parts where I say "do stuff"):
Delay holdTheFrame = new Delay(1);
void draw() {
if(holdTheFrame.expired()) {
holdTheFrame = new Delay(500); // half a second before the next frame
// Advance one step forward in your sorting
// Draw the visualization of the data
}
}
You can fine tune at what pace your data is sorted and only paint it when it changes. It's win-win!
Have fun!
EDIT
To help you with the implementation, here's an example one. You can copy and paste this code in an empty Processing sketch and it'll run as-is. To make things easier on my side I print to console instead of using the graphical display, but you should be able to get what I'm doing.
The secret here is that my sorting algorithm have been subtly modified so they instead always run only ONE sorting step when I call them. See for yourself:
int _numberOfItems = 10;
int _sortingStep = 0;
IntList _bubbleList = new IntList();
boolean _bubbleListSorted = false;
IntList _selectionList = new IntList();
IntList _insertionList = new IntList();
Delay _delay = new Delay(1);
void setup() {
for (int i=0; i<_numberOfItems; i++) {
_bubbleList.append((int)random(10, 99));
}
for (int i=0; i<_numberOfItems; i++) {
_selectionList.append((int)random(10, 99));
}
for (int i=0; i<_numberOfItems; i++) {
_insertionList.append((int)random(10, 99));
}
}
void draw() {
if (_delay.expired()) {
_delay = new Delay(500);
// sort one step with every algo you want to display
if (!_bubbleListSorted) {
singleStepBubbleSort(_bubbleList);
}
if (_sortingStep < _numberOfItems) {
singleStepSelectionSort(_selectionList, _sortingStep);
singleStepInsertionSort(_insertionList, _sortingStep);
}
_sortingStep++;
// update the display (I'm printing to console instead for simplicity)
for (int i : _bubbleList) {
print(i + " ");
}
print(" | ");
for (int i : _selectionList) {
print(i + " ");
}
print(" | ");
for (int i : _insertionList) {
print(i + " ");
}
print("\n");
}
}
// An "single-step" implementation of Insertion Sort
void singleStepInsertionSort(IntList list, int step) {
int k = list.get(step);
int j = step - 1;
while (j >= 0 && list.get(j) > k) {
list.set(j+1, list.get(j));
j = j - 1;
}
list.set(j+1, k);
}
// An "single-step" implementation of Bubble Sort
void singleStepBubbleSort(IntList list) {
int temp;
boolean swapped = false;
for (int i=0; i<list.size()-1; i++)
{
if (list.get(i) > list.get(i + 1))
{
// swap arr[j] and arr[j+1]
temp = list.get(i);
list.set(i, list.get(i+1));
list.set(i+1, temp);
swapped = true;
}
}
if (!swapped) {
_bubbleListSorted = true;
}
}
// An "single-step" implementation of Selection Sort
void singleStepSelectionSort(IntList list, int step)
{
int min_idx = step;
for (int j = step+1; j < list.size(); j++) {
if (list.get(j) < list.get(min_idx)) {
min_idx = j;
}
}
int temp = list.get(min_idx);
list.set(min_idx, list.get(step));
list.set(step, temp);
}
class Delay {
int limit;
Delay (int l) {
limit = millis() + l;
}
boolean expired () {
return (millis() > limit);
}
}
Let me know if you have questions.
MORE EDITS:
Every swap of an insertion sort means many, many swaps. It's a real pain because this algorithm is kinda complicated to stop in it's tracks.
Luckily, I don't care. Thinking outside the box, I opted instead to create a class dedicated to sort an array while recording how to sort it, then be able to play it back "as if it was happening in real time". take a look:
int numberOfItems = 10;
int sortingStep = 0;
Delay delay = new Delay(1);
ManagedSelectionSort managedSelectionSort; // I created a class just to manage this madness
void setup() {
IntList list = new IntList();
for (int i=0; i<numberOfItems; i++) {
list.append((int)random(10, 99)); // some random numbers to sort later
}
managedSelectionSort = new ManagedSelectionSort(list); // take a look at the instantiation of this class
print("Step " + String.format("%02d", sortingStep) + ": ");
printArray(managedSelectionSort.list);
print("\n");
}
void draw() {
if (delay.expired()) {
delay = new Delay(100); // i put a very short delay, you'll probably want to tweak this
managedSelectionSort.sortOneStep(); // this is not what it seems
sortingStep++;
print("Step " + String.format("%02d", sortingStep) + ": ");
printArray(managedSelectionSort.list);
print("\n");
}
}
// this class is where the magic happens
// we'll sort the array all at once while recording every move
// then we'll play back those moves on a copy of the array
class ManagedSelectionSort {
IntList list, hiddenList; // list is the "official" list, while hiddenList is where the heavy lifting happens
ArrayList<SwapIndex> swapList; // this is where I record how to sort the array
ManagedSelectionSort(IntList baseList) { // this way I can instantiate several similar objects with the same list
list = new IntList();
hiddenList = new IntList();
swapList = new ArrayList<SwapIndex>();
for (int i : baseList) {
// both lists have the same initial numbers
list.append(i);
hiddenList.append(i);
}
// as soon as this object is instantiated, it knows how it'll sort the array
// because it already did...
hiddenSort();
}
// this method plays the moves which were recorded earlier according to the current sortingStep
// the swapList array was filled with every swap needed to sort the array, one by one
// now it's just a matter of playing them back on a copy of the initial array
void sortOneStep() {
if (sortingStep < swapList.size()) {
swap(list, swapList.get(sortingStep).index1, swapList.get(sortingStep).index2);
}
}
// this is the real implementation of the insertion sort
void hiddenSort()
{
for (int i=1; i<hiddenList.size(); i++) {
int j = i;
while (j>0 && hiddenList.get(j) < hiddenList.get(j-1)) {
swap(hiddenList, j, j-1, true); // swap is a class specific helper method, it swaps the numbers and also records the move
j--;
}
}
}
// this is an overload, i could have done without but it's confortable
void swap(IntList list, int index1, int index2) {
swap(list, index1, index2, false);
}
void swap(IntList list, int index1, int index2, boolean recordMove) {
// the swap first
int temp = list.get(index1);
list.set(index1, list.get(index2));
list.set(index2, temp);
// if the method is set on 'record', it adds this move to the swapList array
if (recordMove) {
swapList.add(new SwapIndex(index1, index2));
}
}
}
// this class could have been a struct, but I like to start in OOP right from the bat in case things gets complicated
class SwapIndex {
int index1;
int index2;
SwapIndex(int index1, int index2) {
this.index1 = index1;
this.index2 = index2;
}
}
// this method is just an helper method to print to console
void printArray(IntList list) {
for (int i : list) {
print(i + " ");
}
}
class Delay {
int limit;
Delay (int l) {
limit = millis() + l;
}
boolean expired () {
return millis() > limit;
}
}
This should solve your initial problem, if I understood it right this time!
Upvotes: 1
Reputation: 307
One way to achieve this is via a some sort of stored state. Below is at a high level what I'm talking about.
// Starts the procedure. Must be called before draw().
void init() {
state = "forLoop";
i = 1;
n = colors.size();
}
// Single iteration of a loop.
void draw(){
switch(state) {
case "forLoop":
doForBody();
break;
case "whileLoop":
doWhileLoopBody();
break;
...
}
}
// Executes everything in the while loop and the one or two things
// just after it.
void doWhileLoopBody() {
if (isThisIterationOfWhileDone()) {
// Get out of the while loop and prepare for the next iteration of for.
// A better way to what I'm doing on the next couple lines here would
// be to introduce an additional state (ex: "postWhile") that would
// execute just after this method and would handle the colors.set(),
// incrementing i, etc.
state = "forLoop";
colors.set(j+1, key);
i++;
return;
}
// update colors, value of j, etc...
}
// Executes everything before the while loop.
void doForLoopBody() {
if (isThisIterationOfForDone()) {
state = "END";
return;
}
// update colors, get values of key and j initialized, etc
// switch to processing the body of the while loop
state = "whileLoop";
}
Upvotes: 0