Efficient Software (by alaric)
Efficiency is a major goal for programmers. It used to be a much bigger goal; once upon a time, it was a struggle to fit useful applications into machines with 1MHz clocks, which took several clock cycles to perform basic operations on 16-bit values. You had to optimise even quite basic algorithms to get them to complete in acceptable timeframes.
In the 1980s and 1990s, the available computing power and memory for running an application exploded, but the sizes of data sets people wanted to work with grew in step. Now people wanted to word process documents with large images. Or keep databases of EVERYTHING. So efficiency was still a big concern for application programmers. But the focus began to shift.
When you're programming a computer to perform some task - let's take the standard example, sorting a list of numbers into order - there's two common measures of how efficiently you do it.
The obvious one is just "how many seconds does it take to sort the kind of size of list I expect to have to deal with".
But a more interesting one is "is the time taken to sort N numbers roughly some constant times N, or some constant times N squared, or some constant to the power of N, or what?".
If you're sorting lists that will usually just be from one to ten numbers, then the quickest way of sorting them will probably be the Bubble sort. This just means running through the list looking at each element in turn, and whenever you see a number that's more than the one in front of it, swapping them around. Keep doing this until the whole list is sorted. The biggest element in the list will, until it reaches the front of the list, always be bigger than the one in front of it, so will always be swapped - and, as such, will "bubble" to the front.
However, on average, the time taken to sort a list of numbers this way is proportional to the square of the size of the list. The act of looking at each element in the list (and swapping if necessary) always takes about the same amount of time. You need to do it to every list element in each pass, so each pass takes N times that long. And on average you'll need to do about half as many passes as there are elements in the list until they're all in place, so the whole sort will take about one half N squared times the time it takes to examine each element. The "one half" and "the time it takes to examine each element" are just constants, so can be multiplied together to make "some constant", so we can say that a bubble sort takes about "some constant times N squared" seconds to sort N numbers.
There's another algorithm, which I won't describe in detail here, called Quicksort. Quicksort is colloquially referred to as being a "faster" sort than Bubble Sort, although that's not strictly accurate. To sort N numbers, Quicksort takes some constant times N times log N seconds. N log N is clearly less than N squared, since log N is always less than N. So Quicksort is faster, right? Well, in practice, the constant for Bubble Sort is smaller than for Quicksort, so for small lists of numbers (or for lists with only a few elements out of place, which won't take many passes of Bubble Sort to finish off), Bubble Sort does actually win.
Fri 20th Apr 2007 10:24 pm 
Subscribe
By woolstar, Thu 26th Apr 2007 @ 6:38 am
What I love is that shell sort beats quicksort every time, and its easy, and nobody can tell you precisely how it works. It just does. It doesn't always beat quicksort, but its consistent. Lovely thing.
Btw, the people who care about performance, now live in the land of the mobile phone. Year 2007: cpu 100mgz, memory 8mbs. Wow, seems like I was here before.