Sorting – More Depth! (and Big-O)

I’m going to get to the point. I’m writing this so you don’t have to spend a whole lot of time scouring the ‘net in search of a solution to your homework assignment.

In later years (2nd, 3rd, 4th) professors get heavy on the subject of efficiency and really analyze algorithms (thus, courses aptly named algorithm analysis). This is where “Big-O” notation comes in to play.

If you’re anything like me, that didn’t make too much sense at the start. Even now I can’t think of when I might actually compare the runtime of an algorithm to the graph created from n2 or n log n. However, what algorithm analysis has given me is the understanding that programs that take a really long time to run can usually be improved upon. And if there’s an algorithm that takes a long time to run that hasn’t yet been improved upon then there is often a prize for the person who can improve upon it (or who gets lucky).

With that being said, let’s look at those three sorting algorithms again.

Bubble Sort is said to have a runtime of O(n2) at worst. What does that mean to you? Well, it means that this sorting algorithm sucks for every day use. But we’re human, and that means we can learn from this mistake. Don’t use bubble sort, but maybe give your professor a hard time about it. Squeeze it into another program somewhere, as a joke. No, don’t listen to me.

Insertion Sort is another example of a sorting algorithm with a worst-case runtime of O(n2). Though it has the same runtime complexity as Bubble Sort, don’t be fooled into thinking that Insertion Sort is always just as slow. Insertion Sort is still worlds more efficient at sorting than Bubble Sort.

See that!? Insertion Sort takes care of 150,000 unsorted values in 1/5 the time it took Bubble Sort to sort the same values. But there is still a quicker way to sort…

Quick Sort is the last algorithm in the scope of this article. The algorithm is just that, it’s quick. Quick Sort has an average runtime complexity of O(n log n) which is a huuuge improvement over Insertion and Bubble Sort.

And in case you are curious, this is what n2 looks like when graphed.

And what n log n looks like when graphed.

And when the two are compared you can see a massive difference:

If you feel so inclined to play around with sorting algorithms, the source code for my sorting demo can be found here or on the files page.

Lotto, detailed.

The lotto page has been updated. The focus has been maintained; the point was to examine the common Lotto 6-49.

Taking for example a hypothetical Lotto 4-15, we select 4 numbers of our choosing from the available numbers ranging between 1 and 15. The 4 you pick are matched against another 4 random numbers drawn from the same range of numbers, 1 through 15, at a later date. You all know how a lottery works.

The point being, you want your 4 numbers to match the 4 numbers later drawn at random. But what are your chances of winning with 4 numbers picked from a pool of 15? Google says 15 choose 4 equals 1365. What’s that 15 choose 4 thing? It’s a binomial coefficient (n choose k), but I won’t get into too much detail about that here. Suffice it to say, it calculates the number of combinations to be made when choosing k numbers from a pool of size n.

So with 4 numbers from a total 15 you have a 1 in 1365 chance of having your 4 numbers picked again.

We can simulate that. The source code is right here. It’s the lotto sim. I set it to pick 4 numbers of it’s choosing from 15 and hold on to them. I also told it to simulate and record stats for 1000 wins.

So the sim chooses the 4 numbers it’s going to play then it picks 4 more, like a lotto-drawing would. If it matches, it’s happy and stops playing. If it doesn’t match then it plays the 4 numbers it originally chose against a new drawing of 4 (think of it like next week’s drawing). It keeps going until it finds a match and when it does it stops and records the number of games played until it won. Then it picks another 4 and plays until it wins… (based on number of wins you told it to play to).

Here’s a spiffy graph showing the Lotto 4-15 with statistics for 1000 wins.

1000 wins gives us an “ok” real-world result for the lotto 4-15. We see that the average starts to converge on the odds of winning this type of lottery. Remember 15 choose 4 gave us the value 1365 and the results here are showing a value of 1380.69 which is reasonable.

Click the Science tab at the top of this page and then the Lotto section. Visit the science page in the wiki. There you can find more information along with results for the common Lotto 6-49.

Staypressed theme by Themocracy