This is something I’ve been working on for the past week or so (along with many other things). It’s basically just visual sorting, with the bars and stuff.
You can change the array that gets sorted by manually changing each number in each index, or you can randomize it all. You can also choose different sorting algorithms. Currently, only bubble sort and insertion sort are available.
I did try to add bogo sort but it was pretty wonky and I had no way to check if it actually works (other than waiting 70 years) so I just cut it, but maybe I’ll add it in the future.
Controls:
A: Add selected number to array at specific slot/index
B: Switch screens
Up: Increase selected number
Down: Decrease selected number
Right: Cycle between selected sorting algorithm
Left: Cycle between randomization
I did try doing that but the millis() function returns an unsigned long so each time it just ended up showing a zero since the number got rounded down.
I did also try lowering the frame rate (to one) so each individual bar could be seen while being swapped, but I got the same results.
It would probably be more of a visualiser if you spread the sorting action over a number of frames, e.g. one frame per one iteration of the sorting algorithm.
At the moment the only thing you’re visualising is an unsorted array followed by a sorted array, which means you get the same visual effect regardless of which sorting method is actually being used.
What code were you using?
Unless the sorting is happening in a time span that’s less than one millisecond (which admittedly is possible) then you should be able to get a value for elapsed time.
(Come to think of it, I don’t know if the ATmega32u4 has some kind of built-in cycle counter or not. If it did, you could count cycles instead of milliseconds, which definitely would increment even if the sorting algorithm was happening in less than a millisecond.)
Lowering the frame rate won’t help there because you’re not actually updating the frame at all during the sorting. All the sorting is happening at once, within the same function and thus within the same frame.
Also, interestingly enough, when I was experimenting with bogo sort, you could actually see each individual bar being swapped. Perhaps the other sorting algorithms are just too fast?
Based on the code you’ve produced, I think you’ll find that’s (at least in part) because counter is a local variable.
Although since you’re not actually initialising counter or hasSorted, both if(!hasSorted) and ++counter are actually undefined behaviour.
In practice, (because of how these abstract language constructs will be realised by machine code instructions,) what value counter and hasSorted actually hold will vary depending on runtime behaviour. There’s actually a slim chance they might somehow be retaining their values and thus giving the illusion of behaving as if they were global variables. (I’ve seen that sort of thing happen before. Only once before, but it was in an Arduboy program.)
If that’s true, it must have been implemented in a very different way to how you’re implementing bubbleSort and insertionSort.
No, it’s definitely because the entire algorithm is running all at once in a single function.
Remember, when a function is called, the CPU jumps to that function and runs the whole thing, line by line. It doesn’t fork it off into another thread and run it asynchronously.
You have an unsorted array, you hand it to the sort function, the function runs, and by the point the function ends, your array is sorted. At no point between the start and the end of the sorting function is the frame buffer or the screen updated.
While I’m at it, I notice that your sorting functions only ever return true.
It’s as if you were on the right track to making them only perform a partial sort and reporting whether they’d actually completed, but somewhere along the line you forgot about trying to do that and ended up making them just do a complete sort.
It used the same fundamentals and the same sort of template, just with different stuff under the loops.
Ah, right.
I just tried putting some display logic inside the sorting functions (I know, bad idea) and now it just shows one extra random frame. Maybe it’s too fast for the display.
But wouldn’t the loops halt the rest of the code until they’re finished iterating over the array? Or is that just while loops?
Without knowing what you wrote or what visuals it produced I can only make wild guesses.
Theoretically it should work, though there is a better way.
I’m not sure whether to put you out of your misery or let you think it over for a while to see if you can figure out how to get your code to do one sorting step per frame.
(Bear in mind that having the sort run as fast as it possibly can and displaying the in-between steps are mutually exclusive goals, because with such small arrays prettty much any half-decent sorting algorithm should run quicker than your eye could perceive.)
If I were to hazard a guess, I would presume that would be the last frame before the array is fully sorted.
If you’re calling arduboy.display() from inside the loop(s) then it’s more likely that it’s too fast for your eyes to perceive.
If you’re not calling arduboy.display() from inside the loop(s) then it’s more likely that you’re only actually displaying the last or second-to-last frame of the sorting process.
Yes.
Though I don’t quite see what that would have to do with the functions currently only returning true.
My point was that they never return false because returning false would indicate that they haven’t finished sorting, and not returning false is in fact accurate because they always finish sorting - i.e. they never stop part way through.
Hence either the return value is entirely redundant or they aren’t behaving the way you originally intended them to (e.g. performing a partial sort instead of a full sort).
A for loop is equivalent to a while loop with a pre-loop initialisation statement and an extra iteration statement within the body of the while loop.
I just tried putting arduboy.display() and arduboy.clear() within the two loops (both at the end and the top, respectively) and now the display flickers a lot and the screen gets rendered really slowly and in small chunks. I also tried using arduboy.nextFrame() (same thing in the loop function) but it just stopped the sorting entirely. Here’s one thing I tried (so you get my thinking process):
I originally made it like that so I could get the exact time it finished (for like running stuff only after it’s complete) but now that I think about it, the function would have to finish before the rest of the code could run anyway.
for(uint8_t i = 0; i < arraySize; ++i) {
for(uint8_t j = i + 1; j < arraySize; ++j) {
while (!Arduboy2::nextFrame()) { delay(1); // Wait until next frame ..
Arduboy2::fillRect(4, 4, 120, 56, BLACK); // Adjust to clear the bard area only.
if(array[j] < array[i]) {
uint8_t temp = array[i];
array[i] = array[j];
array[j] = temp;
}
drawBars();
Arduboy2::display();
}
}
I think you probably need to wait for the next frame within the loop and you will need to move your drawBars() function into the class itself. The fillRect() immediately after the nextFrame() check will also need to be adjusted so that it clears only the ‘graph’ area.
It likely would do, you just uncapped the framerate limit.
(arduboy.nextFrame() is what limits the framerate, when used properly.)
The first clear is redundant, as is the first call to display.
You also don’t appear to actually be drawing the bars at all.
clear clears the frame buffer. display copies the frame buffer to the screen.
That’s what I’ve been trying to point out.
I think if I leave you guessing you’re going to be at this for a while, so I’ll help you along some more…
Rather than trying to cram clearing and displaying code into the sorting function (which is poor separation of concerns), what you ideally need to do is to instead create a function that runs a single step of the sort function rather than doing the whole sort at once.
That means you’ll inevitably have to have some state, but it’ll make the separation cleaner and you won’t have to worry about messing up the frame rate or calling clear or display.
Here’s a hint in the right direction:
class BubbleSorter
{
private:
uint8_t * array;
size_t arraySize;
uint8_t i;
uint8_t j;
public:
void reset(uint8_t * array, size_t arraySize)
{
this->array = array;
this->arraySize = arraySize;
this->i = 0;
this->j = 0;
}
bool isComplete()
{
// Return true when the sort function has finished
// and false if it's still running.
}
void runOneStep()
{
// Perform a single step of the sort function
}
// When the other functions are implemented correctly
// this function should behave like your current 'bubbleSort' function,
// i.e. it performs a full sort, uninterrupted.
void run()
{
while(!this->isComplete())
this->runOneStep();
}
};
Not that it wouldn’t work, but it’d probably get a bit awkward after a while, particularly when trying to add extra features like being able to cancel the sort part way through. (You can just return, but then you’ve added button handling too, which means you’d need to call pollButtons, and by that point you’re basically recreating the loop function.) Come to think of it, after a few functions it wouldn’t be very DRY either - inserting the same few lines into every single sort function.
In a desktop environment the class-based approach would be a good candidate for turning into a child class of some pure functional Sorter class, which would make it more easily extensible. Unfortunately in Arduboy-land that would be a waste of progmem.
(Theoretically the nicest/simplest solution would actually be to use coroutines, but C++ only introduced coroutines in C++20 and they’re a little bit “batteries not included” from what I’ve read.)
