[Powered by Google Translate] [बुलबुला तरह] [जैक्सन STEINKAMP हार्वर्ड विश्वविद्यालय] [इस CS50 है. CS50TV] बुलबुला तरह एक छँटाई एल्गोरिथ्म का एक उदाहरण है - कि है, तत्वों का एक सेट में छंटनी करने के लिए एक प्रक्रिया आरोही या अवरोही क्रम. उदाहरण के लिए, यदि आप एक सरणी तरह चाहता था संख्या से मिलकर [3, 5, 2, 9], बुलबुला तरह के एक सही कार्यान्वयन लौटेंगे क्रमबद्ध [2, 3, 5, 9] सरणी आरोही क्रम में. अब, मैं pseudocode में व्याख्या कैसे एल्गोरिथ्म काम करता जा रहा हूँ. 

चलो कहते हैं कि हम 5 पूर्णांकों की एक सूची छँटाई कर रहे हैं - 3, 2, 9, 6, और 5. एल्गोरिथ्म पहले दो तत्वों, 3 और 2 पर देख द्वारा शुरू होता है, और जाँच अगर वे एक दूसरे के सापेक्ष आदेश से बाहर रहे हैं. वे हैं - तीन दो से अधिक है. आरोही क्रम में हो सकता है, वे अन्य तरह के आसपास होना चाहिए. इसलिए, हम उन्हें स्वैप. [2, 3, 9, 6, 5]: अब सूची इस तरह लग रहा है. 

अगला, हम दूसरे और तीसरे तत्वों, 3 और 9 पर दिखेगा. वे सही क्रम में एक दूसरे के रिश्तेदार हैं. यही कारण है, 3 9 से कम इतना एल्गोरिथ्म उन्हें स्वैप नहीं करता है. अगला, हम 9 और 6 में देखो. वे आदेश से बाहर रहे हैं. 

तो, हम उन्हें स्वैप है क्योंकि 9 6 से अधिक है की जरूरत है. अन्त में, हम पिछले दो integers, 9 और 5 को देखो. वे आदेश के बाहर हैं, तो वे बदली किया जाना चाहिए. सूची के माध्यम से पहले पूरा पास के बाद, [2, 3, 6, 5, 9]: यह इस तरह दिखता है. बुरा नहीं है. यह लगभग हल है. लेकिन हम सूची के माध्यम से फिर से चलाने के लिए यह पूरी तरह से क्रमबद्ध करने की जरूरत है. दो 3 की तुलना में कम है, तो हम उन्हें स्वैप नहीं. 

तीन 6 की तुलना में कम है, तो हम उन्हें स्वैप नहीं. छह 5 से अधिक है. हम बदली. 9 से छह कम है. हम स्वैप नहीं. 2 के माध्यम से पारित करने के बाद, यह इस तरह दिखता है: [2, 3, 5, 6, 9]. बिल्कुल सही. अब, चलो यह pseudocode में लिखने के. असल में, सूची में प्रत्येक तत्व के लिए, हम इसे देखने की जरूरत है और सीधे इसकी सही तत्व. यदि वे आदेश के बाहर एक दूसरे के रिश्तेदार हैं - जो है, अगर बाईं तरफ तत्व सही पर एक से अधिक है - हम दो तत्वों स्वैप चाहिए. 

हम सूची के प्रत्येक तत्व के लिए ऐसा करते हैं, और हम के माध्यम से एक पास कर दिया है. अब हम सिर्फ पास के माध्यम से पर्याप्त समय सूची में करने के लिए सुनिश्चित करने के लिए है पूरी तरह से ठीक से हल. लेकिन कितनी बार हम सूची के माध्यम से पारित है गारंटी है कि हम कर रहे हैं? खैर, सबसे खराब स्थिति यह है कि अगर हम एक पूरी तरह से पीछे की ओर सूची. तो यह पारित throughs की संख्या के बराबर संख्या लेता है n-1 तत्वों की. यदि यह भावना intuitively नहीं पड़ता है, एक साधारण मामला है के बारे में सोच - सूची [2, 1]. 

यह एक पास के माध्यम से लेने के लिए सही ढंग से सॉर्ट जा रहा है. [3, 2, 1] - सबसे खराब मामला है कि 3 तत्वों के साथ पीछे की ओर क्रमबद्ध यह तरह 2 पुनरावृत्तियों ले जा रहा है. एक चलना के बाद, यह [2, 1, 3] है. 2 पैदावार क्रमबद्ध सरणी [1, 2, 3]. तो आप जानते हैं कि आप सामान्य रूप में कभी नहीं किया है, सरणी के माध्यम से जाना है, n-1 बार, जहाँ n सरणी में तत्वों की संख्या की तुलना में अधिक है. यह बुलबुला तरह कहा जाता है, क्योंकि सबसे बड़ा तत्वों 'बुलबुला' के लिए करते हैं सही करने के लिए बहुत जल्दी. वास्तव में, इस एल्गोरिथ्म व्यवहार बहुत ही रोचक है. 

पूरे सरणी के माध्यम से मीटर iterations के बाद, rightmost मीटर तत्वों की गारंटी हैं उनके सही जगह में हल किया जा. अगर आप खुद के लिए यह देखना चाहते हैं, हम इसे पूरी तरह से पीछे की ओर [9, 6, 5, 3, 2] सूची पर कोशिश कर सकते हैं. पूरी सूची के माध्यम से एक पास के बाद, लेखन की ध्वनि [] [6, 9, 5, 2, 3], [6, 5, 9, 3 2,], [6, 5, 3, 9 2,], [6, 5, 3, 2, 9] rightmost 9 तत्व अपनी सही जगह में है. पास के माध्यम से 2 के बाद 6 'bubbled अप' होगा 2 rightmost जगह. 6 और 9 - सही पर दो तत्वों को उनके सही स्थानों में होगा पहले दो पास - थ्रू के बाद. 

तो, हम कैसे इस का उपयोग एल्गोरिथ्म अनुकूलन कर सकते हैं? खैर, सरणी के माध्यम से एक चलना के बाद हम वास्तव rightmost तत्व की जांच की जरूरत नहीं है क्योंकि हम जानते हैं कि यह हल है. दो iterations के बाद, हम सुनिश्चित करें कि rightmost दो तत्वों जगह में हैं के लिए जानते हैं. तो, सामान्य रूप में, पूर्ण सरणी के माध्यम से कश्मीर पुनरावृत्तियों के बाद, पिछले कश्मीर तत्वों की जाँच निरर्थक है क्योंकि हम जानते हैं वे सही स्थान में पहले से ही कर रहे हैं. 

तो अगर आप n तत्वों की एक सरणी छँटाई कर रहे हैं, पहली यात्रा पर you'll तत्वों के सभी प्रकार है - 1 n-0. दूसरी यात्रा पर, आप तत्वों के सभी लेकिन पिछले पर देखना होगा - n-1 1. एक अन्य अनुकूलन जाँच करने के लिए हो सकता है यदि सूची पहले से ही सॉर्ट किया जाता है प्रत्येक यात्रा के बाद. यदि यह पहले से ही हल है, हम किसी भी अधिक पुनरावृत्तियों बनाने की जरूरत नहीं सूची के माध्यम से. हम यह कैसे कर सकते हैं? खैर, अगर हम किसी भी स्वैप एक सूची के माध्यम से गुजरती पर बनाना नहीं है, यह स्पष्ट है कि सूची में पहले से ही है क्योंकि हम कुछ भी नहीं स्वैप किया हल किया गया था. तो हम निश्चित रूप से फिर तरह नहीं है. 

शायद तुम एक झंडा चर 'हल नहीं' नामक शुरू नहीं कर पाया झूठी और यह सच में बदलने के लिए अगर आप पर किसी भी तत्व को स्वैप सरणी के माध्यम से एक चलना. या इसी तरह, एक काउंटर बनाने के लिए गिनती के लिए कितने स्वैप आप बनाने किसी भी यात्रा पर. एक चलना के अंत में, अगर आप तत्वों की किसी भी स्वैप नहीं था, आप जानते हैं कि सूची पहले से ही हल है और आप कर रहे हैं. बुलबुला तरह, अन्य छँटाई एल्गोरिदम की तरह हो सकता है, किसी भी तत्व है जो एक आदेश विधि के लिए काम करने के लिए tweaked. 

कि दो तत्वों दिया आप कहने के लिए एक तरीका है, अगर पहले एक की तुलना में, दूसरे से कम के बराबर या अधिक से अधिक है. उदाहरण के लिए, आप कह रही द्वारा वर्णमाला के अक्षर की तरह सकता है कि एक <ख, ख <सी, आदि, या आप सप्ताह के दिनों में ऐसी जगह है जहां रविवार सोमवार की तुलना में कम हो सकता है हो सकता है जो मंगलवार की तुलना में कम है. 

बुलबुला तरह कोई एक बहुत ही कुशल है या तेजी से छँटाई एल्गोरिथ्म का मतलब है. इसके सबसे ज्यादा मामले क्रम n बड़ी हे ² है क्योंकि आप एक सूची के माध्यम से n पुनरावृत्तियों करना है सभी n तत्वों की जाँच के माध्यम से प्रत्येक पारित करने के लिए, nxn n = ². इस चलाने के लिए समय का मतलब है कि तत्वों की संख्या के रूप में बढ़ जाती है छँटाई कर रहे हैं, चलाते समय quadratically बढ़ जाती है. 

लेकिन अगर क्षमता अपने कार्यक्रम के एक प्रमुख चिंता का विषय नहीं है या यदि आप केवल तत्वों की एक छोटी संख्या छँटाई कर रहे हैं, आप बुलबुला तरह उपयोगी मिल सकता है क्योंकि यह एक सरल छँटाई एल्गोरिदम की है समझने के लिए कोड और. यह भी एक शानदार तरीका है करने के लिए एक सैद्धांतिक अनुवाद के साथ अनुभव प्राप्त वास्तविक कार्य कोड में एल्गोरिथ्म. खैर, कि आप के लिए बुलबुला तरह है. देखने के लिए धन्यवाद. CS50.TV