JavaScript में इंसर्शन सॉर्ट कैसे लागू करें?

इंसर्शन सॉर्ट (Insertion Sort)

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

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

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

एल्गोरिदम ट्रेस

दिया गया एरे: 0, -3, 5, 8, 2, 7, 6

• इटरेशन 0 - केवल अनसॉर्टेड एरे: 0, -3, 5, 8, 2, 7, 6
• इटरेशन 1 - की = -3 (इंडेक्स 1)। -3 < 0, इसलिए बाएं जाता है: -3, 0, 5, 8, 2, 7, 6
• इटरेशन 2 - की = 5। बाएं मानों (-3, 0) से तुलना, सही स्थान पर: -3, 0, 5, 8, 2, 7, 6
• इटरेशन 3 - की = 8। बाएं मानों से तुलना: -3, 0, 5, 8, 2, 7, 6
• इटरेशन 4 - की = 2। बाएं मानों से तुलना और सॉर्टेड स्थान पर: -3, 0, 2, 5, 8, 7, 6
• अंतिम सॉर्टेड एरे: -3, 0, 2, 5, 6, 7, 8

JavaScript कार्यान्वयन

<html>
<head>
<script>
  function iSort(array) {
    for (var p = 1; p < array.length; p++) {
      if (array[p] < array[0]) {
        array.unshift(array.splice(p, 1)[0]);
      } else if (array[p] > array[p-1]) {
        continue;
      } else {
        for (var q = 1; q < p; q++) {
          if (array[p] > array[q-1] && array[p] < array[q]) {
            array.splice(q, 0, array.splice(p, 1)[0]);
          }
        }
      }
    }
    return array;
  }
  document.write(iSort([0, -3, 5, 8, 2, 7, 6]));
</script>
</body>
</html>

आउटपुट

-3,0,2,5,6,7,8

समय जटिलता