क्यूसॉर्ट

For other uses, see Q sort (disambiguation).

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

इतिहास

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

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

उदाहरण

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

#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 केवल दो पॉइंटर्स को स्वीकार करता है, अतिरिक्त पैरामीटर्स में गुजरता है (उदाहरण के लिए एक तुलनात्मक फ़ंक्शन का उत्पादन करता है जो दो मानों के अंतर से दूसरे मान के साथ तुलना करता है) वैश्विक चर का उपयोग करके किया जाना चाहिए। समस्या को बर्कले सॉफ्टवेयर डिस्ट्रीब्यूशन और GNU यूनिक्स जैसी प्रणालियों द्वारा एक परिचय द्वारा हल किया गया था qsort_r फ़ंक्शन, जो एक अतिरिक्त पैरामीटर को तुलना फ़ंक्शन में पास करने की अनुमति देता है। के दो संस्करण qsort_r अलग तर्क आदेश हैं। C11 (C मानक संशोधन) a को परिभाषित करता है qsort_s अनिवार्य रूप से जीएनयू के समान qsort_r. macOS और FreeBSD libcs ​​में भी शामिल है qsort_b, एक वैरिएंट जो उसी समस्या के वैकल्पिक समाधान के रूप में ब्लॉक (सी भाषा विस्तार), क्लोजर (कंप्यूटर विज्ञान) के अनुरूप का उपयोग करता है।