Quicksort doesn't work for the last two numbers

Question

The task was to write quicksort for unknown type of elements in array (using only C code), but my code doesn't work for the last two elements. FOr the following numbers output is '67 45 44 33 5 1 -3 0 -4 -100' I also tried to debug but the only thing I understood is that the last numbers just do not compare. ``` #include #include #include #include typedef int typeEl; void swap(void* a, void* b, size_t sizeOfElem) { void* tmp = calloc(1,sizeOfElem); memcpy(tmp, a, sizeOfElem); memcpy(a, b, sizeOfElem); memcpy(b, tmp, sizeOfElem); } int compare(const void* a, const void* b) { return (*(typeEl*)a - *(typeEl*)b); } void quickSortR(void* a, long N, size_t sizeOfElem, int (*comp)(const void* c, const void* d)) { long i = 0, j = N; void* p = (void *) ((char *)a + (N>>1)*sizeOfElem); do { while ( comp((void *) ((char *)a + i*sizeOfElem), p)>0) i++; while ( comp((void *) ((char *)a + j*sizeOfElem), p)<0) j--; if (i <= j) { swap((void *) ((char *)a + i*…

Accepted Answer

There're 3 problems in your code:

The initialization of `j = N` shall be `j = N - 1`. Reason: later you use the element at position `j` to start comparing, and index of an array in `C` is `[0,N-1]`

The pivot `p` shall not be a pointer but a value. This affects the result when the value at position `p` is swapped but you still regard it as the pivot. Your code seems designed for comparing with pointers, however I could present a quick & ugly(also dangerous!) fix: replace your code:

```
void* p = (void *) ((char *)a + (N>>1)*sizeOfElem);
```

with these:

```
void* p = (void *) ((char *)a + (N>>1)*sizeOfElem);
void *px = malloc(sizeOfElem);
memcpy(px, p, sizeOfElem);
p = px;
```

This line of your code:

```
if ( j > 0) quickSortR((void *)a, j, sizeOfElem, comp);
```

shall be:

```
if ( j > 0) quickSortR((void *)a, j + 1, sizeOfElem, comp);
```

since at the second parameter of `quickSortR` you're passing the length of array.

Fix all these 3 problems and your code shall give correct results.

EDITED: When I say `3 problems` above I mean problems when implementing the algorithm. Other than that there is memory leak within your function `compare` (simply `free(tmp)` to solve it). Also the test `if ( N > i )` could be `if ( N > i + 1 )`. :)

Quicksort doesn't work for the last two numbers

Solution

Problem