Jump to content
Sign in to follow this  

Classic video on sorting

Recommended Posts

When I took data structures 1 I had to program in Pascal (on a NeXT) and watch this movie.

With the power of youtube, I can share it with everyone.  It turns out that these techniques are quite helpful.  The timeout driver and rtcounter driver in MCC Foundation services uses the insertion sort to keep a sorted list of timeouts advancing into the future.  This is key to the driver using a single HW timer to support any number of future timeouts.

Share this post

Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Sign in to follow this  


  • Popular Contributors

    Nobody has received reputation this week.

  • Similar Content

    • By Orunmila
      A colleague of mine recommended this little book to me sometime last year. I have been referring to it so often now that I think we should add this to our reading list for embedded software engineers.
      The book is called "Don't make me think", by Steve Krug.The one I linked below is the "Revisited" version, which is the updated version.

      This book explains the essense of good user interface design, but why would I recommend this to embedded software engineers? After all embedded devices seldom have rich graphical GUI's and this book seems to be about building websites?
      It turns out that all the principles that makes a website easy to read, that makes for an awesome website in other words, apply almost verbatim to writing readable/maintainable code! 
      You see code is written for humans to read and maintain, not for machines (machines prefer to read assembly or machine code in binary after all!). The principles explained in this book, when applied to your software will make it a pleasure to read, and effortless to maintain, because it will clearly communicate it's message without the unnecessary clutter and noise that we usually find in source code.
      You will learn that people who are maintaining and extending your code will not be reasoning as much as they will be satisficing (yes that is a real word !). This forms the basis of what Bob Martin calls "Viscosity" in your code. (read about it in his excellent paper entitled Design Principles and Design Patterns. The idea of Viscosity is that developers will satisfice when maintaining or extending the code, which results in the easiest way to do things being followed most often, so if the easiest thing is the correct thing the code will not rot over time, on the other hand if doing the "right" thing is hard people will bypass the design with ugly hacks and the code will become a tangled mess fairly quickly. But I digress, this book will help you understand the underlying reasons for this and a host of other problems.
      This also made me think of some excellent videos I keep on sending to people, this excellent talk by Chandler Carruth  which explains that, just like Krug explains in this little book, programmers do not actually read code, they scan it, which is why consistency of form is so important (coding standards). Also this great talk by Kevlin Henney which explains concepts like signal to noise ratio and other details about style in your code (including how to write code with formatting which is refactoring immune - hint you should not be using tabs - because of course only a moron would use tabs)
      Remember, your code is the user interface to your program for maintainers of the code who it was written for in the first place. Let's make sure they understand what the hell it is you were doing before they break your code!
      For the lazy - here is an Amazon share link to the book, click it, buy it right now!
    • By Orunmila
      I came across this one yet again today, so I wanted to record it here where people can find it and where I can point to it without looking up all the details in the standard over and over again.
      I know pointers are hard enough to grok as it is, but it seems that const-qualified pointers and pointers to const-qualified types confuses the hell out of everybody.
      Here is a bit of wisdom from the C standard. As they say - if all else fails read the manual!
      BTW. The same applies to all qualifiers so this counts for volatile as well. I see the mistake too often where people are trying to make a pointer which is being changed from an ISR e.g. and they will use something like:
      volatile List_t * ListHead; This usually does not have the intended meaning of course. The volatile qualifier applies to the List_t and not to the pointer. So this is in fact not a volatile pointer to a List_t. It is instead a non-volatile pointer to a "volatile List_t". In simple terms it is the variable at the address being pointed to which is volatile, not the address itself (the pointer). 
      To make the a volatile pointer, that is a pointer which is changed from another context such as an ISR, you need to do it like this:
      List_t * volatile ListHead; Of course if both the pointer and the thing it is pointing to are volatile we do it like this:
      volatile List_t * volatile ListHead;  
      There is another example in section 6.2.5 of the standard.
    • By Orunmila
      I have a fairly general question for you all. I keep on running into situations where I need to mix C and ASM. Sometimes this works out easily by just using some asm("") instructions in the middle of my function, but sometimes I really feel like I could benefit from writing a function in ASM and calling it from C.

      I think my best example of this is the implementation of cryptographic functions such as AES or SHA. For these I see sometimes a 2x or even 3x speed improvement over what the compiler produces and I need to use these from more than one place so I really need a C function I can call to do these but I reallly need to implement it in ASM.
      Whenever I ask about mixing C and ASM I am told just not to do it, but it still seems to me that there are a lot of situations where this really is the best way to go?
      I recall a converstation with @holdmybeer where he needed very precise timing and the optimizer would always change the timing depending how the banks ended up being laid out (adding or removing bank switches), where implementing a function in ASM also seemed to be the solution.

      So I would like to get some opinions on this, do you guys agree? Any thoughts on this?

      PS. We recently had a related discussion about calculating parity as another example.
    • By Orunmila
      This zip file contains the project implementing Duff's Device using XC8 and a PIC16F18875 which goes with the Duff's Device Blog. The project can be run entirely in the simulator in MPLAB-X so no need to have the device to play with the code!
      See the blog for more details
    • By Orunmila
      This file is the project which accompanies the blog post - A brief introduction to the pitfalls of Floating Point for programmers.
      This zip file contains a MPLAB-X project whcih is designed to run on a PIC16F18875, but is best used running in the simulator. The project should be configured for running on the simulator already. It was built using XC8 v2.05 and MPLAB-X v5.10.
      See the blog for more details
    • By Orunmila
      We found that we have quite a lot to say about programming embedded systems and this lounge is not quite flexible enough for us to do this, so we decided to start a community blog area.
      We have posted the first blog post as a test here  https://www.microforum.cc/blogs/entry/1-floating-point-numbers/ and the landing page for the blog collection is here https://www.microforum.cc/blogs/blog/1-what-every-embedded-programmer-should-know-about/. We are calling this one "What every embedded programmer should know about ..." and it will feature a series of posts along this topic.
      If there is any topic close to your heart that you would like us to cover please leave a comment and we will see if we can make it happen. As a start we will allow moderators to create and post blogs, if you want to make a contribution please contact one of the moderators and we should be able to hook you up.
      We have been toying with the idea to allow members to blog once they reach a certain level in the community, but since we are just starting out that will not be practical right now, let us know what you think, we may "upgrade" the system like that sometimg in the future!
    • By N9WXU
      My 7 year old wants to be an engineer.  She loves robots and programming. Just the other day, she asked how she "could be an engineer because I don't know everything".  So for Christmas I gave her one of these:

      This was just perfect.  It displaced one doll on her bed.  It can be driven around with an IR remote control, but it can also record your button presses (i.e. be programmed) and then play them back.  This sort of programming is just her speed.
      Here is a picture of Veronica studying her new programming book with the robot looking on.

  • Create New...