कॉम्ब सॉर्ट

कॉम्ब सॉर्ट

Comb sort with shrink factor k=1.24733
Class	Sorting algorithm
Data structure	Array
Worst-case performance	$O(n^{2})$
Best-case performance	$\Theta (n\log n)$
Average performance	$\Omega (n^{2}/2^{p})$, where p is the number of increments
Worst-case space complexity	$O(1)$

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

nist.gov की "डिमिनिशिंग इंक्रीमेंट सॉर्ट" परिभाषा में 'कॉम्ब सॉर्ट' शब्द का उल्लेख डेटा के पुनरावृत्त पास को देखने के रूप में किया गया है, जहां कॉम्ब के दांत स्पर्श करते हैं; पहला शब्द डोनाल्ड नुथ से जुड़ा है।

एल्गोरिदम

मूल विचार कछुओं, या सूची के अंत के पास छोटे मूल्यों को खत्म करना है, क्योंकि बबल सॉर्ट में ये सॉर्टिंग को काफी धीमा कर देते हैं। खरगोश, सूची की शुरुआत में बड़े मान, बबल सॉर्ट में कोई समस्या पैदा नहीं करते हैं।

बबल सॉर्ट में, जब किन्हीं दो तत्वों की तुलना की जाती है, तो उनमें हमेशा 1 का अंतर (दूसरे से दूरी) होता है। कॉम्ब सॉर्ट का मूल विचार यह है कि अंतर 1 से अधिक हो सकता है। बबल सॉर्ट का आंतरिक लूप, जो वास्तविक स्वैप करता है, को इस तरह संशोधित किया जाता है कि स्वैप किए गए तत्वों के बीच का अंतर कम हो जाता है (बाहरी लूप के प्रत्येक पुनरावृत्ति के लिए) सिकुड़न कारक k के चरण: [n/k, n/k², n/k³, ..., 1].

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

सिकुड़न कारक का कॉम्ब छंटाई की दक्षता पर बहुत प्रभाव पड़ता है। 200,000 से अधिक यादृच्छिक सूचियों पर अनुभवजन्य परीक्षण के बाद मूल लेख के लेखकों द्वारा k = 1.3 को आदर्श सिकुड़न कारक के रूप में सुझाया गया है। बहुत छोटा मान अनावश्यक रूप से कई तुलनाएँ करके एल्गोरिदम को धीमा कर देता है, जबकि बहुत बड़ा मान कछुओं से प्रभावी ढंग से निपटने में विफल रहता है, जिससे उसे 1 गैप आकार के साथ कई पास की आवश्यकता होती है।

घटते अंतराल के साथ बार-बार सॉर्टिंग पास का पैटर्न शेलसॉर्ट के समान है, लेकिन शेलसॉर्ट में सरणी को अगले सबसे छोटे अंतराल पर जाने से पहले प्रत्येक पास को पूरी तरह से सॉर्ट किया जाता है। कॉम्ब सॉर्ट के पास तत्वों को पूरी तरह से सॉर्ट नहीं करते हैं। यही कारण है कि शेलसॉर्ट#गैप अनुक्रमों में लगभग 2.2 का बड़ा इष्टतम सिकुड़न कारक होता है।

छद्मकोड

फ़ंक्शन कॉम्बसॉर्ट (सरणी इनपुट) है

    गैप�:= इनपुट.साइज // गैप साइज आरंभ करें
    सिकुड़न�:= 1.3  // गैप सिकुड़न कारक सेट करें
    क्रमबद्ध:=झूठा

    सॉर्ट करते समय लूप = गलत
        // अगली कॉम्ब के लिए गैप वैल्यू अपडेट करें
        अंतराल�:= फर्श(अंतराल / सिकुड़न)
        यदि गैप ≤ 1 है तो
            अंतराल�:= 1
            क्रमबद्ध�:= सत्य // यदि इस पास में कोई स्वैप नहीं है, तो हमारा काम हो गया
        अगर अंत

        // इनपुट सूची पर एकल कॉम्ब
        मैं�:= 0
        लूप जबकि i + गैप < इनपुट.साइज   // समान विचार के लिए शैल सॉर्ट  देखें
            यदि इनपुट[i] > इनपुट[i+gap] तो
                स्वैप (कंप्यूटर विज्ञान)(इनपुट[i], इनपुट[i+गैप])
                क्रमबद्ध:=झूठा
                // यदि यह असाइनमेंट लूप के भीतर कभी नहीं होता है,
                  // तो कोई अदला-बदली नहीं हुई है और सूची क्रमबद्ध है।
             अगर अंत
    
             मैं�:= मैं + 1
         अंत पाश
     अंत पाश
अंत समारोह

पायथन कोड

साथ ही, दो त्वरित पायथन (प्रोग्रामिंग भाषा) कार्यान्वयन: सूची (या सरणी, या अन्य परिवर्तनीय प्रकार जहां उस पर उपयोग किए गए संचालन भाषा को समझ में आता है) पर काम करता है, दूसरा उसी स्थान पर समान मानों के साथ सूची बनाता है दिया गया डेटा और उसे सॉर्ट करने के बाद लौटाता है (बिल्डिन के समान)। sorted समारोह)।

from math import floor

def combsort_inplace(data):
    length = len(data)
    shrink = 1.3
    gap = length
    sorted = False
    while not sorted:
        gap = floor(gap / shrink)
        if gap <= 1:
            sorted = True
            gap = 1
        # equivalent to `i = 0; while (i + gap) < length: ...{loop body}... i += 1`
        for i in range(length - gap):
            sm = gap + i
            if data[i] > data[sm]:
                # because Python is very nice, this accomplishes the swap
                data[i], data[sm] = data[sm], data[i]
                sorted = False


def combsort(data):
    length = len(data)
    shrink = 1.3
    gap = length
    out = list(data)
    is_sorted = False
    while not is_sorted:
        gap = floor(gap / shrink)
        if gap <= 1:
            is_sorted = True
            gap = 1
        for i in range(length - gap):
            sm = gap + i
            if out[i] > out[sm]:
                out[i], out[sm] = out[sm], out[i]
                is_sorted = False
    return out

यह भी देखें

• बबल सॉर्ट, आम तौर पर धीमी एल्गोरिथ्म, कॉम्ब सॉर्ट का आधार है।
• कॉकटेल प्रकार , या द्विदिशात्मक बबल सॉर्ट, बबल सॉर्ट का रूप है जो कछुओं की समस्या का भी समाधान करता है, यद्यपि कम प्रभावी ढंग से।