Bubble Sort Algorithm in Data Structure with Example

Bubble Sort Algorithm in Data Structure with Example: किसी Data Structure के सभी Data को एक व्यवस्थित क्रम में रखना Sorting कहलाता है। ये दो प्रकार की होती है, आरोही क्रम में या अवरोही क्रम में। आरोही क्रम में सबसे कम मान का Data List की शुरूआत में व सबसे अधिक मान का Data List के अंत में Store होता है, जबकि अवरोही क्रम में ठीक इसके विपरीत क्रिया होती है। यानी सबसे अधिक मान का Data सबसे पहले व सबसे कम मान का Data List में सबसे बाद में Store होता है। Data Processing के अंतर्गत Sorting को मुख्‍यत: तीन भागों में बांटा गया है-

Bubble Sort

यह अत्यधिक काम में आने वाली सबसे साधारण तकनीक है। इसमें किसी भी Array के प्रथम मान की तुलना Array के दूसरे मान से करते हैं।

• यदि Array का दूसरा मान प्रथम मान से बडा है, तो आरोही क्रम में जमाने के लिये दूसरे Data को प्रथम स्थान पर रख दिया जाता है व प्रथम स्थान के Data को दूसरे स्थान पर।
• फिर Array के दूसरे मान की तुलना तीसरे मान से करते हैं और यदि तीसरा मान दूसरे मान से बडा है तो तीसरे मान की जगह दूसरा मान व दूसरे मान की जगह तीसरा मान रख दिया जाता है।
• यदि दूसरा मान तीसरे मान से बडा नहीं है तो Array के दूसरे व तीसरे मानों के स्थान में कोई परिवर्तन नहीं किया जाता है।

मानों के स्थान परिवर्तन का ये क्रम तब तक चलाया जाता है, जब तक कि सारे मान आरोही क्रम में व्यवस्थित ना हो जाए। ये क्रम N-1 बार चलाया जाता है, जहां N Array के कुल मानों की संख्‍या है। Bubble Sort का Algorithm निम्नानुसार है-

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

1. START
2. REPEATE FOR I = 1 To N – 1 STEP I = I + 1 [ Outer Loop]
3. REPEATE FOR J = 1 To N – I STEP J = J + 1 [ Inner Loop ]
4. IF LArray[ J ] > LArray[ J + 1 ]
5. LArray[ J ] = LArray[ J + 1 ]    [ Interchange Data Items ]
   [ End of Inner Loop ]
   [ End of Outer Loop ]
6. End

Bubble Sort तब बहुत उपयोगी होता है जब List लगभग Sorted हो और केवल कुछ ही इकाईयों की Sorting करनी हो। जब इकाईयों की संख्‍या अधिक होती है, तब इस विधी में Program की गति काफी कम हो जाती है, क्योंकि N-1 बार List को व्यवस्थित करना पडता है। इस Algorithm का प्रयोग करते हुए हम निम्नानुसार एक Function बना सकते हैं जिसे किसी भी Main Function में Call किया जा सकता है। Function निम्नानुसार है-

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

इस Function में दो Argument Calling Function से आते हैं। पहले Argument में एक Array का Base Address आता है, जिसके विभिन्न Elements को Sorting Order में रखना है और दूसरे Argument में Array की Size प्रदान की जाती है। चूंकि इस Function में Array का Base Address आता है इसलिए इस Function द्वारा जो Sorting होती है वह Calling Function के Array की Sorting होती है।

Bubble Sort के Algorithm से हम समझ सकते हैं कि ये Algorithm List में से सबसे छोटे Data Item को Search करता है और उस Data Element को उसकी Final Position पर Place कर देता है। फिर दूसरे Iteration में दूसरे Element से शुरू करता है और बचे हुए Elements में से सबसे छोटे Data Item को खोज कर उसकी Final Position पर भेजता है।

Algorithm में हम देख सकते हैं कि यदि Data Items की संख्‍या n हो तो Outer Loop n बार चलता है और Outer Loop के आधार पर Smallest Data Find करने के लिए Inner Loop n-i बार Comparison करता है। यानी कुल Comparisons की संख्‍या निम्नानुसार होती है-

Elements E( n )   =  i

= 1 To n SIGMA( n-i )
=  (n-1) + (n-2) + (n-2) + . . . + 2 + 1
=  n(n-1)/2
=  O(n²) – O(n/2)
=  O(n²)

सारांश में कहें तो Bubble Sort Algorithm की Complexity O(n²) होती है।