How to randomly sort an array

In this article, I will introduce a random sort algorithm with a complexity of O(n).

A randomized array is widely used in games (e.g., Poker) and other systems alike. So I assume it is a commonly encountered program difficulty.

The most intuitive approach is slow. To randomly sort elements in an array A and copy the results to B, this approach 1) uses a random generated number as an; 2) fetch the element from array A using the index; 3) checks if the element exists in B already; 4) if not, insert the element in B and 5) If so, goes back to 1) and regenerates a random index again and conducts the check. As the program proceeds and the B grows bigger, it is more likely that a randomly selected element already exists in B, so the algorithm has to redo everything again (regenerate an index, iterate B to check if the element exists) from 5). When the program reaches the very end of the procedure, the performance becomes unacceptably slow.
To avoid the collision, we can remove the element from A once it is selected. The art is about how to remove to achieve O(n):

1) each time we select an element we append it in the new array;
2) we assign the element from the original array with the last element in the tail;
3) we reduce the size of the original array by 1.

And here is the code:


Callback class for member functions in C++

This article is derived from the post. It describes a generalized class that can represent C++ member functions as callbacks, like a function pointer in C. In the original post: these callbacks are called as “delegate”s but I will keep using the term callback.

In traditional C, function pointers are used for callbacks. However, In C++, the definition of a callback is a bit more complex because most functions (member functions) require an instance pointer to be invoked.

After fixed some typos in the demo code, I made it compilable and runnable in my ubuntu virtual machine. Next, I will explain the critical lines in the source code. N.b., in the demo code, it use a concrete types for a callback’s prototype (i.e., <void(int)>). In real-world application, however, those types can be made genetic too.

In #1 #2 and#3, the genetic parameters are passed all the way down to the method_stub, which is the working horse of this class. For now,  it is a template function that is not specialized yet. In the constructor, object_ptr points to the instance pointer and stub_ptr points to the specialized version of method_stub. With the combination of object_ptr->stub_ptr, the callback is ready to use.

Two points worth noting here are #4 and #5.

In step #4, the cast is not necessary if we move the template T to the class itself and do necessary changes. However, this makes the delegate polymorphic thus is inefficient according to the original post.

In step #5, the confusing dereference here is actually the syntax for invoking a function pointer to a member function.