क्विकसॉर्ट एल्गोरिथ्म Javaलिपि

सॉर्टिंग क्या है?

सॉर्टिंग कुछ और नहीं बल्कि तत्वों को उस क्रम में व्यवस्थित करना है जिसे हम चाहते हैं। आपने अपने स्कूल या कॉलेज के दिनों में इसे पढ़ा होगा। जैसे संख्याओं को छोटे से बड़े (आरोही) या बड़े से छोटे (अवरोही) में व्यवस्थित करना, जिसे हमने अब तक देखा है और इसे सॉर्टिंग कहा जाता है।

डिफ़ॉल्ट सॉर्टिंग Javaलिपि

जैसा कि पहले उल्लेख किया गया है, Javaस्क्रिप्ट में क्रमबद्ध करें ()आइए हम [5,3,7,6,2,9] जैसे तत्वों की कुछ सरणी के साथ एक उदाहरण लेते हैं और इस सरणी तत्वों को आरोही क्रम में क्रमबद्ध करना चाहते हैं। बस कॉल करें क्रमबद्ध करें () आइटम सरणी पर और यह सरणी तत्वों को आरोही क्रम में सॉर्ट करता है।

कोड:

var items = [5,3,7,6,2,9];
console.log(items.sort());
//prints [2, 3, 5, 6, 7, 9]

डिफ़ॉल्ट sort() के स्थान पर त्वरित sort चुनने का क्या कारण है? Javaलिपि

हालाँकि sort() हमें मनचाहा परिणाम देता है, लेकिन समस्या यह है कि यह सरणी तत्वों को किस तरह से क्रमबद्ध करता है। Javaस्क्रिप्ट का उपयोग सम्मिलन सॉर्ट by क्रोम का V8 इंजन और मर्ज़ सॉर्ट by Mozilla Firefox और Safari.

लेकिन, अगर आपको बड़ी संख्या में तत्वों को सॉर्ट करने की आवश्यकता है तो यह उपयुक्त नहीं है। इसलिए, समाधान बड़े डेटासेट के लिए क्विक सॉर्ट का उपयोग करना है।

तो, पूरी तरह से समझने के लिए, आपको यह जानना होगा कि त्वरित सॉर्ट कैसे काम करता है और आइए अब हम इसे विस्तार से देखें।

त्वरित सॉर्ट क्या है?

त्वरित क्रम इस प्रकार है विभाजन और जीत एल्गोरिदम। यह कुछ शर्तों के आधार पर तत्वों को छोटे भागों में विभाजित करता है और उन विभाजित छोटे भागों पर सॉर्ट ऑपरेशन करता है। इसलिए, यह बड़े डेटासेट के लिए अच्छी तरह से काम करता है। तो, यहाँ सरल शब्दों में क्विक सॉर्ट कैसे काम करता है, इसके चरण दिए गए हैं।

1. सबसे पहले एक तत्व का चयन करें जिसे बुलाया जाना है धुरी तत्व।
2. इसके बाद, सभी सारणी तत्वों की तुलना चयनित पिवट तत्व से करें और उन्हें इस प्रकार व्यवस्थित करें कि पिवट तत्व से छोटे तत्व उसके बाईं ओर हों तथा पिवट से बड़े तत्व उसके दाईं ओर हों।
3. अंत में, पिवट तत्व के बाएं और दाएं तरफ के तत्वों पर समान ऑपरेशन करें।

तो, यह क्विक सॉर्ट की मूल रूपरेखा है। क्विक सॉर्ट करने के लिए एक-एक करके निम्नलिखित चरणों का पालन करना होगा।

क्विकसॉर्ट कैसे काम करता है?

1. सबसे पहले खोजें "धुरी" सरणी में तत्व.
2. बायें पॉइंटर को सारणी के प्रथम तत्व से प्रारंभ करें।
3. दायाँ पॉइंटर सारणी के अंतिम तत्व से प्रारंभ करें।
4. बाएं पॉइंटर से पॉइंट करने वाले तत्व की तुलना करें और अगर यह पिवट तत्व से कम है, तो बाएं पॉइंटर को दाईं ओर ले जाएं (बाएं इंडेक्स में 1 जोड़ें)। ऐसा तब तक जारी रखें जब तक कि बाईं ओर का तत्व पिवट तत्व से बड़ा या बराबर न हो जाए।
5. दाएँ पॉइंटर से पॉइंट करने वाले एलिमेंट की तुलना करें और अगर यह पिवट एलिमेंट से बड़ा है, तो दाएँ पॉइंटर को बाईं ओर ले जाएँ (दाएँ इंडेक्स से 1 घटाएँ)। ऐसा तब तक जारी रखें जब तक दायाँ साइड एलिमेंट पिवट एलिमेंट से कम या बराबर न हो जाए।
6. जाँच करें कि बायाँ पॉइंटर दाएँ पॉइंटर से छोटा या बराबर है, फिर इन पॉइंटर्स के स्थानों में तत्वों को बदलें।
7. बाएँ पॉइंटर को बढ़ाएँ और दाएँ पॉइंटर को घटाएँ।
8. यदि बाएं पॉइंटर का सूचकांक दाएं पॉइंटर के सूचकांक से अभी भी कम है, तो प्रक्रिया को दोहराएं; अन्यथा बाएं पॉइंटर का सूचकांक लौटाएं।

तो, आइए इन चरणों को एक उदाहरण के साथ देखें। आइए हम उन तत्वों की सरणी पर विचार करें जिन्हें हमें क्रमबद्ध करने की आवश्यकता है [5,3,7,6,2,9]।

पिवट तत्व निर्धारित करें

लेकिन क्विक सॉर्ट के साथ आगे बढ़ने से पहले, पिवट एलिमेंट का चयन करना एक प्रमुख भूमिका निभाता है। यदि आप पहले एलिमेंट को पिवट एलिमेंट के रूप में चुनते हैं, तो यह सॉर्टेड ऐरे में सबसे खराब प्रदर्शन देता है। इसलिए, हमेशा बीच वाले एलिमेंट (ऐरे की लंबाई को 2 से विभाजित करके) को पिवट एलिमेंट के रूप में चुनना उचित होता है और हम ऐसा ही करते हैं।

यहां त्वरित सॉर्ट करने के चरण दिए गए हैं जिन्हें एक उदाहरण [5,3,7,6,2,9] के साथ दिखाया जा रहा है।

1 कदम: धुरी को मध्य तत्व के रूप में निर्धारित करें। तो, 7 धुरी तत्व है.

2 कदम: बाएं और दाएं पॉइंटर्स को क्रमशः सरणी के पहले और अंतिम तत्व के रूप में शुरू करें। इसलिए, बायां पॉइंटर किस ओर इशारा कर रहा है 5 इंडेक्स 0 पर और दायाँ पॉइंटर इशारा कर रहा है 9 सूचकांक 5 पर.

3 कदम: बाएं पॉइंटर पर मौजूद तत्व की तुलना पिवट तत्व से करें। चूंकि, 5 < 6, बाएं पॉइंटर को इंडेक्स 1 पर दाईं ओर शिफ्ट करें।

4 कदम: अब भी 3 <6 है इसलिए बाएं पॉइंटर को दाईं ओर एक और इंडेक्स पर ले जाएं। तो अब 7 > 6 बाएं पॉइंटर को बढ़ाना बंद करें और अब बायां पॉइंटर इंडेक्स 2 पर है।

5 कदम: अब, दाएँ पॉइंटर पर मान की तुलना पिवट तत्व से करें। चूँकि 9 > 6 है, दाएँ पॉइंटर को बाईं ओर ले जाएँ। अब चूँकि 2 < 6 है, दाएँ पॉइंटर को हिलाना बंद करें।

6 कदम: बाएं और दाएं पॉइंटर्स पर मौजूद दोनों मानों को एक दूसरे के साथ स्वैप करें।

7 कदम: दोनों पॉइंटर्स को एक कदम और आगे ले जाएँ।

8 कदम: चूँकि 6 = 6 है, पॉइंटर्स को एक कदम और आगे ले जाएँ तथा जैसे ही बायाँ पॉइंटर दाएँ पॉइंटर को पार करे, रुक जाएँ और बाएँ पॉइंटर का इंडेक्स लौटा दें।

इसलिए, यहां उपरोक्त दृष्टिकोण के आधार पर, हमें तत्वों की अदला-बदली और सरणी को विभाजित करने के लिए कोड लिखने की आवश्यकता है जैसा कि ऊपर दिए गए चरणों में बताया गया है।

दो नंबरों को बदलने के लिए कोड Javaलिपि

function swap(items, leftIndex, rightIndex){
    var temp = items[leftIndex];
    items[leftIndex] = items[rightIndex];
    items[rightIndex] = temp;
}

उपरोक्त चरणों में बताए अनुसार विभाजन करने के लिए कोड

function partition(items, left, right) {
    var pivot   = items[Math.floor((right + left) / 2)], //middle element
        i       = left, //left pointer
        j       = right; //right pointer
    while (i <= j) {
        while (items[i] < pivot) {
            i++;
        }
        while (items[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(items, i, j); //swap two elements
            i++;
            j--;
        }
    }
    return i;
}

पुनरावर्ती ऑपरेशन निष्पादित करें

एक बार जब आप ऊपर दिए गए चरणों को पूरा कर लेंगे, तो बाएं पॉइंटर का इंडेक्स वापस आ जाएगा और हमें सरणी को विभाजित करने और उस हिस्से पर क्विक सॉर्ट करने के लिए इसका उपयोग करना होगा। इसलिए, इसे डिवाइड एंड कॉनकर एल्गोरिदम कहा जाता है।

इसलिए, त्वरित सॉर्ट तब तक किया जाता है जब तक कि बाएं सरणी और दाएं सरणी के सभी तत्व सॉर्ट नहीं हो जाते।

नोट: त्वरित सॉर्टिंग उसी सारणी पर की जाती है तथा इस प्रक्रिया में कोई नई सारणी नहीं बनाई जाती।

तो, हमें इसे कॉल करने की आवश्यकता है विभाजन () ऊपर बताया गया है और उसके आधार पर हम इसे विभाजित करते हैं सरणी भागों में। तो यहाँ वह कोड है जहाँ आप इसका उपयोग करते हैं,

function quickSort(items, left, right) {
    var index;
    if (items.length > 1) {
        index = partition(items, left, right); //index returned from partition
        if (left < index - 1) { //more elements on the left side of the pivot
            quickSort(items, left, index - 1);
        }
        if (index < right) { //more elements on the right side of the pivot
            quickSort(items, index, right);
        }
    }
    return items;
}
// first call to quick sort
var result = quickSort(items, 0, items.length - 1);

त्वरित सॉर्ट कोड पूरा करें

var items = [5,3,7,6,2,9];
function swap(items, leftIndex, rightIndex){
    var temp = items[leftIndex];
    items[leftIndex] = items[rightIndex];
    items[rightIndex] = temp;
}
function partition(items, left, right) {
    var pivot   = items[Math.floor((right + left) / 2)], //middle element
        i       = left, //left pointer
        j       = right; //right pointer
    while (i <= j) {
        while (items[i] < pivot) {
            i++;
        }
        while (items[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(items, i, j); //sawpping two elements
            i++;
            j--;
        }
    }
    return i;
}

function quickSort(items, left, right) {
    var index;
    if (items.length > 1) {
        index = partition(items, left, right); //index returned from partition
        if (left < index - 1) { //more elements on the left side of the pivot
            quickSort(items, left, index - 1);
        }
        if (index < right) { //more elements on the right side of the pivot
            quickSort(items, index, right);
        }
    }
    return items;
}
// first call to quick sort
var sortedArray = quickSort(items, 0, items.length - 1);
console.log(sortedArray); //prints [2,3,5,6,7,9]

नोट: त्वरित सॉर्ट समय जटिलता के साथ चलता है ओ(एनलॉगएन)।