DAA - सम्मिलन क्रमबद्ध करें

सम्मिलन क्रम एक आरोही या अवरोही क्रम में संख्याओं को क्रमबद्ध करने की एक बहुत ही सरल विधि है। यह विधि वृद्धिशील विधि का अनुसरण करती है। यह तकनीक के साथ तुलना की जा सकती है कि गेम खेलने के समय कार्ड कैसे छांटे जाते हैं।

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

Algorithm: Insertion-Sort(A) 
for j = 2 to A.length 
   key = A[j] 
   i = j – 1 
   while i > 0 and A[i] > key 
      A[i + 1] = A[i] 
      i = i -1 
   A[i + 1] = key

विश्लेषण

इस एल्गोरिथ्म का रन टाइम दिए गए इनपुट पर बहुत अधिक निर्भर है।

यदि दी गई संख्याओं को क्रमबद्ध किया जाता है, तो यह एल्गोरिथ्म चलता है O(n)समय। यदि दिए गए नंबर उल्टे क्रम में हैं, तो एल्गोरिथ्म अंदर चलता हैO(n²) समय।

उदाहरण

Unsorted list:

2 13 5 18 14

1^st iteration:

की = एक [२] = १३

[a १] = २ <१३

स्वैप, कोई स्वैप नहीं

2 13 5 18 14

2^nd iteration:

की = एक [३] = ५

एक [२] = १३> ५

स्वैप 5 और 13

2 5 13 18 14

अगला, एक [१] = २ <१३

स्वैप, कोई स्वैप नहीं

2 5 13 18 14

3^rd iteration:

की = एक [४] = १]

[३] = १३ <१ 13,

एक [२] = ५ <१ 5,

[a १] = २ <१ 2

स्वैप, कोई स्वैप नहीं

2 5 13 18 14

4^th iteration:

की = एक [५] = १४

[[४] = १ 14> १४

स्वैप 18 और 14

2 5 13 14 18

अगला, एक [३] = १३ <१४,

एक [२] = ५ <१४,

[a १] = २ <१४

तो, कोई स्वैप नहीं

2 5 13 14 18

आखिरकार,

the sorted list is

2 5 13 14 18