CODEWITHSUNDEEP
c++arrayssorting
Jeff Huijsmans
Jeff Huijsmans

Reputation: 1418

QSort doesn't sort correctly, unless sorting one extra time afterwards

I'm trying to add two Priority Queues to each other by overloading the "+" operator. 

// Overloading add operator (+)
template <class T> PrioQueue<T> operator + (PrioQueue<T> &a, PrioQueue<T> &b) {
    // Create a new queue that's big enough to hold our 2 queues
    PrioQueue<T> newPrioQueue(a.num_items + b.num_items);

    // Push all items to the new queue
    // all items will be sorted on pushtime (get it? Instead of runtime? Haha... Ha...)
    for (T * element = a.bottom_; element < a.bottom_ + a.num_items; element++) {
        newPrioQueue.push(*element);
        std::cout << newPrioQueue;
    }

    // Push all items to the new queue
    // all items will be sorted on pushtime
    for (T * element = b.bottom_; element < b.bottom_ + b.num_items; element++) {
        newPrioQueue.push(*element);
        std::cout << newPrioQueue;
    }

    // This one is needed - why?
    newPrioQueue.sort();

    std::cout << newPrioQueue;

    // New queue is done, return it.
    return newPrioQueue;
}

This is my PrioQueue's push function:

void push(T t) {
    if (!full()) {
        *top_ = t;
        top_++;
        num_items++;

        // Sort items using qsort
        qsort(bottom_, num_items, sizeof(T), compareFunction);
    } else {
        std::cout << "Queue is full" << endl;
    }

};

As you can see, the PrioQueue will get sorted after every push. However, one last sort is needed after combining the two arrays! Check this output:

Queue has 1 item(s): 429
Queue has 2 item(s): 429|123
Queue has 3 item(s): 429|123|24
Queue has 4 item(s): 429|123|24|24
Queue has 5 item(s): 429|123|24|24|3
Queue has 6 item(s): 429|123|24|24|3|2
Queue has 7 item(s): 24|123|24|429|3|2|1
Queue has 7 item(s): 429|123|24|24|3|2|1

The second to last line is the bug. It suddenly scrambles all the data!

Why is this happening?

EDIT: Here's my CompareFunction:

static int compareFunction (const void * a, const void * b) {
    // Relies on overloading of the "<" operator with non-std objects
    return (*(T*)a < *(T*)b);
}

This is the input:

intQueue1.push(24);
intQueue1.push(429);
intQueue1.push(123);

intQueue2.push(1);
intQueue2.push(2);
intQueue2.push(3);
intQueue2.push(24);

intQueue3 = intQueue1 + intQueue2;

Upvotes: 2

Views: 129

Answers (2)

Thomas Ayoub
Thomas Ayoub

Reputation: 29431

I may be wrong but your compareFunction:

static int compareFunction (const void * a, const void * b) {
    // Relies on overloading of the "<" operator with non-std objects
    return (*(T*)a < *(T*)b);
}

Is supposed to return 1, 0 or -1 and it return true or false...

Upvotes: 3

Mike Seymour
Mike Seymour

Reputation: 254431

You shouldn't be using qsort in C++ without a very good reason. Try

std::sort(bottom_, bottom_+num_items);

This will compare using <, so there's no need to provide a comparator if your type overrides that operator.

If you really want to use qsort for some reason, then beware that it only works for trivially copyable types, and needs a different form of comparator, returning a negative, zero or positive value to indicate respectively less than, equal or greater than. You'd need something like

T & aa = reinterpret_cast<T&>(a);
T & bb = reinterpret_cast<T&>(b);
if (aa < bb) return -1;
if (bb < aa) return 1;
return 0;

Upvotes: 1

Related Questions