बबल सॉर्ट एल्गोरिथम का परिचय

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

इस लेख में, आप बबल सॉर्ट एल्गोरिथ्म के काम करने के बारे में जानेंगे, बबल सॉर्ट का छद्म कोड एल्गोरिथ्म, इसका समय और स्थान जटिलता, और विभिन्न प्रोग्रामिंग भाषाओं जैसे C++, Python, C, and. में इसका कार्यान्वयन जावास्क्रिप्ट।

बबल सॉर्ट एल्गोरिथम कैसे काम करता है?

बबल सॉर्ट सबसे सरल सॉर्टिंग एल्गोरिदम है जो बार-बार सूची के माध्यम से कदम उठाता है, आसन्न तत्वों की तुलना करता है, और यदि वे गलत क्रम में हैं तो उन्हें स्वैप कर देता है। इस अवधारणा को एक उदाहरण की सहायता से अधिक कुशलता से समझाया जा सकता है। निम्नलिखित तत्वों के साथ एक क्रमबद्ध सरणी पर विचार करें: {16, 12, 15, 13, 19}।

उदाहरण:

यहां आसन्न तत्वों की तुलना की जाती है और यदि वे आरोही क्रम में नहीं हैं, तो उनकी अदला-बदली की जाती है।

बबल सॉर्ट एल्गोरिथम का स्यूडोकोड

स्यूडोकोड मेंबबल सॉर्ट एल्गोरिथ्म के रूप में व्यक्त किया जा सकता है:

बबलसॉर्ट (एआर [], आकार)
// प्रत्येक सरणी तत्व तक पहुंचने के लिए लूप
i = 0 से आकार -1 के लिए करें:
// सरणी तत्वों की तुलना करने के लिए लूप
j = 0 से आकार-i-1 के लिए करें:
// आसन्न तत्वों की तुलना करें
अगर एआर [जे] > एआर [जे + 1] तो
// उन्हें स्वैप करें
स्वैप (एआर [जे], एआर [जे + 1])
अगर अंत
अंत के लिए
अंत के लिए
समाप्त

उपरोक्त एल्गोरिथ्म सभी तुलनाओं को संसाधित करता है, भले ही सरणी पहले से ही क्रमबद्ध हो। यदि आंतरिक लूप किसी भी स्वैप का कारण नहीं बनता है तो इसे एल्गोरिदम को रोककर और अनुकूलित किया जा सकता है। यह एल्गोरिथम के निष्पादन समय को कम करेगा।

इस प्रकार, अनुकूलित बबल सॉर्ट एल्गोरिथ्म का छद्म कोड इस प्रकार व्यक्त किया जा सकता है:

बबलसॉर्ट (एआर [], आकार)
// प्रत्येक सरणी तत्व तक पहुंचने के लिए लूप
i = 0 से आकार -1 के लिए करें:
// जांचें कि क्या स्वैपिंग होती है
अदला-बदली = असत्य
// सरणी तत्वों की तुलना करने के लिए लूप
j = 0 से आकार-i-1 के लिए करें:
// आसन्न तत्वों की तुलना करें
अगर एआर [जे] > एआर [जे + 1] तो
// उन्हें स्वैप करें
स्वैप (एआर [जे], एआर [जे + 1])
अदला-बदली = सच
अगर अंत
अंत के लिए
// यदि कोई तत्व स्वैप नहीं किया गया था, जिसका अर्थ है कि सरणी अब सॉर्ट की गई है, तो लूप को तोड़ दें।
अगर (बदली नहीं) तो
टूटना
अगर अंत
अंत के लिए
समाप्त

बबल सॉर्ट एल्गोरिथम का समय जटिलता और सहायक स्थान

बबल सॉर्ट एल्गोरिथम की सबसे खराब स्थिति समय जटिलता ओ (एन ^ 2) है। यह तब होता है जब सरणी अवरोही क्रम में होती है और आप इसे आरोही क्रम में या इसके विपरीत क्रमबद्ध करना चाहते हैं।

बबल सॉर्ट एल्गोरिथम की सर्वोत्तम-केस समय जटिलता O(n) है। यह तब होता है जब सरणी पहले से ही क्रमबद्ध होती है।

सम्बंधित: बिग-ओ नोटेशन क्या है?

बबल सॉर्ट एल्गोरिथम की औसत-केस समय जटिलता O(n^2) है। यह तब होता है जब सरणी के तत्व अव्यवस्थित क्रम में होते हैं।

बबल सॉर्ट एल्गोरिथ्म के लिए आवश्यक सहायक स्थान O(1) है।

C++ बबल सॉर्ट एल्गोरिथम का कार्यान्वयन

बबल सॉर्ट एल्गोरिथम का C++ कार्यान्वयन नीचे दिया गया है:

// सी ++ का कार्यान्वयन
// अनुकूलित बबल सॉर्ट एल्गोरिथ्म
#शामिल 
नेमस्पेस एसटीडी का उपयोग करना;
// बबल सॉर्ट करने का कार्य
शून्य बबलसॉर्ट (इंट एआर [], इंट साइज) {
// सरणी के प्रत्येक तत्व तक पहुंचने के लिए लूप
के लिए (int i=0; मैं // यह जांचने के लिए चर कि क्या अदला-बदली होती है
बूल अदला-बदली = झूठा;
// सरणी के दो आसन्न तत्वों की तुलना करने के लिए लूप
के लिए (इंट जे = 0; जे < (आकार-i-1); जे++) {
// दो आसन्न सरणी तत्वों की तुलना करना
अगर (गिरफ्तारी [जे]> गिरफ्तारी [जे + 1]) {
// दोनों तत्वों को स्वैप करें यदि वे हैं
// सही क्रम में नहीं
इंट अस्थायी = एआर [जे];
एआर [जे] = एआर [जे + 1];
एआर [जे + 1] = अस्थायी;
अदला-बदली = सच;
}
}
// यदि किसी भी तत्व की अदला-बदली नहीं की गई है, तो इसका मतलब है कि सरणी अब क्रमबद्ध है,
// फिर लूप को तोड़ें।
अगर (स्वैप किया गया == झूठा) {
टूटना;
}
}
}
// सरणी के तत्वों को प्रिंट करता है
शून्य प्रिंटअरे (इंट एआर [], इंट साइज) {
के लिए (इंट आई = 0; मैं cout << गिरफ्तार [i] << "";
}
कोउट << एंडल;
}
मुख्य प्रवेश बिंदु() {
int arr[] = {16, 12, 15, 13, 19};
// सरणी की लंबाई का पता लगाना
int आकार = आकार (गिरफ्तारी) / आकार (गिरफ्तारी [0]);
// दिए गए अवर्गीकृत सरणी को प्रिंट करना
cout << "बिना क्रमबद्ध सरणी:" << endl;
प्रिंटअरे (गिरफ्तारी, आकार);
// कॉलिंग बबलसॉर्ट () फ़ंक्शन
बबलसॉर्ट (गिरफ्तारी, आकार);
// सॉर्ट किए गए सरणी को प्रिंट करना
cout << "आरोही क्रम में क्रमबद्ध सरणी:" << endl;
प्रिंटअरे (गिरफ्तारी, आकार);
वापसी 0;
}

आउटपुट:

क्रमबद्ध सरणी: 
16 12 15 13 19 
आरोही क्रम में क्रमबद्ध सरणी:
12 13 15 16 19

बबल सॉर्ट एल्गोरिथम का पायथन कार्यान्वयन

बबल सॉर्ट एल्गोरिथम का पायथन कार्यान्वयन नीचे दिया गया है:

# पायथन का कार्यान्वयन implementation
# अनुकूलित बबल सॉर्ट एल्गोरिथ्म
# बबल सॉर्ट करने का कार्य
डीईएफ़ बबलसॉर्ट (गिरफ्तारी, आकार):
# सूची के प्रत्येक तत्व तक पहुंचने के लिए लूप
मैं सीमा में (आकार -1) के लिए:
# अदला-बदली होने पर जाँच करने के लिए चर
अदला-बदली = असत्य
# सूची के दो आसन्न तत्वों की तुलना करने के लिए लूप
रेंज में j के लिए (आकार-i-1):
# दो आसन्न सूची तत्वों की तुलना
अगर गिरफ्तारी [जे]> गिरफ्तारी [जे + 1]:
अस्थायी = गिरफ्तारी [जे]
एआर [जे] = एआर [जे + 1]
गिरफ्तारी [जे + 1] = अस्थायी
अदला-बदली = सच
# यदि किसी भी तत्व की अदला-बदली नहीं हुई है, तो इसका मतलब है कि सूची अब क्रमबद्ध है,
#फिर लूप तोड़ो।
अगर स्वैप किया गया == गलत:
टूटना
# सूची के तत्वों को प्रिंट करता है
डीईएफ़ प्रिंटअरे (गिरफ्तारी):
गिरफ्तारी में तत्व के लिए:
प्रिंट (तत्व, अंत = "")
प्रिंट ("")
गिरफ्तारी = [१६, १२, १५, १३, १९]
# सूची की लंबाई ढूँढना
आकार = लेन (गिरफ्तारी)
# दी गई अवर्गीकृत सूची को प्रिंट करना
प्रिंट ("अनक्रमित सूची:")
प्रिंटअरे (गिरफ्तारी)
# कॉलिंग बबलसॉर्ट () फ़ंक्शन
बबलसॉर्ट (गिरफ्तारी, आकार)
# सॉर्ट की गई सूची को प्रिंट करना
प्रिंट ("आरोही क्रम में क्रमबद्ध सूची:")
प्रिंटअरे (गिरफ्तारी)

आउटपुट:

क्रमबद्ध सूची:
16 12 15 13 19 
आरोही क्रम में क्रमबद्ध सूची:
12 13 15 16 19

सम्बंधित: पायथन में फॉर लूप्स का उपयोग कैसे करें

सी बबल सॉर्ट एल्गोरिदम का कार्यान्वयन

बबल सॉर्ट एल्गोरिथम का C कार्यान्वयन नीचे दिया गया है:

// सी का कार्यान्वयन
// अनुकूलित बबल सॉर्ट एल्गोरिथ्म
#शामिल 
#शामिल 
// बबल सॉर्ट करने का कार्य
शून्य बबलसॉर्ट (इंट एआर [], इंट साइज) {
// सरणी के प्रत्येक तत्व तक पहुंचने के लिए लूप
के लिए (int i=0; मैं // यह जांचने के लिए चर कि क्या अदला-बदली होती है
बूल अदला-बदली = झूठा;
// सरणी के दो आसन्न तत्वों की तुलना करने के लिए लूप
के लिए (इंट जे = 0; जे < (आकार-i-1); जे++) {
// दो आसन्न सरणी तत्वों की तुलना करना
अगर (गिरफ्तारी [जे]> गिरफ्तारी [जे + 1]) {
// दोनों तत्वों को स्वैप करें यदि वे हैं
// सही क्रम में नहीं
इंट अस्थायी = एआर [जे];
एआर [जे] = एआर [जे + 1];
एआर [जे + 1] = अस्थायी;
अदला-बदली = सच;
}
}
// यदि किसी भी तत्व की अदला-बदली नहीं की गई है, तो इसका मतलब है कि सरणी अब क्रमबद्ध है,
// फिर लूप को तोड़ें।
अगर (स्वैप किया गया == झूठा) {
टूटना;
}
}
}
// सरणी के तत्वों को प्रिंट करता है
शून्य प्रिंटअरे (इंट एआर [], इंट साइज) {
के लिए (इंट आई = 0; मैं प्रिंटफ ("% d", गिरफ्तारी [i]);
}
प्रिंटफ ("\ ⁠n");
}
मुख्य प्रवेश बिंदु() {
int arr[] = {16, 12, 15, 13, 19};
// सरणी की लंबाई का पता लगाना
int आकार = आकार (गिरफ्तारी) / आकार (गिरफ्तारी [0]);
// दिए गए अवर्गीकृत सरणी को प्रिंट करना
प्रिंटफ ("बिना क्रमबद्ध सरणी: \ ⁠n");
प्रिंटअरे (गिरफ्तारी, आकार);
// कॉलिंग बबलसॉर्ट () फ़ंक्शन
बबलसॉर्ट (गिरफ्तारी, आकार);
// सॉर्ट किए गए सरणी को प्रिंट करना
प्रिंटफ ("आरोही क्रम में क्रमबद्ध सरणी: \ ⁠n");
प्रिंटअरे (गिरफ्तारी, आकार);
वापसी 0;
}

आउटपुट:

क्रमबद्ध सरणी: 
16 12 15 13 19 
आरोही क्रम में क्रमबद्ध सरणी: 
12 13 15 16 19

बबल सॉर्ट एल्गोरिथम का जावास्क्रिप्ट कार्यान्वयन

बबल सॉर्ट एल्गोरिथम का जावास्क्रिप्ट कार्यान्वयन नीचे दिया गया है:

// जावास्क्रिप्ट का कार्यान्वयन
// अनुकूलित बबल सॉर्ट एल्गोरिथ्म
// बबल सॉर्ट करने का कार्य
फ़ंक्शन बबलसॉर्ट (गिरफ्तारी, आकार) {
// सरणी के प्रत्येक तत्व तक पहुंचने के लिए लूप
के लिए (चलो मैं = 0; मैं// यह जांचने के लिए चर कि क्या अदला-बदली होती है
वर अदला-बदली = झूठा;
// सरणी के दो आसन्न तत्वों की तुलना करने के लिए लूप
के लिए (चलो जे = 0; जे// दो आसन्न सरणी तत्वों की तुलना करना
अगर (गिरफ्तारी [जे]> गिरफ्तारी [जे + 1]) {
// दोनों तत्वों को स्वैप करें यदि वे हैं
// सही क्रम में नहीं
चलो अस्थायी = गिरफ्तारी [जे];
एआर [जे] = एआर [जे + 1];
एआर [जे + 1] = अस्थायी;
अदला-बदली = सच;
}
// यदि किसी भी तत्व की अदला-बदली नहीं की गई है, तो इसका मतलब है कि सरणी अब क्रमबद्ध है,
// फिर लूप को तोड़ें।
अगर (स्वैप किया गया == झूठा) {
टूटना;
}
}
}
}
// सरणी के तत्वों को प्रिंट करता है
फ़ंक्शन प्रिंटअरे (गिरफ्तारी, आकार) {
के लिए (चलो मैं = 0; मैंदस्तावेज़.लिखें (गिरफ्तारी [i] + "");
}
दस्तावेज़.लिखें ("
")
}
वर गिरफ्तारी = [१६, १२, १५, १३, १९];
// सरणी की लंबाई का पता लगाना
वर आकार = गिरफ्तारी लंबाई;
// दिए गए अवर्गीकृत सरणी को प्रिंट करना
दस्तावेज़.लिखें ("बिना क्रमबद्ध सरणी: 
");
प्रिंटअरे (गिरफ्तारी, आकार);
// कॉलिंग बबलसॉर्ट () फ़ंक्शन
बबलसॉर्ट (गिरफ्तारी, आकार);
// सॉर्ट किए गए सरणी को प्रिंट करना
document.write ("आरोही क्रम में क्रमबद्ध सरणी: 
");
प्रिंटअरे (गिरफ्तारी, आकार);

आउटपुट:

क्रमबद्ध सरणी:
16 12 15 13 19
आरोही क्रम में क्रमबद्ध सरणी:
12 15 13 16 19

अब आप बबल सॉर्ट एल्गोरिथम के कार्य को समझते हैं

बबल सॉर्ट सबसे सरल सॉर्टिंग एल्गोरिथम है और इसका उपयोग मुख्य रूप से सॉर्टिंग की नींव को समझने के लिए किया जाता है। बबल सॉर्ट को पुनरावर्ती रूप से भी लागू किया जा सकता है, लेकिन यह ऐसा करने के लिए कोई अतिरिक्त लाभ प्रदान नहीं करता है।

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

"हैलो वर्ल्ड" स्क्रिप्ट का उपयोग करके पायथन के साथ शुरुआत कैसे करें

पायथन आज उपयोग की जाने वाली सबसे लोकप्रिय प्रोग्रामिंग भाषाओं में से एक है। अपनी पहली पायथन लिपि के साथ आरंभ करने के लिए इस ट्यूटोरियल का अनुसरण करें।

आगे पढ़िए

लेखक के बारे में