Insertion Sort in Data Structure

Insertion Sort in Data Structure in Hindi – इस Method में सम्पूर्ण List को दो भागों Sorted Part व Unsorted Part मे बांटा जाता है। List के Unsorted Part से एक इकाई लेकर Sorted Part में उपयुक्त स्थान पर रखते हैं। यह प्रक्रिया तब तक चलाते हैं जब तक कि Unsorted Part की सभी इकाईयां Sorted Part में व्‍यवस्थित नहीं हो जाती।

इस Method में दो पद होते हैं। Sorted भाग को पढ़ कर उस स्थान को चिन्हित करना होता है जहां पर Unsorted भाग से इकाई लाकर Insert करवाना है। इस प्रक्रिया में इकाई के लिये स्थान बनाने के लिये शेष इकाईयों को Right Side में Shift करना होता है। उसके बाद बनाए गए स्थान में इकाई को प्रवेश करवा देते हैं। इस Method का Algorithm निम्नानुसार होता है-

[code]
Here LArray[N] is an Array with N Elements. 
This Algorithm SORTS the Data Items of the Array

START
REPEATE FOR I = 1 To N – 1 STEP I = I + 1 [ Outer Loop ]
REPEATE FOR J = 0 To I STEP J = J + 1 [ Inner Loop ]
IF LArray[ J ] > LArray[ I ]
TEMP = LARRAY[ J ]
LArray[ J ] = LArray[ I ]
REPEATE FOR K = I To J STEP K = K + 1 [ Inner Loop ]
LARRAY[ K ] = LARRAY[ K – 1 ]
LARRAY[ K + 1 ] = TEMP
     [ End of Inner Loop ]
     [ End of Inner Loop ]
     [ End of Outer Loop ]
End
[/code]

इस विधि से Sorting तब की जानी चाहिये जब इकाईयों की संख्‍या कम होती है। जब इकाईयों की संख्‍या अधिक होती है, तब ये विधि ठीक नहीं रहती क्योंकि इकाईयों के लिये जगह बनाने में समय लगता है जिससे Program की गति कम हो जाती है। इस Algorithm की Complexity में कम से कम n – 1 बार Comparison करना पडता है। इस Algorithm का प्रयोग करके हम निम्नानुसार एक Function बना सकते हैं जिसे किसी भी Program में Use किया जा सकता है-

[code]
void sort(int *Array, int size)
{
   int i, j, k, temp;
   for(i=0; i<size; i++)
   {
      for(j=0; j<i; j++)
      {
      if(Array[j]>Array[i])
         {
             temp = Array[j];
            Array[j] = Array[i];
            for(k=i; k>j; k--)
            Array[k] = Array[k-1];
            Array[k+1] = temp;
         }
      }
   }
}
[/code]

Insertion Algorithm का प्रयोग तब किया जा सकता है जब Data Items n की संख्‍या कम हो। इस Algorithm का Inner Loop i-1 Comparisons करता है। यानी-

[code]
Elements E( n )
=    i = 1 To n SIGMA( i-1 )
=    1 + 2 + 3 + . . . + n-1
=    n(n-1)/2
=    O(n2) – O(n/2)
=    O(n2)
[/code]

Average Case में इस Algorithm की Complexity को निम्नानुसार दर्शाया जा सकता है-

[code]
Elements E( n )   
=    i = 1 To n SIGMA( i-1 )/2
=    (1 + 2 + 3 + . . . + n-1)/2
=    n(n-1)/4
=    O(n2)
[/code]

हम देख सकते हैं कि दोनों ही स्थितियों में इस Algorithm की Complexity O(n²) होती है। (Insertion Sort in Data Structure in Hindi)