Sorting

Today I was introduced to a youtube video called 15 sorting algorithms in 6 minutes.  If you are not into computer science that may sound rather boring, but the video represented all of the sorting algorithms both graphically and tonally, so you could both hear and see the effect of the algorithm on a set of unsorted differing sized lines.  Even if you are still skeptical of how interesting that is, I urge you to take 6 minutes out of your day, search 15 sorting algorithms in 6 minutes and watch the video.  

With that done, you saw some rather impressive algorithms of various sorts(haha).  While some of the most interesting are a bit hard to explain, I’m going to give you the basic gist of what is happening in a few of the easier to explain algorithms.  

Bubble Sort:  Bubble sort is pretty much the easiest algorithm to think about and it is something a human being might use if they were being particularly machine like when sorting something.  It simply goes down the list of numbers, finds the largest one and puts it on the end, swapping the places of the largest and whatever was in the end slot.  Then it checks all the numbers except the one in the last slot and finds the largest.  It puts that one in the second to last spot and so on and so forth until the entire thing is sorted.  Bubble sort is useful when something is close to being sorted already, but is also commonly coded when someone has to add a sorting algorithm to something that is not very complex because it takes only a moment to code and is very simple to understand intuitively.

Radix Sort:  One of the ones in the video that seemed the most like magic was the Radix sort LSD.  The easiest way to think about that one is that it is sorting based on the places in the number.  That is it first sorts everything based on the ones place, then the tens place then hundreds place.  Of course since this is a computer algorithm, its doing this with binary numbers not decimal ones but its still pretty straightforward.  It does look like magic when it makes that last step and just kinda sorts everything at once though.  

Merge Sort:  Merge Sort works by cutting the sorting problem into a bunch of easy problems.  It cuts the first problem in half, then each of the sub problems in half etc until you are looking at a bunch of problems that are just sorting 2 numbers.  It sorts those two numbers, and then mixes them with another set of 2 sorted numbers.  Then that sorted list is merged with another of the same size until it goes all the way back up to the whole list.  The merge sort takes advantage of the fact that it is much easier for a computer to merge two sorted list into a sorted list than it is to just sort all of the elements.  Because of this, this algorithm and one called quicksort are considered the most efficient and quick algorithms for sorting assuming that you have a fully unsorted list.  

Insertion Sort:  An algorithm that is about as intuitive as bubblesort, Insertion Sort basically moves from one side of the list to the other, sorting the list as it goes along.  You order the first two elements, then you take the next element and put it in the correct place within the already sorted part of the list.  Then you put the next element in the correct place in the sorted part of the list, until everything is in the right place.  Depending upon how your list is implemented this can be costly in time, because you have to move each element that is larger over one and end up having to do a whole bunch of swaps.  Its a kind of middle of the line algorithm and is, like bubble sort, basically only implemented because its fairly simple to code.  

Bogo Sort:  The simplest possible sorting algorithm.  Check if the list is sorted.  If it is not, randomize the list.  Each step is very quick, as checking whether a list is sorted is extremely fast most of the time, but the algorithm itself takes an incredible amount of time on average for anything bigger than 6 or 7 elements long and is not guaranteed to terminate ever.  The hope of course is that it is technically possible for this to just instasort something.  Don’t ever use this method of sorting unless you are trying to make an intentionally bad sorting algorithm.  

Advertisements

Tags: , , , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: