## Friday, November 29, 2013

### Sorting Time Stuff

More often than not sorting algorithms seem to be viewed as the first major step to understanding programming after basic arithmetic. They seem to be to some extent the embodiment of what we as programmers do and while this is an extremely limited example of what a computer can and does do it’s in a way iconic. It teaches young and aspiring minds a few very key things to programming. First, speed is important. Second, efficiency is import. And most over looked I think, there is more than one way to solve a problem.

I think a lot of people thing that since computers are math based they must work like math too, and to a certain extent they do. There usually is only one right answer, and it takes a lot funky logic to get to it sometimes. Yet unlike in math, there is more than one way to apply logic to a problem. Sorting algorithms are an awesome example of this. First of all there about 10 standard ones granted some of them aren’t that great but still that’s a lot of different solutions to one problem. Here are three examples:
Selection sort starts at the top picks the smallest item and puts it at the front then takes moves on to the next position, rinse and repeat. It’s kind of slow, O(n^2), but also pretty simple.

Quick sort does live up to its name with O(nlogn) (just don’t give it a list in reverse order or it’ll be as bad as selection sort). It picks a pivot, arranges the values in the list so that those smaller than it go on the left and those bigger go on the right then does the same to the sublist and it’s sublist and it’s sublist and its sub – you get the point – until everything’s nice and orderly.

Merge sort also uses sublist but in a different way. It divides the original into to as many sublist as it has to until there’s only one element left in each sublist. It then proceeds to merge the sublist all the while comparing and making sure each sublist is in sorted order. It actually works at about the same average speed as quick sort, again O(nlogn) but lacks an obvious kryptonite.

So ya, lots of ways to fix one problem each with varying uses and speed. Also big O() notation: useful thing. It’s kind of annoying when you have to prove it but very good at giving people solid ways to compare algorithms after all it’s kind of hard to argue with graphs and number.