Sorting it all out

Well, I have missed a couple of SLOG entries over this term, so I’m gonna try to make up for it by posting a few today. In this one I want to talk about sorting algorithms. (In the spirit of holidays this post also includes lots of flashing coloured things) We went over the basic and/or most common sorts:

Bubble

Image by Wikipedia User Swfung8

Insertion

Image by Wikipedia User Swfung8

Selection

Image by Wikipedia User Joestape89

Quick

Image by Wikipedia User Matt Chan

and last but not least Merge

Image by Wikipedia User Swfung8

However the world of sorting doesn't end there. One sort I thought of, and I believe we may have done in class was using a binary tree to sort. You make a Binary search tree and add items accordingly, and then do an inorder traversal of it. The performance of such a sort is quite good: O(n log n) on average )( n) in best case. The worst case is a bit more interesting though where you can have a balanced or unbalanced BST. Balanced means the tree's height is the minimum (or close to) of what it can be (log2 n [thats "log base 2 of n"]) and unbalanced means it is more. Balancing a tree can be quite the overhead but it doesn't have to happen upon every insertion. 

The difference in worst case performance is O(n log n) for balanced and O (n^2) for unbalanced.

Balancing a tree seems rather tricky and I have yet to figure it out exactly, but I hope this sparks some interest in some of you.

Anyways that concludes this post, see you guys next week (actually like a few hours).