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 निम्नानुसार होता है-


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

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


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;
         }
      }
   }
}

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


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)

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


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

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

Selection Sort Algorithm
Searching - Internal and External

Data Structure and Algorithmes in Hindiये Article इस वेबसाईट पर Selling हेतु उपलब्‍ध EBook Data Structure and Algorithms in Hindi से लिया गया है। इसलिए यदि ये Article आपके लिए उपयोगी रहा, तो निश्चित रूप से ये पुस्तक भी आपके लिए काफी उपयोगी साबित होगी। 

Data Structure and Algorithms in Hindi | Page: 433 | Format: PDF

BUY NOW DOWNLOAD READ ONLINE

Special Discount Offer

खरीदिए एक से ज्‍यादा EBooks, और पाईए ₹100 से ₹1200 तक का Extra Cash Discount

Discount Coupon Codes