Hi, I’m just getting started in programming and have been working with Processing for a couple of months now, but haven’t found a solution to a rather advanced (for me) problem concerning solving and projecting an array being sorted. I’m not asking how sorting algorithms work, but more of how to organize them in terms of a global draw loop or something of the sort.
Here’s how I implemented bubble sort basically: I had a single draw() loop execute a single full loop of the bubble sort algorithm, not the full thing, just a single iteration. It would then draw the current look of the array in whatever way I wanted.
This worked fine, but only for bubble sort. And it seemed to be limited by the fact that if I wanted a different algorithm, I would need checks for what ‘stage’ of the algorithm I’m at, and if I wanted a different array, if I wanted to be able to ‘rewind’ or ‘pause’ I would encounter problems, making the whole process super difficult to maintain.
The only solution I can think of requires exponential amounts of RAM for everything I want to show changes for, or would be tedious to show changes for.
Is there a good way to organize this? I’m not sure how, and the only good idea I have is using an Object for storing everything and calling a tick() method of sort which would complete one loop of whatever it was on.
I kind of wish I was just able to do a draw tick while inside of a loop, being able to just call display(), sleep 0.01 seconds and then the loop continues, but unfortunately, no such thing.
I hope you guys understand what I’m talking about because everyone I’ve talked to shakes their head and says “I don’t know”.
This has been discussed before so you might read this discussion
Most sort algorithms have two key activities
Compare two elements in the collection to sort
Swap two elements in the collection if in the wrong order.
One possible solution is to remember the elements being compared / swapped in another data structure e.g. a list and then iterate forwards or backwards displaying the current state of the collection.
This is the solution I have used in the sketch shown in the linked discussion.
Definitely follow the chain of previous discussion links back from quark’s link – including to several places in the old forum.
Many / most sorting algorithms are not designed to be animated – certainly not to be reversable / rewound. If all you want is animation, then you can refactor the algorithm loop(s) to an object or set of global variables with draw “inside” it. If you need rewind as well as animation, however, sorting algorithms are NOT reversible – so a history data structure of the kind quark demonstrates is also necessary.
There is one workaround for not keeping history – although it is low performance. For deterministic sorting algorithms, you can simply pass the step number, and have it sort up to that step. So, at step 15, you could “step back” by rerunning the whole step from step 1-14. Then you don’t need a stack, you only need to save the initial non-sorted state. If the sorting algorithm involves randomness then this also requires that you save and reset from the randomSeed.