मेन्यू

उदाहरणों के साथ C ++ में बबल सॉर्ट

bubble sort c with examples

समस्याओं को खत्म करने के लिए हमारे साधन का प्रयास करें

सी ++ में बबल सॉर्ट तकनीक।

बबल सॉर्ट छँटाई तकनीकों में सबसे सरल है।

बबल सॉर्ट तकनीक में, सूची के प्रत्येक तत्व की तुलना उसके आसन्न तत्व से की जाती है। इस प्रकार यदि सूची A में n तत्व हैं, तो A (0) की तुलना A (1) से की जाती है, A (1) की तुलना A (2) और इसी तरह की जाती है।

तुलना करने के बाद यदि पहला तत्व दूसरे से अधिक है, तो दो तत्वों की अदला-बदली की जाती है।

=> विशेषज्ञों से पूरा सी ++ कोर्स के लिए यहां जाएं।

बुलबुले की तरह

आप क्या सीखेंगे:

लिंक की गई सूची c ++ क्या है

बबल सॉर्ट तकनीक

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

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

सामान्य एल्गोरिथम

चरण 1 : I = 0 से N-1 के लिए चरण 2 दोहराएं
चरण 2 : जे = आई + 1 से एन के लिए - मैं दोहराता हूं
चरण 3 : अगर A (J)> A (i)
स्वैप ए (जे) और ए (आई)
(लूप के लिए इनर का अंत)
(अंत अगर पाश के लिए बाहरी)
चरण 4 : बाहर जाएं

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

पहले लूप में, हम 0 से शुरू करते हैंवेंतत्व और अगले लूप में, हम एक आसन्न तत्व से शुरू करते हैं। आंतरिक लूप शरीर में, हम आसन्न तत्वों में से प्रत्येक की तुलना करते हैं और यदि वे क्रम में नहीं हैं तो उन्हें स्वैप करें। बाहरी लूप के प्रत्येक पुनरावृत्ति के अंत में, सबसे भारी तत्व अंत में बुलबुले बनते हैं।

स्यूडोकोड

Procedure bubble_sort (array , N) array – list of items to be sorted N – size of array begin swapped = false repeat for I = 1 to N-1 if array(i-1) > array(i) then swap array(i-1) and array(i) swapped = true end if end for until not swapped end procedure

ऊपर दिया गया बबल सॉर्ट तकनीक के लिए छद्म कोड है। आइए अब हम एक विस्तृत चित्रण का उपयोग करके इस तकनीक का वर्णन करते हैं।

चित्रण

हम आकार 5 की एक सरणी लेते हैं और बुलबुला सॉर्ट एल्गोरिथ्म का वर्णन करते हैं।

बबल सॉर्ट इलस्ट्रेशन - पास 1

बबल सॉर्ट इलस्ट्रेशन - पास 2

बबल चित्रण - पास 3

अर्रे पूरी तरह से छांटे गए।

उपरोक्त चित्र को सारणीबद्ध रूप में संक्षेप में प्रस्तुत किया जा सकता है:

उत्तीर्ण करनाअनारक्षित सूचीतुलनाक्रमबद्ध सूची
{5,0,10,12,15}{10.12}{5,0,10,12,15}
1{10,5,15,0,12}{10.5}{5,10,15,0,12}
{5,10,15,0,12}{10.15}{5,10,15,0,12}
{5,10,15,0,12}{15.0}{5,10,0,15,12}
{5,10,0,15,12}{15.12}{5,10,0,12,15}
दो{5,10,0,12,15}{5,10}{5,10,0,12,15}
{5,10,0,12,15}{{}{5,0,10,12,15}
३{5,0,10,12,15}{5,0}{५,५,१०,१२,१५}
{5,0,10,12,15}{5,10}{5,0,10,12,15}
{5,0,10,12,15}हल

जैसा कि चित्रण में दिखाया गया है, हर पास के साथ, सबसे बड़ा तत्व हर पास के साथ सूची को छांटते हुए अंतिम तक बुलबुले बनाता है। जैसा कि परिचय में बताया गया है, प्रत्येक तत्व की तुलना उसके आसन्न तत्व से की जाती है और क्रम में न होने पर एक दूसरे से अदला-बदली की जाती है।

इस प्रकार जैसा कि ऊपर चित्रण में दिखाया गया है, पहली पास के अंत में, यदि आरोही क्रम में क्रमबद्ध करना है, तो सबसे बड़ा तत्व सूची के अंत में रखा गया है। दूसरे पास के लिए, दूसरा सबसे बड़ा तत्व सूची में दूसरे अंतिम स्थान पर रखा गया है और इसी तरह।

जब हम एन -1 (जहां एन सूची में तत्वों की कुल संख्या है) तक पहुंचते हैं, तो हम पूरी सूची को क्रमबद्ध करेंगे।

Android फोन पर जासूसी करने के लिए app

बबल सॉर्ट तकनीक को किसी भी प्रोग्रामिंग भाषा में लागू किया जा सकता है। हमने नीचे C ++ और Java भाषा का उपयोग करके बबल सॉर्ट एल्गोरिथ्म को लागू किया है।

C ++ उदाहरण

आइए हम बबल सॉर्ट को प्रदर्शित करने के लिए एक प्रोग्रामिंग उदाहरण देखें।

#include using namespace std; int main () { int i, j,temp,pass=0; int a(10) = {10,2,0,14,43,25,18,1,5,45}; cout <<'Input list ... '; for(i = 0; i<10; i++) { cout <

आउटपुट:

इनपुट सूची…

10 2 0 14 43 25 18 1 5 45

क्रमबद्ध तत्व सूची…

0 1 2 5 10 14 18 25 43 45

सूची को सॉर्ट करने के लिए लिए गए पासों की संख्या: 10

जावा उदाहरण

class Main { public static void main(String() args) { int pass = 0; int() a = {10,-2,0,14,43,25,18,1,5,45}; System.out.println('Input List...'); for(int i=0;i<10;i++) { System.out.print(a(i) + ' '); } for(int i=0;i<10;i++) { for (int j=0;j<10;j++) { if(a(i)

आउटपुट:

मैक पर एक टोरेंट फाइल को कैसे खोलें

bubble_sort Java आउटपुट

दोनों कार्यक्रमों में, हमने 10 तत्वों की एक सरणी का उपयोग किया है और हम इसे बबल सॉर्ट तकनीक का उपयोग करके सॉर्ट करते हैं। दोनों कार्यक्रमों में, हमने सरणी के आसन्न तत्वों के माध्यम से दो छोरों को पुनरावृत्त करने के लिए उपयोग किया है।

प्रत्येक पास (बाहरी लूप) के अंत में, सरणी में सबसे बड़ा तत्व सरणी के अंत तक बुदबुदाया जाता है। हम संपूर्ण सरणी को सॉर्ट करने के लिए आवश्यक पास की संख्या भी गिनते हैं।

बबल सॉर्ट एल्गोरिथम की जटिलता विश्लेषण

छद्म कोड और चित्रण से जो हमने ऊपर देखा है, बबल सॉर्ट में, हम पहले पास में एन -1 तुलना करते हैं, दूसरे पास में एन -2 तुलना और इसी तरह।

इसलिए बबल सॉर्ट में तुलना की कुल संख्या है:

I = (n-1) + (n-2) + (n-3) + ... + 3 + 2 + 1

= एन (एन -1) / 2

= ओ (एन)दो) => बबल सॉर्ट तकनीक की समय जटिलता

इस प्रकार बबल सॉर्ट तकनीक के लिए विभिन्न जटिलताएं नीचे दी गई हैं:

सबसे खराब स्थिति समय जटिलताओ (एन 2)
सबसे अच्छा मामला समय जटिलतापर)
औसत समय जटिलताओ (एन 2)
अंतरिक्ष की जटिलताओ (1)

बबल सॉर्ट तकनीक में स्वैपिंग की सुविधा के लिए अस्थायी चर के लिए केवल एक अतिरिक्त मेमोरी स्पेस की आवश्यकता होती है। इसलिए बुलबुला सॉर्ट एल्गोरिथ्म के लिए अंतरिक्ष जटिलता ओ (1) है।

ध्यान दें कि बुलबुला सॉर्ट तकनीक के लिए सबसे अच्छा मामला समय जटिलता तब होगी जब सूची पहले से ही सॉर्ट की गई हो और वह O (n) होगी।

निष्कर्ष

बबल सॉर्ट का मुख्य लाभ एल्गोरिथ्म की सादगी है। बुलबुला क्रम में, हर पास के साथ, सबसे बड़ा तत्व सूची के अंत तक बुलबुले करता है यदि सरणी आरोही क्रम में क्रमबद्ध होती है।

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

सॉर्टिंग तकनीक को लागू करने के लिए सबसे सरल और आसान होने के नाते, बबल सॉर्ट को आमतौर पर दर्शकों को छांटने के लिए लिया जाता है। दूसरे, बबल सॉर्ट का उपयोग कंप्यूटर ग्राफिक्स जैसे कि बहुभुज किनारों को भरने आदि में भी किया जाता है, बहुभुज को अस्तर बनाने के लिए बबल सॉर्ट की आवश्यकता होती है।

हमारे आगामी ट्यूटोरियल में, हम विस्तार से चयन सॉर्ट के बारे में जानेंगे।

=> स्क्रैच से C ++ जानने के लिए यहाँ जाएँ।

अनुशंसित पाठ

^