Sort in reverse order. "Don't repeat yourself" rule

Question

Here is a piece of C++ code that do an Insertion Sort:

#ifndef INSERTIONSORT
#define INSERTIONSORT

template<class T> 
void insertionSort(T* elements, int size, int reverse = 0) {
    T tempElement;
    int j;

    for (int i = 0; i < size; ++i) {
        tempElement = elements[i];

        for (j = i - 1; j >= 0 && elements[j] > tempElement; j--)
            elements[j + 1] = elements[j];

        elements[j + 1] = tempElement;
    }
}
#endif

I can't write it without repeating code. Its not the first time I face that kind of problem. All I need is to replace < to >, when reverse = 1. The first way that I tried is to use ternary operator:

(repeat)?(elements[j] > tempElement):(elements[j] < tempElement)

It looks little bit strange and I know its not the best way to solve the problem, so I tried this:

elements[j] (reverse)?(<):(>) tempElement

But its not correct and doesn't work. Also ternary operator doubled the number of elementary operations in if statement. I know it's just an Insertion Sort that does Θ(n^2) operations (not the best way of sorting a lot of elements), but I think there is a better way to write it. Another thing is that you can't use this:

(repeat)?(-1):(1) * (elements[j] - tempElement) > 0

Because class T can have only operator= and operator> (operator<). Also you can't call function in loop, because it will be Θ(n) or Θ(n^2) calls. Here is the last solution:

#ifndef INSERTIONSORT
#define INSERTIONSORT

template<class T> 
void insertionSort(T* elements, int size, int reverse = 0) {
    T tempElement;
    int j;

    if (reverse)
        for (int i = 0; i < size; ++i) {
            tempElement = elements[i];

            for (j = i - 1; j >= 0 && elements[j] < tempElement; j--)
                elements[j + 1] = elements[j];

            elements[j + 1] = tempElement;
        }
    else 
        for (int i = 0; i < size; ++i) {
            tempElement = elements[i];

            for (j = i - 1; j >= 0 && elements[j] > tempElement; j--)
                elements[j + 1] = elements[j];

            elements[j + 1] = tempElement;
        }
}
#endif

The only problem is repeating code. The main principle of programming says: "Don't repeat yourself" (D.R.Y). I really don't know how to write code correctly here.

Take a callable object that compares elements. That's how the standard library does it, anyway, with a default of `std::less`. — chris, Jul 09 '14 at 20:35
If you really want to follow DRY, `std::sort` might be a good option :) — Rapptz, Jul 09 '14 at 20:38
@Rapptz technically that's not avoiding repeating _himself_... also insertion sort has the optimal best case complexity of O(n), better than any of the O(n log n) average algorithms and `std::sort` explicitly uses one of those. So it may be that insertion sort is more appropriate to his problem domain. Ummm, possibly. Somehow. — Tommy, Jul 09 '14 at 20:43
@Rapptz I just starting to learn algorithms and the first is the Insertion sort. I want know how to write clear code here, so next time I can easy read it and understand. — Demyanov, Jul 09 '14 at 20:44
Is there a reason that you have to have both pieces of functionality in the same function? Why not have two methods: `insertionSort` and `reverseInsertionSort` so that each method only has a single responsibility? The name of the function would make it perfectly clear what it does, though you would still be repeating some code — Caleb Brinkman, Jul 09 '14 at 20:46
@Tommy I know about std::sort and heard about switching to Θ(n^2) sorts, when number of elements is too small. But now I want to write it myself. — Demyanov, Jul 09 '14 at 20:48
Even if you sort and reverse in two steps (one after the other) it will not change the complexity of the algorithm — , Jul 09 '14 at 20:48
@DieterLücking Ok. Anyway its Θ(n^2), but I though that might be better solution. — Demyanov, Jul 09 '14 at 20:55
@Demyanov Chaining the steps, the complexity will be the worst complexity of the steps (not a combined one) — , Jul 09 '14 at 21:01
DRY, (re-)use the STL: http://stackoverflow.com/q/24650626/819272 — TemplateRex, Jul 13 '14 at 20:22

score 5 · Accepted Answer · answered Jul 09 '14 at 20:49

5

You could add a comparator as a type, like the example below:

template<template<class> class COMP = std::less, typename T> 
void insertionSort(T* elements, int size) {
    T tempElement;
    int j;
    COMP<T> pred;
    for (int i = 0; i < size; ++i) {
        tempElement = elements[i];

        for (j = i - 1; j >= 0 && pred(tempElement, elements[j]); --j)
            elements[j + 1] = elements[j];

        elements[j + 1] = tempElement;
    }
}

LIVE DEMO

answered Jul 09 '14 at 20:49

101010

41,839
11
94
168

Why don't you switch the template parameters and change `COMP` to `class COMP = std::less`. Then you can just refer to it as `COMP`. – David G Jul 09 '14 at 21:07
@0x499602D2 because I would have to define explicitly `T` as well. This way `T` is deduced by input argument `elements`. – 101010 Jul 09 '14 at 21:17
1

[You could make another overload if you wish.](http://coliru.stacked-crooked.com/a/2aa539b4f6d87ebc) – David G Jul 09 '14 at 21:26
@0x499602D2 Nice, I didn't think of that, could be an alternative I guess. – 101010 Jul 09 '14 at 21:29
@0x499602D2 in C++11, you can do `template>> void insertion_sort(FwdIt first, FwdIt last, Compare cmp = Compare{})` to only have a single overload, see e.g. http://stackoverflow.com/q/24650626/819272 – TemplateRex Jul 13 '14 at 20:24
@TemplateRex I've seen your example and I prefer it, but 40two's version allows you to set the predicate template using a single template argument without providing the value type first. – David G Jul 13 '14 at 20:28
1

@0x499602D2 I use the interface that Stephan T. Lavavej showed in one of his videos, and you can simply do `insertion_sort(first, last, OtherComp{})` without specifying a single template parameter, and just passing a comparison function object. Everything is deduced. – TemplateRex Jul 13 '14 at 20:39

Sort in reverse order. "Don't repeat yourself" rule

1 Answers1