This is the second in my series of algorithm posts in trying to become a better programmer. Counting sort is possibly my favorite of the sorting algorithms because it looks so complicated at first glance, but its actually very simple and graceful.

The principle behind counting sort is to store a count of each value that appears in the array and use that as a way to place the original value in the resulting array. It's generally used for fairly low numbered positive integer values, and the running time of the algorithm depends on both the number of elements, and the range of values within the array. For example, a simple array with the values (1, 6, 1000000000) will take a LONG time to be sorted, even though there are only three elements because at some point there will be a loop from 0 to 1000000000. Also note that the sort method requires a parameter k, which is the maximum value contained in the array.

If you don't understand the algorithm, it would probably be better to read the wikipedia article instead of trying to rely on my brief and badly written version.

Language Choice

I decided to do a version in Python because I've never really used the language much and I figured it was a good way to give it a try. My first impressions are pretty positive, and I love how it uses indenting as part of the language semantics.

My C Implementation:

My Python Implementation

This is the first post in my quest to be a better programmer. Quicksort is one of the 'standard' sorting algorithms. Its fairly easy to implement, and normally runs fairly quickly. I've implemented quicksort in both C and Scheme, although I think my Scheme implementation is more of a pseudo-quicksort due to a reluctance to break from the functional style encouraged by Scheme syntax.

Quicksort Overview

The 'Partition' algorithm is at the core of a quicksort implementation, and this partitions an array into groups of 'less than x' and 'more than x', with x itself being placed inbetween. The final position of x is the value returned by the partition function. In my simple implementation, the choice of x remains constant (either the first or last element). Randomizing this is the main way to increase the worst case speed of this algorithm.

After partitioning the initial input, quicksort recursivly calls itself on the 'less-than' and 'more-than' groups returned from partition. The result is a chain of recursive calls which continues until quicksort is trying to sort a single number.

Check out Wikipedia to get a more in-depth understanding of quicksort.

Special Property

Quicksort is good because it sorts 'in-place'. In other words it doesn't use a secondary array to sort the elements into. This can save a lot of memory, especially if you are sorting a list of complicated data structures which are a few KB each.

My C Implementation

My Scheme Implementation

I think its worth noting that the scheme implementation doesn't exactly sort 'in-place'. Instead it recursivly builds up secondary lists then joins them together at the end as the return value instead of moving the elements around in a single list. However the amount of memory used should still be in the order of the number of elements in the input array unlike other sorting algorithms (counting-sort, and bucket-sort come to mind) which use secondary arrays which do not form part of the solution.

(define pHelper (lambda (all chk l m)
                  (cond ((null? all) (cons l (cons chk (cons m '()))))
                        (else
                        (let ((x (car all)))
                          (if (<= x chk) 
                              (pHelper (cdr all) chk (cons x l) m)
                              (pHelper (cdr all) chk l (cons x m))))))))

(define partition (lambda (l)
                      (pHelper (cdr l) (car l) '() '())))



(define quicksort (lambda (l)
                    (cond ((null? l) l)
                          (else
                          (let ((lx (partition l)))
                            (append (quicksort (car lx)) (cons (cadr lx) (quicksort (caddr lx)))))))))

In an attempt to be a better programmer, and even better student, I'm undertaking a new mini-project: I will make a series of blog posts whereby I describe a particular (well known) algorithm, then provide an implementation in 2 different programming languages.

Skills++

Doing this should help with two things.

1) It should make me remember these algorithms in more detail. Most of these algorithms are so very clever that it will certainly help if I know them by heart.

2) At a time when I don't need to use anything other than Java it will help to keep me comfortable with other languages.

Languages

I'm certainly going to do every algorithm in C, probably not with the best C code, but certainly C code that works. Also I'll probably switch in and out of a functional language such as Scheme and something like VBA to keep it old-school.

Algorithms and Links

I will update this post with links when I make each post. Also check out the Operation-Algorithm tag in my tag cloud for easy access.

Quicksort
Counting Sort
BucketSort (love this one)
Heapsort (including the making of a Max-heap)
Binary Search Tree creation and traversal

Stay tuned!

So I was casually browsing blogs and twitter posts this morning and came across a bunch of links to a new twitter application called Tweeter Getter. Essentially this is a twitter pyramid scheme to get you *thousands* of followers.

Pyramids

Here is an apt description of the pyramid business model from Wikipedia:

The essential idea is that the mark, Mr. X, makes only one payment. To start earning, Mr. X has to recruit others like him who will also make one payment each. Mr. X gets paid out of receipts from those new recruits. They then go on to recruit others. As each new recruit makes a payment, Mr. X gets a cut. He is thus promised exponential benefits as the "business" expands.

Twitter + Pyramid

In our case the business is twitter followers, and the payments are follows.

By following the first 6 users on the list, and retweeting your own link, you start your own little pyramid coming in under the 6 people above you. They get a new follower, and on the assumption that people ACTUALLY follow your link you could get the same.

Each subsequent person that joins the pyramid from either your link, or a derivative of your link will add you as another follower.

Lots of People

Of course this model is not sustainable in the long term, and the more people join the lower the 'returns' are likely to be. By the time the pyramid is 13 layers deep, it will need more than the entire population of the globe to participate in order to continue.

I move to New York City in July with my soon-to-be fiance and while we're very excited, the amount work required in order to make it happen is staggering

I'm doing a masters in computer science, and its already taken me about 9 months to pull that off, but we still have to:

1. Get the university documentation I need for a visa
2. Get a Visa
3. Work out if shipping all our stuff to the USA is cost effective
4. Realize it isn't
5. Sell everything we can't fit into 4 (large) suitcases
6. Sell more stuff when we realize the suitcases weigh three times the allowed limit
7. Cancel all our phone bills / electricitiy bills / internet bills / etc
8. Sell the car (already done!)
9. Move out of our London flat
10. Find somewhere to stay until our flights (Thanks Rob)
11. Fly out
12. Move in
13. Realize we forgot something important
14. Realize we're going to have about 1/2 the space we had in London

Costs

We thought it would be pretty cost effective to ship all our stuff by freight, you know because it takes 2-3 months and your stuff could get covered in sea water, but we were quoted £400 just to ship 5 regular moving boxes. Thats insane.

Bearing in mind that its costing us $30,000 a year for me to do a masters we need every penny we can get.

Crazy

You'd also think that a university such as NYU (which has 45% international students) would have a process in place for registering with various national governments as a provider of education. Apparently they missed that lecture, and instead I have to deal with administration offices who have absolutely no idea.

I'm trying to get them to register with the UK Learning and skills council (so the UK government will give me an interest-paid loan). Its already taken me a month of talking to one office after another, and they still haven't managed to fill in the 2 page form. I keep getting responses like "we don't think we can participate in that scheme" and "we don't understand the requirements", but what they really mean is "We can't be bothered".

Excited Regardless

All this stuff will go away in a few months so I'm not going to let myself get worked up. Instead I think I'll just dig in the the final push, because this next year could well be the best year of my life.