klugness

Quicksort—Conceptual Framework

Quicksort is a type of "divide and conquer" algorithm where a "pivot" item is selected (usually the last item in the list) and then moved to somewhere in the middle of the list. Then all the items that are less than the pivot item are placed in the first portion of the list (i.e., before the pivot), while all of the items that are greater than that item are placed in the second portion of the list (i.e., after the pivot). Once the first pivot run-through is complete, each half of the list is not in order yet—and yes, Scarlet, admittedly that doesn't seem like much progress. However, all of the items have been mapped into the correct half, which is progress for a very large dataset. (Think of it like putting together a jigsaw puzzle of the states in the United States; it could actually be considered progress to divide the pieces into two groups: states east of the Mississippi and states west of the Mississippi.) The algorithm then continues to subdivide each portion of the list and to perform the same type of pivot activity until the list is sorted.

Note the above description is somewhat casual and doesn't capture the complexities and variations on this algorithm. For example, I used the word "half" as if to imply that the algorithm automatically divides the list into halves, but that's not precisely what happens. In fact, a poor choice of pivot can actually make it so that one subdivision is much smaller than the other, which negatively affects the performance of the algorithm. In addition, as you might imagine, keeping track of all the subdivisions is a bean-counting exercise on steroids, which definitely puts the algorithm into the "complex" category.

While the casual description above is good enough for my purposes, readers interested in getting more details (and more precision/accuracy) in the description of the quicksort algorithm may want to review the Quicksort Wikipedia entry, which includes a detailed technical discussion of the approach and its variations as well as a couple of animated visual examples of the approach in action on small sample sets of data. I find it very helpful to see this type of dynamic visual portrayal of the algorithm in action.

Quicksort—Key Characteristics

Here are a few key characteristics of the quicksort algorithm:

• It's pretty efficient for large data sets that are badly jumbled
• It's pretty inefficient for lists that are already in order (or close to it)
• This typically occurs because picking the first element (which—for a list that's already in order—is the lowest value) or last element (i.e., the highest value, for a list that's already in order) as a pivot leads to subdivisions that are very lopsided (like one subdivision has nothing in it, and the other has everything, and that keeps happening over and over as the algorithm repeatedly subdivides each subdivision)
• In a sense, you're not really "dividing and conquering"—you're doing busy work and wasting time
• This disadvantage has led to variations that choose a different pivot element
• Quicksort struggles with lists that have the same item repeated many times. There are variations that help overcome this disadvantage as well
• Some variations use a different algorithm once the subdivisions are small (say, 10 items or less) because the power of "divide and conquer" is most apparent when applied to large data sets

We'll come back to some of these characteristics when we get on our soapbox about real-life problem-solving. But first we turn our attention to one of the simplest sort algorithms: the bubble sort.

Bubble Sort—Conceptual Framework

The bubble sort is a simple algorithm that involves looking through the entire list in adjacent pairs (i.e., items 1 and 2, then items 2 and 3, and so on to the end of the list) and interchanging (or "swapping") the adjacent items if they're out of order. If the adjacent pairs are in order, the algorithm takes no action and simply moves on to the next adjacent pair. The process repeats until there's a pass through the list that involves no swaps—the absence of swaps means that no items are out of order, so the list is sorted and the process is complete. "Voila!"—to borrow a neat word from the French.

The algorithm is called the "bubble sort" because the items that belong at the top of the list gradually "bubble up" to the top. Sometimes the algorithm is called the "sinking sort" because the items that belong at the bottom of the list gradually sink down to the bottom. We'll illustrate the bubble sort using the following sample dataset:

Obviously this sample set could be sorted into numeric order by a third grader in no time at all. My goal is not to sort this ridiculously easy list of items, but to illustrate the bubble sort approach so readers have a solid understanding of how the approach works.

When tasked with sorting the above list of values from lowest to highest, the bubble sort algorithm would take the following actions, as illustrated in the table that follows this list of numbered actions:

1. Since item 1 is greater than item 2 (i.e., 3 is greater than 1), these two items are out of order and should be swapped. Thus, item 1 takes on the value of 1 (which was formerly the value of item 2), and item 2 takes on the value of 3 (which was formerly the value of item 1). These new values are reflected in the list (see "After Action 1" in the table below), and then we move to the next adjacent pair.
2. Since items 2 and 3 are in the right order (i.e. 3 is less than 4), do nothing.
3. Since items 3 and 4 are in the right order (i.e., 4 is less than 5), do nothing.
4. Since item 4 is greater than item 5 (i.e., 5 is greater than 2), swap the items. Item 4 becomes 2 and item 5 becomes 5 (see "After Action 4").

The table below shows the list after completing the first pass through the data (Actions 1 through 4).

Bubble Sort—Programming Nuances

This image of "computer server room" was created by Klugmeister using artificial intelligence software. The image was reviewed by Klugmeister before posting on this web page.

After the first pass through the data, the bubble sort algorithm is guaranteed to move the item that belongs in the last position to that spot—note the largest value (5) is now in item 5. The list must generally be passed through several times before the entire list is in the right order (generally up to n - 1 times for a list of n items). However, for efficiency reasons the bubble sort algorithm is often programmed so that you check after each pass through the data to see whether any swaps occurred, because if none did, that means you're done and can halt the algorithm, even if you haven't completed n - 1 passes.

Our sample list, for example, is guaranteed to be sorted after 5 - 1 = 4 passes through the list, but as it happens the list will actually be in the correct order after only three passes. (No swaps occur on the fourth pass because no items are out of order.) However, note that the programming for the animated illustration of the bubble sort (see further below) does not reflect a test on each pass to track whether any swaps occurred, so the animated bubble sort visualization completes all four passes through the sample list, consistent with the n - 1 rule provided in this paragraph. The programming to flag whether one or more swaps occurred on each pass (and if so, stop running the program) isn't all that difficult to implement, but it does introduce some extra complexity, and I tend to "choose my battles" when it comes to introducing additional complexity.

We noted above that the item that belongs in the last position will be there after the first pass. Extrapolating, the item that belongs in the second to last position will be there after the second pass, and so on. Thus, it's unnecessary to look through all n items on every pass, because a certain number of items are guaranteed to be in place on each pass after the first one. As a result, the bubble sort algorithm is typically programmed so that it doesn't process (i.e., do any comparisons or swaps) related to the items that are guaranteed to be in place.

If we designate the pass number through the list as passNum, for example, you would look through n - passNum + 1 items on each pass through the data. In our case, you'd look through all five items on the first pass, just the first four items on the second pass, just the first three items on the third pass, and just the first two items on the fourth pass. The fourth pass is the last pass because the algorithm is guaranteed complete after n - 1 passes (5 - 1 = 4th pass).

Essentially, this programming logic brings some efficiency compared to looking through all n items on each pass, because there's no need to look at items that are already in the correct spot. This isn't a big time saver for a small list, but makes a difference for a large list. The bubble sort animation shown below reflects this more efficient programming logic—note for example that on the fourth pass the program only compares the first two items, since the last three are guaranteed to be in position after the third pass.

Confused? The animated illustration of the bubble sort in the next section may help bring these concepts to life.

Bubble Sort—Animated Visualization

Bubble Sort—Key Characteristics

Here are a few key characteristics of the bubble sort algorithm:

• It's inefficient for large data sets that are badly jumbled
• It's extremely efficient for lists that are already in order (or close to it)
• If a list is in order, the bubble sort will do its usual comparisons of adjacent items on the first pass, will observe that there were no swaps, and declare the list sorted without doing any swaps or any additional passes
• Swaps are generally more of a "heavy lift" than comparisons, so sorting data without any swaps is very efficient!
• The worst case scenario is a list that is in backwards order. In this case the algorithm would complete all n - 1 passes and do zillions of swaps to get the list in order.
• Because of its inefficiency for most large data sets, the bubble sort is rarely used in practice, but is often covered in introductory programming classes due to the relatively small amount of code needed to implement it.

Now that I've provided an overview of these two sorting algorithms, let's get to a head-to-head comparison of the approaches.

Quicksort Algorithm vs. Bubble Sort Algorithm

If you were given the assignment to sort a dataset of unknown composition and size, which approach(es) would you choose?

A side-by-side comparison of characteristics of these approaches may be helpful in making a decision. The information in the table below already appears in the above two bullet point lists of characteristics of the quicksort and bubble sort algorithms, but putting these traits side-by-side helps make it obvious that the characteristics of these algorithms are in some ways opposites of each other:

Obviously, if you think there's a decent chance that the dataset might be large and badly jumbled, the quicksort approach would be the way to go. Bubble sort would generally only be appropriate if (1) the list is small, or (2) the list is not small, but is already close to being in order. This might be the case if, for example, a company keeps its customer list in alphabetic order by customer name, except for the relatively small number of new customers that get added each day. It could be reasonable to use bubble sort once per day if there are, say, 1,000 customers in the database, plus around 10 new ones that are out of order.

I noted previously that the bubble sort algorithm is rarely used in practice because of the limited situations where it's efficient/useful. The "fame" of bubble sort comes from the fact that it's a fairly simple algorithm that doesn't require a lot of code, so it's frequently covered in introductory computer programming classes.

Quicksort's Nightmare Scenario

This image of "an office worker wearing a T shirt that says 'quicksort' chained to his or her desk on Friday afternoon at 5:00" was created by Klugmeister using artificial intelligence software. The image was reviewed by Klugmeister before posting on this web page.

I like the strategy of trying to anticipate situations where a given approach would either work well or not so well. For example, let's suppose that—without any serious forethought— you make the decision to use the strong and powerful quicksort algorithm for the mystery problem. (And why wouldn't you? You've heard the bubble sort algorithm is weak and slow.) Further, let's assume that your Introductory Computer Programming professor (who has a mean streak) assigns you a list that is large and (for his own dastardly reasons) already completely in order.

Large isn't a problem for the complex and powerful quicksort, but quicksort is inefficient for data sets that are already in order because the algorithm ends up doing lots of counterproductive work (such as taking items that are in order and moving them elsewhere). Depending on how it's programmed, for example, the quicksort algorithm will generally take an item that's already in order (say, the last item, which is already in the correct position) and move it to somewhere in the middle of the list, where it becomes a pivot element. Now...you don't need to be a computer science professional to realize that taking an item that's in order and moving it to a spot that's out of order is counterproductive.

Quicksort's struggles with a dataset that's in order are in stark contrast to the bubble sort, which performs extremely well for a list that's already in order (even if it's a large list). Why, you ask? Because the bubble sort algorithm will simply look through the list once, confirm that no swaps occurred, and declare the list sorted without doing any heavy lifting in the form of swaps or multiple passes through the data.

Isn't it interesting that the simple bubble sort works very well on a very specific (and admittedly rather contrived) situation that's a challenge for the more complex and powerful quicksort? Well, perhaps it's not interesting to everyone, but "20s Klugmeister" thought it was interesting enough to wait over 40 years, then write a blog post about it as "60s Klugmeister" (40ish years later)! It's as funny as watching a quiz show competition between Forrest Gump and a very smart person, initially thinking that Gump has no chance, and then seeing that the mystery question is "Who has to pee?" Ha!

This image of "two people relaxing on a beach while sipping light amber colored beers out of bottles" was created by Klugmeister using artificial intelligence software. The image was reviewed by Klugmeister before posting on this web page.

The whole situation reminds me of when my sister had a job in the publishing industry many years ago. Her then employer provided the employees a perk known as "summer hours." For those unfamiliar with this concept, you work an extra hour or so the first four days of the week, and then you may leave work at noon on Friday.

I recall this being a sticking point with me at the time, as my sister was always emailing me early on Friday afternoons during the summer, letting me know that she was at the beach, while I had to work a regular day. Hmmm, why couldn't I be at the beach? In this made-up scenario, I am the quicksort algorithm, which is burning up a lot of computing power working hard all day Friday to sort a list that's already in order, while my sister is bubble sort, who got to go home early on Friday because she got all her work done.

Isn't it better to work smart than to work hard? In fact, perhaps we could personify the algorithms as me and my sister: quicksort is heating up the computer room by doing a lot of unnecessary work, while bubble sort is at the beach sipping Coronas with Snoop Dog. (My sister doesn't drink Coronas or know Snoop Dog, but either way it's a funny image). Must be nice, huh?

Bubble Sort's Nightmare Scenario

This image of "an evil computer science professor" was created by Klugmeister using artificial intelligence software. The image was reviewed by Klugmeister before posting on this web page.

We could even think about the choice of algorithm from the point of view of the computer science professor. Let's say you're the evil professor who has an axe to grind with one of the students—perhaps because he or she insists on calling you Mr. or Ms. Frankenstein instead of Dr. Frankenstein. If you had an inkling that this student was going to use the bubble sort algorithm, and the assignment was going to be graded on how efficiently the chosen algorithm handles the dataset you provide, you could fulfill your evil destiny by picking a dataset that's in backwards order.

Why? Because unlike the dream scenario of a list that's in order, a list that's in backwards order is a nightmare scenario for the bubble sort due to the maximal number of passes it makes through the data and the large number of swaps that must take place. The bubble sort is already inefficient for large datasets, and putting the list in backward order is cruel and unusual punishment because it's the worst possible order from the bubble sort algorithm's perspective.

In this case, the situation is the reverse of the previous scenario; i.e., this time the bubble sort is chained to its desk on Friday afternoon while quicksort gets its work done early enough to do some frolicking with bikini girls. (Actually, the quicksort algorithm isn't efficient either for a list that's in backwards order, so maybe I should have included a different choice of complex sorting algorithm? Whatever!) Note that the performance of each algorithm depends heavily on the characteristics of the dataset, so it's dicey to conclude that a certain algorithm is always the preferred approach.

These examples highlight the importance of trying to anticipate the exact nature of the problem rather than picking an approach with no thought to the specifics of the problem. It may be a challenge to put the person on a hand or guess the play the opposing football coach is going to call, but you have to be thoughtful and give it a try. And you may have more information than you think. Don't be the person who says "How could I possibly know what play the other coach is going to call?"

1. Don't Count Out Simple Approaches

A simple approach may be the best solution to the problem at hand, depending on the circumstances. If instead you always use a more complicated approach, you may be wasting time and resources and not getting a better outcome. We saw above how there are some specific situations where the simple bubble sort works better than more powerful and complex sorting algorithms. Perhaps slow and steady sometimes does win the race?

One real-life area where a simple approach may be appropriate is retirement planning, which involves preparing projections of future retirement assets based on assumed savings rates and rates of return on investment. In these situations, it's common practice to project future 401(k) and Individual Retirement Account (IRA) account balances assuming a rate of return that is the same percentage (such as 6%) for each and every year. This approach is so common that we don't often recognize it as a simplification, though of course retirement assets that are invested in the stock market are actually subject to returns that can and do vary significantly from year to year.

More complicated models exist to take into account this variability in returns, but it's generally considered acceptable to use a long-term "average" expected rate of return for this type of modeling, especially for an individual who is preparing long-term projections and simply wants an estimate of how much retirement assets he or she will accumulate by a desired target retirement age, such as age 65. Such an individual can compare the results to common rules of thumb (such as accumulating 7.5 to 13.5 times your annual pay by age 65) to see if he or she is "on track." An individual who is experienced with Excel spreadsheets could develop a simple spreadsheet for this purpose.

Such a spreadsheet might look like this:

Besides assuming a fixed rate of investment return, another simplification that I used for this sample projection is the assumption that contributions are made in the middle of the year. Of course, it would be more accurate to take into account the actual timing, which would normally depend on the situation. For example, for a participant in a 401(k) plan sponsored by the participant's employer, the timing could be weekly, biweekly, semi-monthly, etc., depending on the paycheck frequency of the employer. Even so, mid-year is often considered a reasonable approximation for situations where contributions are spread throughout the year. For example, it may not be appropriate to assume mid-year timing for an individual who receives a relatively large bonus early or late in the year (e.g., March 15). A more customized timing assumption may also be needed for an individual who makes contributions to an IRA, since the individual has discretion over the timing on contributions within certain constraints.

Note that just because you can do an exact calculation of the timing of contributions doesn't necessarily mean you should:

• Variations due to other more significant assumptions (e.g., the assumed investment return) tend to overwhelm any precision in the timing assumption, so a rigorous calculation of timing of contributions may be more hassle than it's worth. It doesn't make sense to fit a bikini on a mosquito if an elephant is liable to sit on it.
• The other unfortunate truth is that building high precision or complexity into every aspect of a model can make it difficult to program and test. This increases the risk of introducing errors that aren't caught before the model goes live. When building financial models, it can help to be judicious and "pick your battles" in determining when to introduce complexity.

2. Customize the Approach

In past discussions of problem solving I've focused on picking an algorithm that would work well (or not so well) for a particular set of circumstances. In this case, however, I'm thinking more along the lines of whether the inputs to the retirement projection model work well or not, rather than trying to pick the best approach from multiple models or algorithms.

For example, various vendors offer retirement projection models with assumed rates of returns that are often in a range of about 6-7%. These models are often based on an assumed investment portfolio of 60% stocks and 40% bonds, or a similar investment mix with a significant allocation to stocks. However, for an individual who invests very conservatively for retirement (such as in a stable value fund), a 6-7% return assumption would generally not be appropriate because ultra conservative investments are unlikely to earn that high of a return. If using a spreadsheet for retirement modeling, this individual with a conservative allocation could conceivably input a lower assumed investment return more in keeping with an ultra conservative asset allocation. That individual should be cautioned against using one of the standard retirement modelers since the investment return that's cooked into the model is higher than can reasonably be achieved using a very conservative investment mix.

Models may also need to be adjusted over time to reflect current economic conditions. For example, a model from 40 years ago (when interest rates were quite high) would likely have been based on an assumed investment return significantly higher than 6-7%. The key factor affecting this is that the expected return on bond (i.e., fixed income) investments back then was high because of the high level of interest rates during the 1980s. Those high return assumptions would not be appropriate in the current economic environment because yields and expected returns on bonds are much lower now. If you find a 1980s retirement modeler in a space capsule, run away!

Another area of customization is the time period to retirement. Consistent with our previous example, an individual age 45 who plans to retire at 65 would likely feel comfortable projecting balances for 20 years at 6-7%, since variations in stock market returns during the period (high and low) would tend to balance each other out over market cycles that occur during a 20 year period. On the other hand, a person who invests in stocks and plans to retire in three years would have a relatively low degree of certainty of achieving a 6-7% annual return during this relatively short three year period. There's a decent chance the return could be much lower or higher.

On the other hand, a person who invests in short-term brokered CDs (not a typical retirement mix, to be sure) for three years starting now might have a decent likelihood of achieving a 4% return and could potentially use a spreadsheet model with 4% return for three years with a higher degree of confidence.

It's important to consider the assumptions that are cooked into the model and whether they can reasonably be applied to your situation.

3. Apply a Stress Test

It is good practice to "kick the tires" on a financial model to see how the results may change if actual experience is better or worse than expected experience. This could involve running three scenarios (worse, expected, better) or potentially running a multidude of scenarios. The question "Have I saved enough to support my needs in retirement?" is important enough that it may justify running a full-blown retirement model like those used by financial planners. These may involve software that runs multiple scenarios and keeps track of a count of how many scenarios are successful or problematic. The scenarios can be grouped into percentiles that help quantify the likelihood that the portfolio will be adequate to support the retiree's income needs during retirement until an assumed age at death. Note this type of multi-scenario stress test goes beyond the "How much will I save by my target retirement age, and am I roughly on target?" question that our projection spreadsheet was designed to answer.

These more complex retirement models are often based on stochastic forecasts. A stochastic forecast incorporates randomness and probability into its predictions, rather than relying on a single, deterministic outcome, like asset returns of 6% per year. A stochastic projection helps quantify the variability of asset returns by taking many random samples from a probability distribution of investment returns. For example, rather than assume an asset return of 6% for every year, one scenario of returns might include annual asset returns such as:

The returns shown above aren't based on random samples—I made them up so that they vary and produce a compound average annual return of about 6% ([95% times 120% times 104.5%]^(1/3) - 1 = 6%). (Stock market returns tend to vary significantly from year to year in a similar way to this example.) In a stochastic forecast, the returns are based on random samples from a probability distribution of returns. A collection of annual returns for consecutive years in such a model is referred to as a "scenario." A stochastic projection might typically develop 1000 plausible scenarios of returns.

Once all the scenarios are developed, a stochastic model would then determine which of those scenarios are successful (where success means the individual didn't run out of money) or unsuccessful (the individual did run out of money). If, for example, 90% of the 1000 scenarios are successful, that would generally be a result that indicates the individual has a good chance of experiencing retirement success (and a low chance of failure). When financial planners develop a retirement readiness "score" on a scale to 100, it's often based on a percentile that represents the estimated likelihood that the retirement portfolio supports your retirement income needs for as long as you (and potentially your spouse) are alive.

Besides the term "stochastic forecast," this type of scenario testing is sometimes referred to as a "Monte Carlo Simulation."

Stochastic forecasts are complex models, so it may be a challenge to gain access to this type of model without the assistance of a retirement planning professional. Even so, you may be able to apply a simpler (but still useful) stress test by tweaking a deterministic model. You'll recall that our spreadsheet projection of retirement account balance showed estimated accumulated retirement assets of $1.2 million at age 65 for an individual currently age 45 with $250,000 of retirement assets. To test how significant the 6% assumed rate of return is, we can stress test that projection by running it with alternative rates of 5% and 7%:

Other ways of stress-testing a retirement portfolio are to adjust the length of retirement. For example, you might lengthen the period of retirement to take into account a longer lifetime than expected, and then check to see if your score is still adequate. Many planning tools already assume a retirement period that lasts into the person's 90s, rather than a probability distribution of future lifetimes. In that case, the assumption is already conservative and there may be no need to run a stress test where the person is assumed to live longer. A model may or may not allow you to adjust the assumed ending age.

One of the outcomes of planning around a high likelihood of success is that the individual may then also have a high likelihood of having significant amount of unspent money at the end of the individual's lifetime.