Bubble Sort
Bubble Sort का Concept और Invariant
Bubble sort adjacent elements compare करता है, गलत order वाले pair को swap करता है और passes दोहराता है। Ascending pass के बाद active range का largest element final position पर पहुंच जाता है; अगला pass sorted suffix को छोड़ सकता है।
values[i] > values[i+1] होने पर ही swap करें। Strict comparison equal records का relative order बचाता है।
Selection और insertion से तुलना के लिए यह lesson पढ़ें।
Pass-by-Pass Trace
| Pass | Swaps | Pass के बाद sequence |
|---|---|---|
| 1 | 5↔1, 5↔4, 5↔2 | 1 4 2 5 8 |
| 2 | 4↔2 | 1 2 4 5 8 |
| 3 | कोई नहीं | 1 2 4 5 8 |
तीसरे pass में swap नहीं हुआ, इसलिए optimized algorithm तुरंत stop करता है।
Algorithm
हर pass में active range के adjacent pairs compare करें
out-of-order pair swap करें
pass के बाद end एक position घटाएं
किसी pass में swap न हो तो stop करेंEmpty और single-element vector में loop नहीं चलता, इसलिए result natural रूप से सही रहता है।
Complete C++ Program
void bubble_sort(std::vector<int>& values) {
for (std::size_t end = values.size(); end > 1; --end) {
bool swapped = false;
for (std::size_t i = 0; i + 1 < end; ++i) {
if (values[i] > values[i + 1]) {
std::swap(values[i], values[i + 1]);
swapped = true;
}
}
if (!swapped) break;
}
}Full program में <iostream>, <utility> और <vector> include करें। Reference parameter caller के vector को in-place sort करता है।
Early-Exit Optimization
हर outer pass से पहले swapped=false करें। Swap होने पर true करें। Pass के अंत में false रहे तो सभी adjacent pairs ordered हैं, इसलिए best case Θ(n) हो जाता है। Last swap का index रखकर अगला boundary और छोटा किया जा सकता है, पर worst case Θ(n²) ही रहता है।
Complexity और Stability
| Property | Result |
|---|---|
| Best | Θ(n), early exit के साथ |
| Average/Worst | Θ(n²) |
| Extra space | O(1) |
| Stable | हाँ, strict > पर |
| In-place | हाँ |
Swap input elements को खोता या बनाता नहीं। हर pass largest active value fix करता है; no-swap pass पूरे sequence के ordered होने का प्रमाण है।
कब Use करें
Teaching, visualization और tiny inputs में उपयोगी है। Large general data के लिए std::sort, stable order के लिए std::stable_sort, और Θ(n log n) अध्ययन के लिए merge sort बेहतर हैं। STL algorithms भी पढ़ें।
Mistakes, Testing और Practice
i+1 < endरखें, वरना out-of-bounds access होगा।swappedएक pass में एक बार reset करें।- Stability के लिए
>=नहीं,>लें। - Sorted, reverse, duplicates, negative, empty और one-element cases test करें।
Practice: comparisons/swaps count करें, descending version लिखें और equal-key records से stability verify करें।
Authoritative संदर्भ
Definition और complexity इन sources से verify की गई हैं। अगला topic: sorting और searching।
