ジェネリッククイックソートが機能しない

Question

ジェネリッククイックソート機能を使用しようとしていますが、正しく動作していないため、何が問題なのか理解できません。私はそれが一般的なようにしようのないオリジナルのクイックソート機能は、ですが

typedef bool (*CmpFunction)(void*, void*); 

void swap(void *c1, void *c2) 
{ 
    assert(c1 && c2); 
    int c = *(int*)c1; 
    *(int*)c1 = *(int*)c2; 
    *(int*)c2 = c; 
} 

void quick_sort(void* a, int n, CmpFunction swap) 
{ 
    int p, b = 1, t = n - 1; 
    if (n < 2) 
     return; 
    swap((char*)a, (char*)a+n/2); 
    p = *(int*)a; 
    while(b <= t) { 
     while(t >= b && (char*)a + t >= p) 
     t--; 
     while(b <= t && (char*)a + b < p) 
     b++; 
     if (b < t) 
     swap((char*)a+(b++), (char*)a+(t--)); 
    } 
    swap((char*)a, (char*)a+t); 
    quick_sort(a, t, swap); 
    n=n-t-1; 
    quick_sort(a + t + 1, n, swap); 
} 

：

int main(){ 

    char b[] = {'a','t','b','c','y','s'}; 
    int c[] = {1,4,6,3,5,7}; 
    quick_sort(c, 6, &swap); 

    for (int i=0;i<6;i++) 
     printf("%d | ", c[i]); 

    return 0; 
} 

：私はこのメイン（）を使用してい

void quick_sort(int a[], int n) 
{ 
    int p, b = 1, t = n - 1; 
    if (n < 2) 
     return; 
    swap(&a[0], &a[n/2]); 
    p = a[0]; 
    while(b <= t) { 
     while(t >= b && a[t] >= p) 
     t--; 
     while(b <= t && a[b] < p) 
     b++; 
     if (b < t) 
     swap(&a[b++], &a[t--]); 
    } 
    swap(&a[0], &a[t]); 
    quick_sort(a, t); 
    n=n-t-1; 
    quick_sort(a + t + 1, n); 
} 

void swap(int *c1, int *c2) 
    { 
     int c = *c1; 
     *c1 = *c2; 
     *c2 = c; 
    } 

ここ は私のコードです

出力は次のとおりです：

1, 3, 4, 5, 6, 7 

これは実際にはNOT generic関数を実行したときに得られるものです。
ジェネリック（上位）関数を実行すると、基本的にはゴミ箱になります。

あなたはすべて私が間違っているアイディアを持っていますか？ :)

Answer 1

最も明らかな問題：あなたの入力データは、その後*ポインタCHARに強制的にvoid *型のポインタに型変換int配列、次のとおりです。

swap((char*)a, (char*)a+n/2); 

ここでは、ポインタchar *型にそれを強制します、それにn/2を飛び越す。
char *は1バイトサイズの要素の配列です
int *はコンパイラ/ OS/CPUに応じて2,4,8バイトの要素の配列です。

So char * a +1、voidは、最初の配列の最初の要素の2番目のバイトを返します。

Answer 2

C言語があまり適切でないことをしようとしています。あなたがそれをしたい場合は、pointer arithmeticsについての背景知識が必要です。

具体的に、TサイズN（sizeof(T) == N）を有するタイプであるT *、あなたのサイズを知らなくてもデータアレイ上で動作する一般的な機能を持っていないことを意味

T * ptr; 
ptr = (T *) 0x0100; 
ptr = ptr + 1; 
// ptr now has value 0x100 + N 

用配列要素の

quick_sortとswapの機能を書き換えて、sizeパラメータを組み込むことをお勧めします。ポインタをchar *にキャストし、sizeパラメータを使用して関数が正しく機能するようにします。例swapの関数が続きます。

void swap(void * c1, void * c2, size_t size) { 
    char tmp[size]; // temporary buffer big enough to contain c1 data 
    memcpy(tmp, c1, size); 
    memcpy(c1, c2, size); 
    memcpy(c2, tmp, size); 
} 

変更するquick_sortは、練習として残っています:)。あなたのデータのサイズがわからないとき、あなたはdst = srcの代わりにmemcpy(dst, src, size)を使用しなければならないことかかわらず、あなたが代わりにa1 >= a2のとあなたのポインタアクセスがsizeを掛けなければならないことをmemcmp(a1, a2, size) >= 0を使用しなければならない、覚えておいてください（quick_sortから抜粋すると、次の）：

EDIT：@Schwernはコメントでなぜmemcmp()を使用しても動作しない可能性があります。未知のサイズとフォーマット（endianness、float X int）の値を比較するには、おそらく一般的な比較関数が必要です（これはおそらく書き込み不可能です）。それは、私たちをこの仕事のためにCの不適切な状態に戻すことになります。

void quick_sort(void *a, int n, size_t size) { 
    char[size] p; 
    int b = 1, t = n - 1; 
    if(n < 2) 
     return; 
    // Using new swap with 'size' parameter 
    swap(&a[0], &((char *)a)[n/2 * size], size); 
    // or swap((char *)a + 0, (char*)a + (n/2 * size), size); 
    memcpy(p, a, size); 
    while(b <= t) { 
     while(t >= b && memcmp((char *)a[t * size], p, size) >= 0) { 
    ... 
} 

ラスタマクロを書き込んで、サイズパラメータをquick_sort関数に渡すことができます。

#define QSORT(arr, n) quick_sort((arr), (n), sizeof((arr)[0])) 

Answer 3

qsortは、一般的なソート機能です。配列、配列内の要素のサイズ、要素の数、比較関数を渡します。

ソート関数は、各要素の幅を知る必要があるため、ポインタの算術演算を正しく実行する必要があります。 charの配列は1要素あたり1バイトになります。 intの配列はおそらく4バイトです。 doubleはchar配列の8 base[4]がbase + 4*1あるだろうが、それはintアレイのbase + 4*4です。最終的にbase[n]はbase + (n * width)です。

は、要素内のデータについての仮定を回避するために、またはあなたがそれらをソートする方法、 compareは、ソートのための要素を比較するために使用されます。 a > b場合は a == bと > 0場合 < 0 a < b場合、 0を返します。これにより、ほとんどの数字では return a - bのように簡単になります。

整数比較するための関数の例：スワップ機能に渡す必要はありません

int cmp_int(const void* _a, const void* _b) { 
    /* Do the casting separately for clarity */ 
    int *a = (int *)_a; 
    int *b = (int *)_b; 

    return *a - *b; 
} 

を。単一のスワップ関数が機能する要素のサイズを知っている限り、 @HonzaRemeš' answerの作品です。念頭に置いてこのすべてで

void swap(void * a, void * b, size_t size) { 
    /* Temp buffer large enough to contain an element */ 
    char tmp[size]; 

    memcpy(tmp, a, size); 
    memcpy(a, b, size); 
    memcpy(b, tmp, size); 
} 

、あなたの関数は、要素サイズ（すなわち。width）を与えられていないので、それは正しく、アレイ内を移動することはできません。また、不必要に関数swapを渡していますが、要素のサイズを知っていれば、これは必要ありません。そして、要素を比較する適切な比較関数が欠けています。物事を比較してソートすることができない場合、ジェネリックソート機能のほとんどではありません。