StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>The right way to do this in C++ is via templates.</p> <p>Sorting something is an algorithm, and it generally has little to no persistent state. A sort isn't an object -- it is a function on data (which may be objects).</p> <p>The <code>std</code> library already has a sort, with this signature:</p> <pre><code>template<typename I, typename C = std::less<typename std::iterator_traits<I>::value_type> > void sort(I begin, I end, C comp = C()); </code></pre> <p>The iterators <code>begin</code> and <code>end</code> denote a range of values to be sorted, and comp is a functor (or function) that when passed two elements of the range of values tells you if the first one is less than the second.</p> <p>To use this on a <code>std::vector</code>, you'd do something like this:</p> <pre><code>std::vector<int> myVector; // assume it has some data in it sort( myVector.begin(), myVector.end() ); </code></pre> <p>The std::sort is (usually?) a quicksort. But the interface works for quick, bubble and insertion sort.</p> <p>The big advantage of this approach is that one sort can use another. As an example, while a quicksort is faster on large data sets, often on small data sets the simplicity of insertion sort wins (lower constant factor, even with the n^2 overhead). So by writing your sorts like this, quicksort's recursive calls can instead become insertion sort when the number of elements is small.</p> <p>Now, if you need run-time substitution of which algorithm you are using, you'll need to pin down what iterators you are using, and maybe even what comparitor. This can be done with either a common function signature (what I'd do), or a base class with a pure virtual interface (which I would advise against). Note that the overhead for a run-time chosen comparitor is non-trivial, however. The overhead from a fixed iterator choice, or from a pointer-to-function or virtual method call, so long as it isn't done in the recursive calls of your algorithm, will be pretty cheap for any reasonable sized container.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload