python / refactoring

An interesting challenge – selection sort

Following on from the previous post… I am going to play with some general sorting algorithms, and hope that these might give me some inspiration for a more imaginative answer to our question. The first algorithm I will play with is selection sort. Here it is:

selection_sort

This doesn’t answer the question, which doesn’t call for a full sort. But it is starting to get the brain firing. I chose selection sort because it most closely resembles the implementation I posted previously. It’s not bad, I like recursion. But splicing lists is quite expensive in python, so it isn’t ideal. Plus, it runs in O(n^2) time, which is not ideal.

On the downside, it is very similar to my original answer. It is just an extended version of it. So this isn’t the way I want to head. I will play around with some other ideas and see if i can’t find something interesting over the next few days.

(refactored version of selection sort here – much nicer, the return x + y, is a trick I picked up from Haskell 🙂

selection_sort_2

Advertisements

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