मानक लाइब्रेरी qsort को स्थिर करना?

Question

मुझे लगता है कि stdlib में अच्छा पुराना qsort फ़ंक्शन स्थिर नहीं है, क्योंकि मैन पेज इसके बारे में कुछ भी नहीं कहता है। इस समारोह के बारे में मैं बात कर रहा हूँ है:

#include <stdlib.h> 
    void qsort(void *base, size_t nmemb, size_t size, 
       int(*compar)(const void *, const void *)); 

मुझे लगता है कि अगर मैं अपने तुलना समारोह बदल भी जो मैं तुलना कर रहा हूं कि का पता शामिल करना है, यह स्थिर हो जाएगा। क्या वो सही है?

उदाहरण के लिए:

int compareFoos(const void* pA, const void *pB) { 
    Foo *pFooA = (Foo*) pA; 
    Foo *pFooB = (Foo*) pB; 

    if(pFooA->id < pFooB->id) { 
     return -1; 
    } else if(pFooA->id > pFooB->id) { 
     return 1; 
    } else if(pA < pB) { 
     return -1;    
    } else if(pB > pA) { 
     return 1; 
    } else { 
     return 0; 
    } 
} 

Answer 1

नहीं है, आपको लगता है कि दुर्भाग्य से पर भरोसा नहीं कर सकते हैं। मान लेते हैं कि आप सरणी है चलो (प्रत्येक रिकॉर्ड में दो क्षेत्रों जाँच लेकिन केवल पहले छँटाई के लिए इस्तेमाल किया क्षेत्र के लिए इस्तेमाल किया):

BBBB,1 
BBBB,2 
AAAA,3 

quicksort bbbb, AAAA के साथ 1, 3 तुलना करने और उन्हें स्वैप, दे रही है हो सकता है:

AAAA,3 
BBBB,2 
BBBB,1 

यदि अगला कदम बीबीबीबी की तुलना करना था, 2 बीबीबीबी के साथ, 1, चाबियाँ समान होंगी और चूंकि बीबीबीबी, 2 में बीबीबीबी से कम पता है, 1, कोई स्वैप नहीं होगा। ऐसा करने के लिए यह सूचक (अपने वर्तमान पता नहीं) के शुरू करने पता संलग्न करने के लिए हो सकता है और प्रकार के रूप में उपयोग कर

AAAA,3 
BBBB,1 
BBBB,2 

एक ही रास्ता: एक स्थिर प्रकार के लिए, आप के साथ समाप्त हो गया हो जाना चाहिए था अच्छी तरह से अन्य चाबियाँ के रूप में। इस तरह, मूल पता सॉर्ट कुंजी का मामूली हिस्सा बन जाता है ताकि BBBB,1 अंततः BBBB,2 से पहले समाप्त हो जाएगा, भले ही दो BBBB लाइनें सॉर्टिंग प्रक्रिया के दौरान जाएं।

Answer 2

विहित समाधान (यानी के लिए स्मृति को आबंटित और भरने) मूल सरणी के तत्वों की ओर इशारा की एक सरणी, और qsort इस नई सरणी, अविवेक की एक अतिरिक्त स्तर का उपयोग करने और सूचक की तुलना मूल्यों पर वापस गिरने बनाना है जब वे जो चीजें इंगित करते हैं वे बराबर होती हैं। इस दृष्टिकोण में संभावित पक्ष लाभ है कि आप मूल सरणी को बिल्कुल संशोधित नहीं करते हैं - लेकिन यदि आप मूल सरणी को अंत में क्रमबद्ध करना चाहते हैं, तो आपको पॉइंटर्स की सरणी में ऑर्डर से मिलान करने की अनुमति देनी होगी qsort रिटर्न।

Answer 3

यह काम नहीं करता है क्योंकि सॉर्ट प्रक्रिया के दौरान, ऑर्डरिंग बदल जाएगी और दो तत्वों में लगातार आउटपुट नहीं होगा। मैं पुराने पुराने क्यूएसओटी स्थिर बनाने के लिए क्या करता हूं, मेरी संरचना के अंदर प्रारंभिक सूचकांक जोड़ना और qsort को पास करने से पहले उस मान को प्रारंभ करना है।

typedef struct __bundle { 
    data_t some_data; 
    int sort_score; 
    size_t init_idx; 
} bundle_t; 

/* 
. 
. 
. 
. 
*/ 

int bundle_cmp(void *ptr1, void *ptr2) { 
    bundle_t *b1, *b2; 
    b1 = (budnel_t *) ptr1; 
    b2 = (budnel_t *) ptr2; 
    if (b1->sort_score < b2->sort_score) { 
     return -1; 
    } 
    if (b1->sort_score > b2->sort_score) { 
     return 1; 
    } 
    if (b1->init_idx < b2->init_idx) { 
     return -1; 
    } 
    if (b1->init_idx > b2->init_idx) { 
     return 1; 
    } 
    return 0; 
} 

void sort_bundle_arr(bundle_t *b, size_t sz) { 
    size_t i; 
    for (i = 0; i < sz; i++) { 
     b[i]->init_idx = i; 
    } 
    qsort(b, sz, sizeof(bundle_t), bundle_cmp); 
}