Searching & Sorting

Space Needle or Cloud City?

I recently realized that were some things you could do with the C library sort (qsort) & search (bsearch) functions that can make them more useful. bsearch will run a binary search on a sorted array and return a pointer to the matching element, if there is one. If it doesn't find a match, all it tells you is that it didn't find it.

But what if you want to find an element with a value close to the one you want? The trick I just figured out is you simply add the element you want to use as a target in your search, run qsort on the array to sort it, and then search for that element. That will put you in the ballpark. Now all you need to do is check adjacent elements to see if they meet your criteria.

To delete this fictitious element, simple change it's value to the maximum possible for this item and then run qsort again. It will now be at the top of the list. All it takes to effectively delete it is to reduce the array's element count by one.

All this extra sorting will use some processor power, and if you were having to sort a gigabyte of data more than once a second, it might have an effect on your system's overall performance.

But if this is for any kind of desktop application, the ease of coding it makes it a worthwhile shortcut.

The last time I went down this road I wrote my own search function that would return the element with the closest value to my requested target. I also wrote my own insert and delete routines. I did this because when I went to school everything about computer programming was about saving CPU cycles. Beginning programmers got seven seconds of execution time on the mainframe. I screwed up once in a junior level class and burned my entire semester's allotment before the OS kicked me off. That rated some words from my professor.

I wonder why it took me so long to figure this out. I'm thinking it might because most of the programming work I did involved making things work, and there was no end to it. Well, I guess it did come to an end which is why I am unemployed. Computer companies eventually got their acts together and started building machines that worked when you turned them on, and software companies started producing software that people could use to do something useful. Took a while but they eventually got it sorted.

So I never got to work on anything that might have been more interesting than the nuts and bolts of getting the hardware to behave. Not that it wasn't interesting, but it was interesting in a picayune kind of way, not a cosmic, universe expanding kind of way.

Modern desktop computers are roughly ten thousand times faster than the old CDC 6600.