Quicksort не работает для последних двух чисел

Question

Задача состояла в том, чтобы написать quicksort для неизвестного типа элементов в массиве (используя только код C), но мой код не работает для двух последних элементов. Выход следующих чисел: '67 45 44 33 5 1 -3 0 -4 -100 ' Я также пытался отлаживать, но единственное, что я понял, это то, что последние цифры просто не сравниваются.

#include <stdio.h> 
#include <conio.h> 
#include <stdlib.h> 
#include <memory.h> 
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*sizeOfElem), (void *) ((char *)a + j*sizeOfElem), sizeOfElem); 
     i++; j--; 
    } 
    } while (i<=j); 


    if (j > 0) quickSortR((void *)a, j, sizeOfElem, comp); 
    if (N > i) quickSortR((void *) ((char *)a + i*sizeOfElem), N-i,sizeOfElem, comp); 
} 
int main() { 
    int n; 
    int m[10] = {1,-3,5,-100,45,33,44,67,-4, 0}; 

    quickSortR((void *)m, 10, sizeof(int),compare);    
    for (n=0; n<10; n++) 
     printf ("%d ",m[n]); 
    return 0; 
} 

Любой может посоветовать? Thx за помощь!

Answer 1

Там вы 3 проблемы в вашем коде:

1. Инициализация j = N должна быть j = N - 1. Причина: позже вы используете элемент в позиции j начать сравнение и индекс массива в C является [0,N-1]

2. Поворотная p не должен быть указателем, а значение. Это влияет на результат, когда значение в позиции p заменяется, но вы по-прежнему считаете его опорным. Ваш код кажется предназначен для сравнения с указателями, однако я мог бы представить быстрый & уродливую (также опасно!) Исправление:
   заменить код:

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

   с ними:

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

3. Эта линия ваш код:

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

   должно быть:

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

   так как при втором параметре quickSortR вы передаете длину массива.

Исправить все эти 3 проблемы, и ваш код должен дать правильные результаты.

EDITED:
Когда я говорю 3 problems выше, я имею в виду проблемы при реализации алгоритма. Кроме того, есть утечка памяти внутри вашей функции compare (просто free(tmp) для ее решения). Также тест if (N > i) может быть if (N > i + 1).
:)