3 रास्ता quicksort (सी कार्यान्वयन)

Question

मैं implement को कुछ एल्गोरिदम शुद्ध जेनेरिक का उपयोग करके सी का उपयोग कर सी। मैं 3-तरफा quicksort के साथ चिपक जाता हूं लेकिन किसी भी तरह कार्यान्वयन सही आउटपुट नहीं देता है। आउटपुट लगभग सॉर्ट किया गया लेकिन कुछ चाबियाँ नहीं हैं जहां यह होना चाहिए। कोड नीचे है। अग्रिम में धन्यवाद।

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <time.h> 

static void swap(void *x, void *y, size_t size) { 
    void *tmp = malloc(size); 

    memcpy(tmp, x, size); 
    memcpy(x, y, size); 
    memcpy(y, tmp, size); 

    free(tmp); 
} 

static int cmpDouble(const void *i, const void *j) { 
    if (*(double *)i < *(double *)j) 
     return 1; 
    else if (*(double *)i == *(double *)j) 
     return 0; 
    else 
     return -1; 
} 

void qsort3way(void *base, int lo, int hi, size_t size, 
       int (*cmp)(const void *, const void *)) { 
    if (hi <= lo) 
     return; 
    else { 
     char *ptr = (char*)base; 
     char *v = ptr + lo * size; 

     int lt = lo, gt = hi; 
     int i = lo; 
     while (i <= gt) { 
      int c = cmp(v, ptr + i * size); 
      if (c < 0) 
       swap(ptr + (lt++) * size, ptr + (i++) * size, size); 
      else if (c > 0) 
       swap(ptr + i * size, ptr + (gt--) * size, size);  
      else 
       i++; 
     } 

     qsort3way(base, lo, lt - 1, size, cmp); 
     qsort3way(base, gt + 1, hi, size, cmp); 
    }  
} 

int main(void) { 
    int i; 
    double *d = (double*)malloc(sizeof(double) * 100); 

    for (i = 0; i < 100; i++) 
     d[i] = (double)rand(); 

    qsort3way(d, 0, 100 -1, sizeof(double), cmpDouble); 

    for (i = 0; i < 100; i++) 
     printf("%.10lf\n", d[i]); 

    free(d); 
    return 0; 
} 

नमूना उत्पादन:

 
    41.0000000000 
    153.0000000000 
    288.0000000000 
    2082.0000000000 
    292.0000000000 
    1869.0000000000 
    491.0000000000 
    778.0000000000 
    1842.0000000000 
    6334.0000000000 
    2995.0000000000 
    8723.0000000000 
    3035.0000000000 
    3548.0000000000 
    4827.0000000000 
    3902.0000000000 
    4664.0000000000 
    5436.0000000000 
    4966.0000000000 
    5537.0000000000 
    5447.0000000000 
    7376.0000000000 
    5705.0000000000 
    6729.0000000000 
    6868.0000000000 
    7711.0000000000 
    9961.0000000000 
    8942.0000000000 
    9894.0000000000 
    9040.0000000000 
    9741.0000000000 

Answer 1

book link कि आप @JohnBollinger को उपलब्ध कराने को पढ़ने के बाद। मैं समझता हूं कि आपका एल्गोरिदम कैसे काम करता है। आपकी समस्या यह है कि आपका पिवोट चलता है, लेकिन आप v के मान को नहीं बदलते हैं।

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 

typedef void qsort3way_swap(void *a, void *b); 
typedef int qsort3way_cmp(void const *a, void const *b); 

static void qsort3way_aux(char *array_begin, char *array_end, size_t size, 
          qsort3way_cmp *cmp, qsort3way_swap *swap) { 
    if (array_begin < array_end) { 
    char *i = array_begin + size; 
    char *lower = array_begin; 
    char *greater = array_end; 
    while (i < greater) { 
     int ret = cmp(lower, i); 
     if (ret < 0) { 
     swap(i, lower); 
     i += size; 
     lower += size; 
     } else if (ret > 0) { 
     greater -= size; 
     swap(i, greater); 
     } else { 
     i += size; 
     } 
    } 
    qsort3way_aux(array_begin, lower, size, cmp, swap); 
    qsort3way_aux(greater, array_end, size, cmp, swap); 
    } 
} 

static void qsort3way(void *array_begin, void *array_end, size_t size, 
         qsort3way_cmp *cmp, qsort3way_swap *swap) { 
    qsort3way_aux(array_begin, array_end, size, cmp, swap); 
} 

static void swap_int_aux(int *a, int *b) { 
    int tmp = *a; 
    *a = *b; 
    *b = tmp; 
} 

static void swap_int(void *a, void *b) { swap_int_aux(a, b); } 

static int cmp_int_aux(int const *a, int const *b) { 
    if (*a < *b) { 
    return 1; 
    } else if (*a > *b) { 
    return -1; 
    } else { 
    return 0; 
    } 
} 

static int cmp_int(void const *a, void const *b) { return cmp_int_aux(a, b); } 

static void print_int(char const *intro, int const *array, size_t const size) { 
    printf("%s:", intro); 
    for (size_t i = 0; i < size; i++) { 
    printf(" %d", array[i]); 
    } 
    printf("\n"); 
} 

#define SIZE 42 

int main(void) { 
    int array[SIZE]; 

    srand((unsigned int)time(NULL)); 
    for (size_t i = 0; i < SIZE; i++) { 
    array[i] = rand() % SIZE - SIZE/2; 
    } 

    print_int("before", array, SIZE); 

    qsort3way(array, array + SIZE, sizeof *array, cmp_int, swap_int); 

    print_int("after", array, SIZE); 
} 

नोट:: अनुकूलन int i = lo + 1; और char *i = array_begin + size; अनिवार्य हैं आपका धुरी मैं तुम्हें एक "उचित" समाधान प्रस्तावित सूचकांक lt

char *ptr = base; 

int lt = lo, gt = hi; // lt is the pivot 
int i = lo + 1; // we don't compare pivot with itself 
while (i <= gt) { 
    int c = cmp(ptr + lt * size, ptr + i * size); 
    if (c < 0) { 
    swap(ptr + lt++ * size, ptr + i++ * size, size); 
    } 
    else if (c > 0) 
    swap(ptr + i * size, ptr + gt-- * size, size); 
    else 
    i++; 
} 
qsort3way(base, lo, lt - 1, size, cmp); 
qsort3way(base, gt + 1, hi, size, cmp); 

पर है। क्योंकि जिस मामले में फ़ंक्शन की समीक्षा pivot != pivot की तुलना में होती है, इससे अनंत असर होगा। यह कैसे संभव होगा?

1. फ़ंक्शन सीएमपी बग है।
2. double में अजीब शक्ति है ... एक डबल खुद के बराबर नहीं हो सकता है! (-nan)।

Answer 2

कार्यान्वयन सही परिणाम नहीं देता है क्योंकि यह गलत है। वास्तव में, बहुत बुरी तरह गलत, यह देखते हुए कि यह एक तीन-तरफा quicksort होना चाहिए और एक नियमित नहीं है।

एक मूल समस्या यह है कि आपने बिट विभाजन को छोड़ दिया है जहां आप मुख्य विभाजन लूप के बाद पिवट को अपनी उचित स्थिति में ले जाते हैं। मानक क्विकॉर्ट के लिए, कार्यान्वयन विवरण के आधार पर, लूप के बाद एक अतिरिक्त स्वैप या असाइनमेंट की आवश्यकता होती है। तीन-तरफा क्विकॉर्ट के लिए जिसमें एक या दो अतिरिक्त लूप शामिल होते हैं, संभावित रूप से स्थानांतरित करने के लिए -वृत्त मूल्यों को उनके पदों के बराबर। आप सूचक द्वारा धुरी तत्व को ट्रैक, मूल्य से नहीं है, और आप (कभी कभी) मूल मूल्य बाहर विभाजन पाश के पाठ्यक्रम में है कि स्थिति से स्वैप:

एक और अधिक घातक समस्या एक @Stargateur पहले बताया है।

इसके अलावा, आपका मुख्य विभाजन लूप तीन-तरफा quicksort के लिए भी गलत है। जब आप पिवट के बराबर तत्व का सामना करते हैं तो आप इसे जगह में छोड़ देते हैं, लेकिन आपको इसके बजाय इसे एक छोर पर ले जाने की आवश्यकता होती है (या किसी प्रकार के सहायक भंडारण के लिए, यदि आप उस मेमोरी लागत को लेने के इच्छुक हैं) तो कि आप अंत में बीच में उस कदम को कर सकते हैं। एक मायने में, पिछली समस्या इस का एक विशेष मामला है - आप पिवट वैल्यू के लिए जगह आरक्षित नहीं कर रहे हैं। इसे ठीक करने से पिछली समस्या भी हल हो जाएगी।

मुझे यकीन नहीं है कि आपने अपना कार्यान्वयन तैयार करने के लिए किस संदर्भ का उपयोग किया था, या आपने इसे स्क्रैच से बनाया है, लेकिन गीक्स के लिए गीक्स में सी ++ (लेकिन बहुत अधिक सी) implementation for int arrays है जिसे आप देखना चाहते हैं।