क्यूसॉर्ट

For other uses, see क्यूसॉर्ट (विसंदिग्धीकरण).

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

इतिहास

1972 में ली मैकमोहन द्वारा एक क्यूसॉर्ट फलन लागू किया गया था।यह 3 यूनिक्स संस्करण में एक लाइब्रेरी फलन के रूप में मौजूद था,, लेकिन तब यह एक समुच्चायक उपनेमका थी। ए सी संस्करण, मोटे तौर पर मानक सी संस्करण के अंतरापृष्ठ के साथ, संस्करण 6 यूनिक्स में था। इसे 1983 में बर्कले सॉफ्टवेयर वितरण के लिए फिर से लिखा गया था।फलन एएनएसआई सी (1989) में मानकीकृत किया गया था।

1991 में, बेल लैब्स के कर्मचारियों ने देखा कि क्यूसॉर्ट के मैकमोहन और बीएसडी संस्करण कुछ सरल निविष्ट के लिए द्विघात समय का उपयोग करेंगे।। इस प्रकार जॉन बेंटले (अभिकलित्र वैज्ञानिक) और डगलस मैक्लॉयय ने एक नया तेज और अधिक मजबूत कार्यान्वयन तैयार किया। मैक्लॉयय बाद में 1998 में एक अधिक जटिल द्विघात-समय निविष्ट का उत्पादन करेगा, जिसे एंटीक्विकसॉर्ट कहा जाता है। यह फलन प्रतिकूल आँकडे़ ऑन-द-फ्लाई का निर्माण करता है।

उदाहरण

सी कोड का निम्न भाग दिखाता है कि क्यूसॉर्ट का उपयोग करके पूर्णांकों की सूची को कैसे क्रमबद्ध किया जाए।

#include <stdlib.h>

/* Comparison function. Receives two generic (void) pointers to the items under comparison. */
int compare_ints(const void *p, const void *q) {
    int x = *(const int *)p;
    int y = *(const int *)q;

    /* Avoid return x - y, which can cause undefined behaviour
       because of signed integer overflow. */
    if (x < y)
        return -1;  // Return -1 if you want ascending, 1 if you want descending order. 
    else if (x > y)
        return 1;   // Return 1 if you want ascending, -1 if you want descending order.

    return 0;
    // All the logic is often alternatively written:
    return (x > y) - (x < y);
}

/* Sort an array of n integers, pointed to by a. */
void sort_ints(int *a, size_t n) {
    qsort(a, n, sizeof(*a), compare_ints);
}

एक्सटेंशन

मूल के तुलनात्मक कार्य के बाद से qsort केवल दो संकेत को स्वीकार करता है, अतिरिक्त मापदण्ड में गुजरता है (उदाहरण के लिए एक तुलनात्मक फलन का उत्पादन करता है जो दो मानों के अंतर से दूसरे मान के साथ तुलना करता है) वैश्विक चर का उपयोग करके किया जाना चाहिए। समस्या को बर्कले सॉफ्टवेयर वितरण और जीएनयू यूनिक्स जैसी प्रणालियों द्वारा एक समाविष्‍ट qsort_r फलन द्वारा हल किया गया था, जो तुलना फलन में एक अतिरिक्त मापदण्ड पारित करने की अनुमति देता है। के दो संस्करण qsort_r अलग तर्क आदेश हैं। C11 (सी मानक संशोधन) को परिभाषित करता है qsort_s अनिवार्य रूप से जीएनयू के समान qsort_r. मैक ओएस और फ्रीबीएसडी लिबिक्स ​​में भी शामिल है qsort_b, एक वैरिएंट जो उसी समस्या के वैकल्पिक समाधान के रूप में ब्लॉक (सी भाषा विस्तार), क्लोजर (अभिकलित्र विज्ञान) के अनुरूप का उपयोग करता है।