Re:Sort an array using only one local variable
by userbinator on Saturday April 23, 2016 @12:13PM
(#11556123)
That's the essence of a goto-based state machine (one of the few problems where gotos are the most natural solution), compared to the alternative of storing the state in a variable and doing an extra indirection every transition to "go to" the right one.
Re:Sort an array using only one local variable
by kpil on Sunday April 24, 2016 @04:27AM
(#11558983)
I guess you can move an arbitrary amount of booleans (or enums) into the running state.
I suppose that the very idea of variables is just to separate the state from the code so that it's possible to handle complex states in generic code with a reasonable size...
On the other hand, a lot of bugs are related to that the resulting implicit state machine is not complete and/or correct...
The same question but including the program state is the interresting one. How much information/state is needed and needs to be shared, as it relates to how an algorithm scales.
If you have "local variable" with more bits than log(# elements to be sorted), then yes, this trick works, but with sufficient extra bits, you can pack multiple indexes into a single variable by shifting and 'or'ing.
An even sneakier way of hiding this extra bit is to use the program counter to store it:
If the program is running the "b" loop, some pair has been swapped, so when it finishes the loop, it knows to re-run the "a" loop. If the program completes the "a" loop, it knows no pair was swapped, and can finish.Edit: formatting