2016-04-25 144 views
1

我想做一個通用快速排序功能,我不明白我在做什麼,因爲它不能正常工作。
這裏是我的代碼:通用快速排序不工作由於某種原因

#include <stdlib.h> 
#include <string.h> 
#include <stdio.h> 
#include <stdbool.h> 
#include <assert.h> 

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

    int cmp(const void *c1, const void *c2) 
{ 
    assert(c1 && c2); 
    int a = *(const int*)c1; 
    int b = *(const int*)c2; 
    if (a > b) return 1; 
    if (a < b) return -1; 
    return 0; 
} 

void swap(void *a, void *b, size_t size) { 
    char tmp[size]; 

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

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

雖然原來的快速排序功能,無需我試圖使它通用是:

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; 
    } 

我使用這個主():

int main(){ 

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

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

    return 0; 
} 

現在我們都同意輸出應該是:

1, 3, 4, 5, 6, 7 

這確實是我運行NOT generic函數時得到的結果。
當我跑我的通用(上)函數我得到這樣的:

5 | 1 | 4 | 7 | 6 | 3 | 


你都在那裏我錯了什麼想法? :)

+0

你試過調試器嗎?或者打印中間結果? (或qsort函數) –

+0

@MohitJain非常難以調試所有這些空白。 Eclipse不會顯示當前值。你知道另一種調試方式嗎? –

+0

谷歌這個「如何調試小C代碼」 –

回答

-1
#include <stdlib.h> 
#include <string.h> 
#include <stdio.h> 


int integerCompare(const void *c1, const void *c2) // use this to compare int 
{ 
    int a = *(const int*) c1; 
    int b = *(const int*) c2; 
    if (a > b) { 
     return 1; 
    } else if(a < b) { 
     return -1; 
    } else { 
     return 0; 
    } 
} 


int characterCompare(const void *c1, const void *c2) // use this to compare char 
{ 
    char a = *(const int*) c1; 
    char b = *(const int*) c2; 
    if (a > b) { 
     return 1; 
    } else if(a < b) { 
     return -1; 
    } else { 
     return 0; 
    } 
} 



void swap(void *a, void *b, size_t size) { 
    // instead of using an array, use a void pointer and malloc 
    void* tmp = malloc(size); 
    memcpy(tmp, a, size); 
    memcpy(a, b, size); 
    memcpy(b, tmp, size); 
    free(tmp); // free the allocated space 
} 

void quick_sort(void* a, int n, int size, int (*cmp)(const void*, const void*)) 
{ 
    int b = 1; 
    int t = n - 1; 
    if (n < 2) { 
     return; 
    } 
    swap(a, a + (n/2) * size, size); // &a[0] == a 
    // you do not need that p variable .. its value is not being modified 
    while(b <= t) { 
     while(t >= b && cmp(a + t*size, a) >= 0) 
     t--; 
     while(b <= t && cmp(a + b*size, a) < 0) 
     b++; 
     if (b < t) 
     swap(a + size * (b++), a + size * (t--), size); 
    } 
    swap(a, a + t * size, size); 
    quick_sort(a, t, size, cmp); 
    n= n - t - 1; 
    quick_sort(a + (t + 1)*size, n, size, cmp); 
} 

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

    quick_sort(c, 6, sizeof(c[0]), &integerCompare); 
    for (int i=0;i<6;i++) { 
     printf("%d | ", c[i]); 
    } 
    printf("\n"); 
    quick_sort(b, 6, sizeof(b[0]), &characterCompare); 
    for (int i=0;i<6;i++) { 
     printf("%c | ", b[i]); 
    } 

    return 0; 
} 
+0

@downvoter如果我可能會問,代碼是不是適合你,或者是什麼問題? – jboockmann

相關問題