Which is the best sorting algorithm?
None. It depends on the circumstances.
Naturally, the next question is: Which one must be used in each case?
The best choice is almost always the implementation that comes with the language you are using.
In some cases you can choose among the following options:
- Stable sort. Generally requires O(N) additional memory, that is, an amount proportional to the data being sorted.
- Non-stable sort. Requires very little additional memory, but does not respect the previous order of the elements considered equal to each other.
More details in: stable sort
and in: “big O” notation.
In C++, for instance, you can choose between std::sort and std::stable_sort.
In the field of sorting with little additional memory there have been several favorites along the history: ShellSort (1959), quicksort (1960), heapsort (1964) and more recently introsort (1997), which is a hybrid of quicksort, heapsort and insertion sort.
Mergesort (1945) dominated many years in the field of stable sorting. Its replacement seems to be Timsort (2002). It is also a hybrid, this time of mergesort, insertion sort and a few more tricks.
I will discuss the few cases where it makes sense (in my opinion) to tailor your own implementation of a sorting algorithm. But I’ll do it later ;-)
My [first] book
I wrote a book! (in Spanish)
Well, yes, I’m a bit boring… I wrote it long ago. Family and friends have read it already and keep asking me when will I write the second one. (Thanks, I love you too ;-)
But this blog is new, so here it goes:
It’s a short science fiction novel, or rather a long tale. You can download it in PDF (for free) or order a printed copy (paying) in bubok.
I’m just an amateur writer and I made some mistakes that I’ll try to avoid in the future. Specifically, I must warn you that the maths stuff from the beginning can be skipped. It’s not all like that ;-)
Finally, I link here a pearl of Spain’s TV memory (sorry, no subtitles). What a moment!
Project Euler
ProjectEuler.net is a great invention that I discovered a couple of years ago. It houses a very interesting collection of programming problems.
The first ones are relatively simple. Then the difficulty increases as you advance through the list of problems.
Every problem is designed to be solved with less than one minute of processing in a normal computer. Many take just a few microseconds. Any language like C or Java with 64 bit integers should suffice. Many people use other languages.
In principle, new users only have access to the problem statements.
For every problem there is a forum where previous users have been sharing their solutions. For many problems there is also a PDF overview explaining possible solutions.
But users can only access the forum and the PDF overview of a problem after solving it and entering the correct answer on the website.
At first glance this might seem a nonsense. What’s the point if the user has already found the solution? There’s a big point, indeed! There are often several ways to solve a problem and they are not all equally efficient. The forum and the PDF overview contain vital clues to approach future problems.
Out of the hundreds of problems that exist in Project Euler, I have solved 81 to date. As a result I have learned a lot about combinatorics and dynamic programming, among other things. About the latter, by the way, I plan to write some day on this blog.
Aside from having solved a few problems, I can proudly say that I contributed my bit to Project Euler: I volunteered for the preparation of the PDF overviews for problems 31 and 53.
Unfortunately, Project Euler has been a while running at half speed. Administrators discovered that someone had sneaked into their database and they shut down the website. They reopened it later but with “reduced functionality”. That is, you can access the problem statements and you can check whether a solution is correct, but there are no forums or PDF overviews.
Reproducing here the problem statements or giving clues to the solutions would go against the philosophy of Project Euler, so I will just link the statements …
Problem 53: combinatoric selections
… and provide the PDFs with the same requirement as prescribed in Project Euler, i.e., having solved the problems previously:
[..]
Update (17th of August, 2014): Project Euler is working again, so I have removed the PDFs from this blog.
The music I like
Before going into technical issues, I want to share with you my playlists.
I’m a [reasonably] satisfied user of Spotify. If you are Spotify users too, you can access my playlists by typing spotify:user:comocomocomo in the search bar:
I hope you enjoy them and feel encouraged to send me yours ;-)
Update: There is an easier method…
Shoelaces? Why that weird title?
Do you know how you tie your shoelaces?
“Of course! I do it every day” – you must be thinking.
No, no, no. I assume you can tie your shoelaces. What I wonder is if you know how do you do it. Could you describe it step by step, in words or pictures? That’s another kettle of fish… You are not allowed to test it. You can not even look at your shoes. How do you move each finger at every step?
If you can describe how to tie shoelaces, it’s probably because you had to teach someone how to do it.
Something similar happens with programming. We have to teach the computer how to perform tasks that we can do. But we have to describe them in detail, in a very limited language. Nothing is understood implicitly by the computer. We often find ourselves thinking hard to separate the elementary steps of a process that we perform automatically, almost unconsciously.
Therein lies one of the difficulties of programming. The other difficulty is that, expanding the analogy, we need the computer to do all known sailor knots… and some more.