Why quick sort throws an exception "write access violation"

Question

I wanted to write quick sort but my program have an error. In first in my program had infinite loop in main cycle in qsort function.Than i added left++; right--; and there was an exception. Please review my code and help me solve this problem.

#include <iostream>

using namespace std;

typedef int (*CFT) (const void*, const void*);

struct User
{
    const char* name;
    int dept;
};

void print_id(User* v, int sz);
int cmp2(const void* a, const void* b);
void qsort(void* base, int n, size_t sz, CFT cmp);

User heads[] = {
    "g", 1,
    "d", 3,
    "s", 5,
    "c", 2,
    "t", 4,
    "h", 6,
    "y", 7,
    "z", 8,
};

int main() {
    const int SIZE = 8;
    print_id(heads, SIZE);
    qsort(heads, SIZE, sizeof(User), cmp2);
    cout << endl << endl;
    print_id(heads, SIZE);
    return 0;
}

void print_id(User* v, int sz) {
    for (int i = 0; i < sz; i++)
    {
        cout << v[i].name << "  " << v[i].dept << endl;
    }
}

int cmp2(const void* a, const void* b) {
    int aa = ((User*)a)->dept;
    int bb = ((User*)b)->dept;
    return aa > bb;
}

void qsort(void* base, int n, size_t sz, CFT cmp) {
    char* b = static_cast<char*> (base);
    char* lg = b;
    char* rg = b + n * sz;
    char* left = lg;
    char* right = rg;
    char* control = b + (n / 2) * sz;
    do
    {
        while (cmp(control, left) && left < rg) left += sz;
        while (cmp(right, control) && right > lg) right -= sz;
        if (left <= right) {
            for (int k = 0; k < sz; k++) {
                char tmp = left[k];
                left[k] = right[k];
                right[k] = tmp; // exception write access violation
            }
            left++;
            right--;
        }
    } while (left <= right);
    if (lg < right) qsort(lg, right - lg, sz, cmp);
    if (left < rg) qsort(left, rg - left, sz, cmp);
}

I dont now how templates work so please dont use them in answers.

*Please review my code and help me solve this problem.* -- [How to implement classic sorting algorithms using modern C++](https://stackoverflow.com/questions/24650626/how-to-implement-classic-sorting-algorithms-in-modern-c) — PaulMcKenzie, Aug 20 '20 at 14:13
@NathanOliver I wanted to wright function which can sort everything not just `struct User`. — LoaDeadd, Aug 20 '20 at 14:13
A hint: With `n`: `SIZE` (8) and `sz`: `sizeof (User)`, `rg = b + n * sz;` will point to the byte past end of your array. With `right = rg;` and `while (cmp(right, control)`, you have an access to memory past end of your array. I guess from here on terrible things may happen which I expect to end up e.g. with _`// exception write access violation`_ (You may debug step-wise to prove me right or wrong.) — Scheff's Cat, Aug 20 '20 at 14:16
*I wanted to wright function which can sort everything not just struct User* -- That is what templates are made for, not `C` coding using void pointers. -- *I dont now how templates work* -- Well wouldn't this be a great time to learn how to use them? — PaulMcKenzie, Aug 20 '20 at 14:18
@KamilCuk Why? I used this structure like example in other sorts and another functions. All worked correct. — LoaDeadd, Aug 20 '20 at 14:24
I agree with @Scheff. I think `char* rg = b + n * sz;` needs to be changed to `char* rg = b + (n-1) * sz;` provided n >1. If not just return. — drescherjm, Aug 20 '20 at 15:02

Nikola · Answer 1 · 2020-08-20T14:18:17.960

1

qsort(heads, SIZE, sizeof(User), cmp2);
...
for (int k = 0; k < sz; k++)

sz is set from sizeof(User)

sizeof(User) is not the same as number of User in heads array. For should be changed to:

for (int k = 0; k < n; k++)

edited Aug 20 '20 at 14:18

answered Aug 20 '20 at 14:16

Nikola

125
1
8

I know. Number of elements is SIZE – LoaDeadd Aug 20 '20 at 14:17
in function sz is size of one element and n in number of elements – LoaDeadd Aug 20 '20 at 14:29
I see what the if (left <= right) { } block does now. `sz` is actually correct. The usage is to swap 2 items. It would have helped to put a comment in about this. Also the <= is unnecessary. Swapping a item with itself is not needed. – drescherjm Aug 20 '20 at 14:59

Why quick sort throws an exception "write access violation"

1 Answers1