Idiot World - What Sorting Teaches Us (Part II)

Idiot Activites:

Idiot Chat

Recent Comments:

Page not found?
on 5.12
by seele

Is there something wrong here?!?!
on What's a recent grad got to do
by garthon

very true
on The difference between =) and ^_^
by boobieface

on The Secrets of the Powernap
by seepinglight

Napping Good For Health
on The Secrets of the Powernap
by livelifecool

Re: i really liked that one
on The Simple Life
by Larry

i really liked that one
on The Simple Life
by seele

I love it!
on What Sorting Teaches Us (Part I)
by usa_sports

Re:
on Super Bowl Challenge
by defkism

What Sorting Teaches Us (Part II)

Submitted by Larry on Fri February 16th, 2007 at 04:59:47 PM EST

If you haven't, read Part I of this series. And now onward we go..

I lied. No one in their right mind would possibly take the term "brute force" that literally, taking every possible permutation..

In fact, we can easily do better. What would be the schoolyard way of doing things?

Find two numbers, any two numbers in the sequence. If the earlier one is bigger than the latter, swap them.

The pseudo-code would look something like:

while ( Not Sorted )
   pick two indices
   if earlier one is bigger than the latter, swap

What is the complexity of this algorithm? A simple way of looking at it would be to say that there are O(N^2) possible pairs of indices to swap, and the linear check to see if it's sorted - so the algorithm is O(N^2).

With just a little thinking, the simplest algorithm gives us an quadratic algorithm! Yay! in fact, most of the more elementary sorting algorithm are just heuristics for telling us which two elements to pick.

The most intuitive sorting algorithm of this sort is the selection sort - it might be how you sort in "real life" - simply go through the list, and find the minimum. Then, swap the minimum with the front of the list. Now you have a problem of size N - 1! (Or, shall we say, subproblem..)

The other intuitive sorting algorithm is probably the bubble sort - nothing fancy about it, go through the list and check adjacent elements. This is probably the worst of these quadratic algorithms. Wait, if they're all quadratic, then why is this one the worst? Because even though the big Oh notation hides the constants, in practice, there are too many swaps. In selection sort, there will be at most N swaps - if everything was out of place, there is at most one swap each pass. Here there might be O(N^2) swaps, so in practice, this is significantly worst - swapping elements isn't free, after all.

The only other one I'll mention here is insertion sort. Bam! Online algorithms! Basically, in an insertion sort, you scan the list to see where you would insert the current element, and push everything back. This is a bit faster because it does not need to swap - it only needs to copy. Surprisingly, this will come in handy later..

Okay, now the more boring of the bunch out of the way, onward to the funky O(n log n) stuff!

2734 Full Story (Permalink) Comments: 0