DAA - बबल सॉर्ट

बबल सॉर्ट एक प्रारंभिक छँटाई एल्गोरिथ्म है, जो यदि आवश्यक हो, तो आसन्न तत्वों का बार-बार आदान-प्रदान करके काम करता है। जब कोई आदान-प्रदान की आवश्यकता नहीं होती है, तो फ़ाइल को क्रमबद्ध किया जाता है।

सभी छँटाई एल्गोरिदम के बीच यह सबसे सरल तकनीक है।

Algorithm: Sequential-Bubble-Sort (A) 
fori← 1 to length [A] do 
for j ← length [A] down-to i +1 do 
   if A[A] < A[j - 1] then 
      Exchange A[j] ↔ A[j-1]

कार्यान्वयन

voidbubbleSort(int numbers[], intarray_size) { 
   inti, j, temp; 
   for (i = (array_size - 1); i >= 0; i--) 
   for (j = 1; j <= i; j++) 
      if (numbers[j - 1] > numbers[j]) { 
         temp = numbers[j-1]; 
         numbers[j - 1] = numbers[j]; 
         numbers[j] = temp; 
      } 
}

विश्लेषण

यहां, तुलना की संख्या है

1 + 2 + 3 +...+ (n - 1) = n(n - 1)/2 = O(n²)

जाहिर है, ग्राफ से पता चलता है n² बबल की प्रकृति।

इस एल्गोरिथ्म में, तुलना की संख्या डेटा सेट के बावजूद है, अर्थात प्रदान किए गए इनपुट तत्व क्रमबद्ध क्रम में या रिवर्स ऑर्डर में या यादृच्छिक पर हैं।

स्मृति की आवश्यकता

ऊपर वर्णित एल्गोरिथ्म से, यह स्पष्ट है कि बुलबुला प्रकार को अतिरिक्त मेमोरी की आवश्यकता नहीं है।

उदाहरण

Unsorted list:

5 2 1 4 3 7 6

1 ^सेंट पुनरावृति:

5 > 2 swap	2 5 1 4 3 7 6
5 > 1 swap	2 1 5 4 3 7 6
5 > 4 swap	2 1 4 5 3 7 6
5 > 3 swap	2 1 4 3 5 7 6
5 < 7 no swap	2 1 4 3 5 7 6
7 > 6 swap	2 1 4 3 5 6 7

2 ^{एन डी} पुनरावृत्ति:

2 > 1 swap	1 2 4 3 5 6 7
2 < 4 no swap	1 2 4 3 5 6 7
4 > 3 swap	1 2 3 4 5 6 7
4 < 5 no swap	1 2 3 4 5 6 7
5 < 6 no swap	1 2 3 4 5 6 7

3 ^आरडी , 4 ^वें , 5 ^वें और 6 ^वें पुनरावृत्ति में कोई बदलाव नहीं हुआ है ।

आखिरकार,

the sorted list is

1 2 3 4 5 6 7