बबल छँटाई

बबल छँटाई एगो छँटाई के बिधी हऽ जेवन की सऊँसे लिस्ट मे बेर बेर घूरेला, अगिला चिक्ष के पिछलका से तूलना करेला आ जदि ऊ दुन्नो सही क्रम मे ना रहे तऽ दून्नो के अदला-बदली कर देवेला। एहमें तबले लिस्ट भ मे घुरल जाला जबले पूरा लिस्ट के छँटाई ना हो जाला। भले ई बिधि बहुते सरल बा बाकिर बहुते लहे लहे काम करेला आ कतना समस्या सभ ला अप्ययोगिक बा।

बबल छँटाई

Static visualization of bubble sort[1]
क्लास	Sorting algorithm
डेटा स्ट्रक्चर	Array
सभसे खराब केस परफार्मेंस	${\displaystyle O(n^{2})}$ comparisons, ${\displaystyle O(n^{2})}$ swaps
सभसे नीमन केस परफार्मेंस	${\displaystyle O(n)}$ comparisons, ${\displaystyle O(1)}$ swaps
एभरेज केस परफार्मेंस	${\displaystyle O(n^{2})}$ comparisons, ${\displaystyle O(n^{2})}$ swaps
सभसे खराब केस स्पेस जटिलता	${\displaystyle O(1)}$ auxiliary

बिबेचन

बबल छँटाई बीधी के एगो उदाहरन, लिस्ट के पहिला अंग से चालू करीं, अगिला मय जोड़ा के मिलाईं, जदि दुन्नो सही क्रम मे नइखे तऽ दुन्नो के अदला बदली कर दिहीं। लिस्ट मे तबले घुरीं जबले सभ अंग एगो बिसेस क्रम मे नइखे आ जात।

परदरसन

बबल छँटाई के सभसे खराब औसत समय जटिलता O(n ²) हऽ, जेने n छाँटे वला चीझन के संख्या हऽ। बसी समय लिहला के चलते ई बीधि अप्ययोगिक बा।

बिधी जोरे उदाहरण

एगो त्राम चाहे अएरे लिहीं "5 1 4 2 8" आ हेकरा बढ़त क्रम मे छाँटी। हर डेग प मोटहन अंग के मिलावल जाई। लिस्ट मे तीन हाली घुरे के जाओरत पड़ी।

पहिलका घुमरी

( 5 1 4 2 8 ) → ( 1 5 4 2 8 ), एहिजा, पहिलका दुगो अंकन के मिलावल जाता आ अदला बदली कईल जाता। एहसे के 5>1

( 1 5 4 2 8 ) → ( 1 4 5 2 8 ), बदल दिहिन एहसे की 5 > 4

( 1 4 5 2 8 ) → ( 1 4 2 5 8 ), बदल दिहिं एहसे की 5 > 2

( 1 4 2 5 8 ) → ( 1 4 2 5 8 ), अबहिन, ई दुन्नो पहिलहीं क्रम मे बाड़न सन(8 > 5), तऽ एखिनी के अदला बदली कईल जाई

दूसरका घुमरी

( 1 4 2 5 8 ) → ( 1 4 2 5 8 )

( 1 4 2 5 8 ) → ( 1 2 4 5 8 ), बदल दिहिं एहसे की 4 > 2

( 1 2 4 5 8 ) → ( 1 2 4 5 8 )

( 1 2 4 5 8 ) → ( 1 2 4 5 8 )

अबहिन, लिस्ट क्रम मे आ गइल बा, बाकिर बिधी नइखे जानत के क्रम मे बा की ना. हेकरा बदे लिस्ट मे फेर एक हाली घूरे के पड़ी

तीसरका घूमरी

( 1 2 4 5 8 ) → ( 1 2 4 5 8 )

( 1 2 4 5 8 ) → ( 1 2 4 5 8 )

( 1 2 4 5 8 ) → ( 1 2 4 5 8 )

( 1 2 4 5 8 ) → ( 1 2 4 5 8 )

संदर्भ

1. Cortesi, Aldo (27 April 2007). "Visualising Sorting Algorithms". Retrieved 16 March 2017.