Mergesort in C++

Standard

This is my favorite sorting algorithm. It’s easy and it also can be parallelized using multiple machines / processes for huuuuge data sets.

Its runtime is (like Quicksort) O(n log(n)). Again here it’s because you split each part into two and work on it recursively.

Most fun is to think about the way Mergesort works in general and find your own implementation. Well, of course each implementation will look pretty much the same in the end…

Quicksort implementation in C++

Standard

This one among a thousand implementaions of the Quicksort algorithm.

Its runtime is O(n log(n)) since you divide each part into two and recursively sort the two parts (always splitting by 2 is logarithmic growth…).

You could optimize it by using Insertionsort for a small input vector (i.e. less than 50 elements). Additionally you can convert the recursive algorithm into a iterative one (maybe I will post this in the future).
You should be careful, and always pass the input vector per reference “&”. If you don’t sorting does not take effect on the input in the end.

Here is another implementation that works on plain integer arrays.

 

Insertionsort with C++ STL vector

Standard

This is my Insertionsort implementation using C++ STL.

Its runtime is O(n^2) because you run through the entire list twice (the outer and the inner loop).

It’s important to pass the input as reference if you want to sort the original vector.

Coding Interview Problem Sites

Standard

I was practicing for a coding interview. Here you can find a list of good problem sites. Some of them have solutions.

Have fun coding and thinking about the problems.

During the interview it’s very important to think out loud to show your way of thinking. Also tell the interviewer why would chose one option over another one. If you see any problem with your current implementation say it out loud – and of course try to find a better solution!

sudo returns “xyz: command not found”

Standard

I ran into the situation that I could not execute any command with “sudo” without passing the entire path to the actual command (you can get the path with “which”).

I.e. “sudo port install subversion” always returned “port: command not found”.

The reason is, that the superuser / root does not know the “port” command.

One solution would be to add the path to the command to the .bash_rc or .profile file in the root user folder (on my Mac it’s “/var/root”).
But if your root account / machine happens to be managed by Puppet or so, then this setting would be removed by Puppet immediately.

Therefore the solution for my problem was (using bash terminal on my Mac) to add the following to my .profile file:

After restarting the terminal I was able to use “mydo” instead of “sudo”.

It works perfectly :-)