Author Topic: How to Solve this with Recursive Bubble Sort Algorithm?  (Read 8248 times)

0 Members and 1 Guest are viewing this topic.

Offline brucehoult

  • Super Contributor
  • ***
  • Posts: 6464
  • Country: nz
Re: How to Solve this with Recursive Bubble Sort Algorithm?
« Reply #25 on: October 06, 2020, 05:12:51 am »
When you deal with iterative algorithms, you can (I should say SHOULD) use invariants to both help implementing them and prove the implementation is correct.

Absolutely.

Precondition, postcondition, and loop invariant (which reduces to the precondition and the postcondition at the start and at the finish).

If your loop is simple enough that you don't need to think about and preferably write down in at least a comment if not an assertion then it's a rather trivial loop and really doesn't matter how you write it (and probably expressible with a simple "each" or "forall" or whatever your language provides).

Much of modern programming, of course, involves hiding all non-trivial loops from the programmer, by burying them inside a standard data structure or standard algorithm in the language's library.
 

Offline Nominal Animal

  • Super Contributor
  • ***
  • Posts: 8353
  • Country: fi
    • My home page and email address
Re: How to Solve this with Recursive Bubble Sort Algorithm?
« Reply #26 on: October 06, 2020, 06:26:25 pm »
I personally would prefer the second lesson on recursion (examining the exercises like the OP is asking about) to concentrate on the possible errors, like one-off errors and infinite recursion.
This shows the learners that while there is more than one way to implement something, there are vastly more ways to do it wrong.

Then, later on, when the learner has sufficient practical experience to understand the theoretical underpinnings, they'll both have something to anchor theory on, but also understand that the theory is inherently useful: one does not need to know all the ways things can go wrong, or each of the ways to do it right, if they have tools to prove the solution right/wrong.  It's not theory for the sake of knowing the theory, it is a set of meta-tools for development.

I always like to rely on (my) inherent laziness.  True laziness is when the overall workload is minimized; not when necessary work is postponed or pushed to others, minimizing just the immediate workload.  The latter is just being short-sighted, shitty dev.  (Yes, even if your employer demands you do that.  They are then deliberately paying you to be a shitty dev.  It's a very common and perfectly valid occupation, but produces shit products.  Which often sell well, given big enough marketing budgets.)

In this thread, as so often happens in this sub-forum, we've delved deep into the theory and details, without showing the OP or others how it is related to the question at hand.
 


Share me

Digg  Facebook  SlashDot  Delicious  Technorati  Twitter  Google  Yahoo
Smf

 

- - -
-->