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.

Anyway, that’s about all I’ve got to say about this one,
other than comp sci is way better than calc XP

not edited

## No comments:

## Post a Comment