Shake sort using MACRO

Question

Shake sort of vector: program works, but:

I was trying to use the same function for bubble up and bubble down for shake sort (bubble up to get the MAX value to the right and bubble down to get the min value to the left). In order to do it I was trying to use the following MACRO which does not compile:

sign is '+' and oper is '>' for bubble

sign is '-' and oper is '<' for bubble down

for bubble up -

start is iterator i (iterated the Vector indices)

end is n-1-i;

for bubble down - swap start and end values

#define bubble_up_down(var_t, pVector, _Is_swp, start, end, sign, oper)\
{\
    var_t current_index;\
    var_t current_val;\
    var_t next_val;\              
    for (current_index = *(start) ; current_index (oper) *(end) ; (sign)(sign)current_index){\
    {\
        VectorGet((pVector), current_index, &current_val);\
        VectorGet((pVector), current_index(sign)1, &next_val);\
        if(current_val (oper) next_val)\
        {\
            VectorSet((pVector), current_index, next_val);\
            VectorSet((pVector), current_index(sign)1, current_val);\
            *(_Is_swp) = 1;\
        }\
    }\
}

Need your advice to fix this macro.

Answer 1

It is not really clear why you want to use a macro here. Do you want to avoid duplicaing code? Or do you want to make your sorting routine type independent?

Anyway, your macro has several errors:

• You've probably read that you should guard macro arguments with parentheses. That is usually good advice, because macros are text replacements; for example infamous SQ(x + 1) will resolve to x + 1*x + 1. In your case, the advice is wrong-headed. You will get syntactically wrong "operators" such as (-) and (<) in your code. Just use sign and oper.
• Even so, sign sign will resolve to - - or + +, which is not what you want. You could rewrite i++ to the equally valid i = i + 1 or you could use the token-pasting operator, sign##sign, which would produce -- or ++.
• Macros aren't functions. You are probably going to invoke your macro inside a function. All local variables that are in scope hen you invoke the macro are also in scope for the macro. That means there is probably no need to define all these pointers.
• Why do you pass the array element type, var_t? I reckon that SetVector and GetVector aren't macros, so the type independence falls flat.
• If var_t is the type of your array elements, your index isn't necessarily of the same type; it should be an integer type. (Your elements must be comparable with the < operator, so it is one of the arithmetic types, but image what happens if you have an array of char that is longer than 256 elements?)
• If your elements are of arithmetic type, there's probably no need for the GetValue and SetValue calls. You can just assign values with the = operator .

All this makes me think that you don't really know what you're doing. That plus the known pitfalls and shortcomings of macros are a good reason not to use any macros here.

---

Addendum   In comments, The PO has said that the macro should achieve two things: It should avoid repeated code and it should make the sorting independent of the types of the array elements. These are two different things.

Writing short local macros to avoid repeating code can be a useful technique, especially, if the code needs to keep variables in sync in several places. Is it useful in your situation?

So you've got your upward-bubbling code:

int done = 0;

while (!done) {
    done = 1;

    for (int i = 1; i < n; i++) {
        if (a[i - 1] > a[i]) {
            swap(a, i - 1, i);
            done = 0;
        }
    }
}

(This uses a swap function to swap two array elements. It is more straightforward than your version, because it doesn't use get/set accessor functions.) Now you write the downward-bubbling counterpart:

while (!done) {
    done = 1;

    for (int i = n - 1; i > 0; i--) {
        if (a[i - 1] > a[i]) {
            swap(a, i - 1, i);
            done = 0;
        }
    }
}

These two snippets differ only in the loop control. Both visit all indices from 1 to n - 1. So your macro needs to pass the start and end values. But it also needs to know which way the comparison goes – less than or greater than – and whether to increment or to decrement the index. That's four pieces of data for a simple loop.

You could try to get rid of the comparison and use != for both directions. But then your loops will fail if the array is empty.

The above backwards loop will already fail on empty arrays when you use an unsigned integer as index. Forward and backward lops are asymmetric an C, because the lower and upper bounds are asymmetric, too: Lower bound are always inclusive, upper bound are always exclusive. This forward loop:

for (unsigned int i = 0; i < n; i++) ...

Has the following backward equivalent:

for (unsigned int i = n; i-- > 0; ) ...

Here, the decrement occurs in the condition and the update part is empty. The advantage is that it uses exactly the same bounds, 0 and n, verbatim, but by decrementing before entering the loop body, the same valid range of numbers, 0 to n - 1 are visited. And it works with unsigned ints, which are a natural choice for looping variables.

To cut a long story short: Forward and backward loops are asymmetric in C, so it is not easy to write a macro for them. C's for syntax is more verbose than for i = 1 to n, but that's how it is. Embrace it and alleviate the typing pain by chosing appropriate index names: it's i, not current_index.

Can you make the code less redundant without macros? Of course: You can write two functions for bubbling up and down once:

static int bubble_up(int a[], int n)
{
    int done = 1;

    for (int i = 1; i < n; i++) {
        if (a[i - 1] > a[i]) {
            swap(a, i - 1, i);
            done = 0;
        }
    }

    return done;
}

static int bubble_down(int a[], int n)
{
    int done = 1;

    for (int i = n; i-- > 1; ) {
        if (a[i - 1] > a[i]) {
            swap(a, i - 1, i);
            done = 0;
        }
    }

    return done;
}

(These functions are static, i.e. private to the current compilation unit.) Now your actual sorting functions look like this:

void sort_bubble_up(int a[], int n)
{
    int done = 0;

    while (!done) {
        done = bubble_down(a, n);
    }
}

void sort_bubble_down(int a[], int n)
{
    int done = 0;

    while (!done) {
        done = bubble_down(a, n);
    }
}

void sort_shaker(int a[], int n)
{
    int done = 0;

    while (!done) {
        done = bubble_up(a, n) || bubble_down(a, n);
    }
}

If you are not afraid of empty loop bodies, you can even get them down to:

void sort_bubble_up(int a[], int n)
{
    while (bubble_down(a, n)) { }
}

void sort_bubble_down(int a[], int n)
{
    while (bubble_down(a, n)) { }
}

void sort_shaker(int a[], int n)
{
    while (bubble_up(a, n) || bubble_down(a, n)) { }
}

All this code works only for int arrays, though. The standard library's way of approaching type independence is to work on the byte level via void * pointers and user-defined comparison functions. The sorting function qsort does this, for example.

C++ and other languages have templates, where you can write an algorithm for several types. When you "instantiate" a template, the compiler creates a function for just this type, which is then called.

You could emulate this with macros. If you just want to call your macro in the function body, you could define:

#define BUBBLE_SORT(ARRAY, N, TYPE) do {         \
        int done = 0;                            \
        int i;                                   \
                                                 \
        while (!done) {                          \
            done = 1;                            \
                                                 \
            for (i = 1; i < N; i++) {            \
                if (ARRAY[i - 1] > ARRAY[i]) {   \
                    TYPE sawp = ARRAY[i];        \
                                                 \
                    ARRAY[i] = ARRAY[i - 1];     \
                    ARRAY[i - 1] = swap;         \
                    done = 0;                    \
                }                                \
            }                                    \
        }                                        \
    } while (0)

and then use the macro like so:

char c[] = "Mississippi";

BUBBLE_SORT(c, strlen(c), char);

(That do { ... } while (0) thing around thze macro makes the macro behave like a function call, sort of. The new scope of the loop body allows for local variables.)

The problem here is that such multi-line macros are hard to debug. When there is an error in the body, you just get the number of the line where the macro is invoked in an error message. (But you can use -E with most compilers to see how the preprocessor resolves that macro.)

Conclusion:

• Macros can be useful, but you have to know what you are doing. In general, try to avoid them, because they are hard to debug and often hard to understand for others. (And this other person might be you half a year later.)
• If you must use macros, try to make then look as natural as possible. Passing operators like > or + should make you wary.
• Use functions, not macros, for common code.
• Embrace C's way to deal with different types. It will be more useful (if less fun) to learn how qsort works than to fiddle with macros for a bubble sort implementation.
• If you really need to write a lot of type-independent code, you probably shouldn't use C.