PGDCA, BCA, B-Tech, MCA, M-Tech, B.Sc computer science राजस्थान सूचना सहायक व कंप्यूटर शिक्षक विशेष नोट्स: इस अध्याय में हम Bubble Sort: Adjacent Swapping, Adaptive Bubble Sort O(n) (बबल सॉर्ट: आसन्न तत्वों की अदला-बदली और O(n^2) जटिलता) की संपूर्ण थ्योरी, मुख्य तकनीकी बिंदु, तुलनात्मक तालिका और विगत परीक्षाओं के पैटर्न पर आधारित 20 अति-महत्वपूर्ण बहुविकल्पीय प्रश्न (MCQs) विस्तृत हिंदी व अंग्रेजी व्याख्या सहित पढ़ेंगे।
Overview: Bubble Sort repeatedly compares and swaps out-of-order adjacent elements so the largest items bubble to the right, running in O(n^2) worst case and O(n) best case when made adaptive with a swap flag.
अध्याय सार: बबल सॉर्ट पास-दर-पास आसन्न (Adjacent) तत्वों की तुलना व अदला-बदली कर सबसे बड़े तत्व को दाईं ओर पहुंचाता है; सामान्यतः O(n^2) समय लेता है पर स्वैप-फ्लैग से एडैप्टिव बनाने पर बेस्ट केस O(n) हो जाता है।
Bubble Sort: Adjacent Swapping, Adaptive Bubble Sort O(n): Detailed Notes & Architecture (बबल सॉर्ट: आसन्न तत्वों की अदला-बदली और O(n^2) जटिलता)
1. Adjacent Pairwise Swapping Mechanics (आसन्न तत्वों की अदला-बदली की प्रक्रिया)
[EN] Bubble Sort executes up to n-1 outer passes over an array of size n. In pass i (0-based), the inner loop compares consecutive neighbors arr[j] and arr[j+1] for j from 0 to n-2-i, swapping them whenever arr[j] > arr[j+1]. Consequently, after pass 0 the global maximum settles into arr[n-1], after pass 1 the second largest settles into arr[n-2], and the unsorted prefix shrinks by one each pass.
[HI] n आकार के एरे पर बबल सॉर्ट अधिकतम n-1 बाहरी पास (Passes) चलाता है। पास i में आंतरिक लूप j = 0 से n-2-i तक लगातार पड़ोसी तत्वों arr[j] और arr[j+1] की तुलना करता है और arr[j] > arr[j+1] होने पर उन्हें स्वैप कर देता है। प्रत्येक पास के अंत में अनसॉर्टेड भाग का सबसे बड़ा तत्व बुलबुले की तरह उभरकर अपने अंतिम सही स्थान पर पहुंच जाता है।
2. Standard vs Adaptive Bubble Sort (O(n) Best Case) (साधारण बनाम एडैप्टिव बबल सॉर्ट (O(n) बेस्ट केस))
[EN] A naive Bubble Sort without early termination blindly executes all n-1 passes, performing n(n-1)/2 comparisons even on an already sorted array—making its Best, Average, and Worst cases all Theta(n^2). Adaptive (Optimized) Bubble Sort initializes a boolean flag swapped = false before each pass; if an entire pass completes with zero swaps, the array is guaranteed sorted and the outer loop breaks immediately. This reduces Best-Case comparisons to n - 1 and time complexity to O(n).
[HI] बिना अर्ली-एग्जिट वाले साधारण बबल सॉर्ट में पहले से सॉर्टेड एरे पर भी पूरे n-1 पास और n(n-1)/2 तुलनाएँ होती हैं, जिससे बेस्ट केस भी O(n^2) रहता है। एडैप्टिव बबल सॉर्ट में हर पास से पहले swapped = false रखा जाता है; यदि पूरे पास में एक भी स्वैप न हो, तो एरे पूरी तरह सॉर्टेड मानकर लूप वहीं रोक दिया जाता है। इससे बेस्ट केस में केवल n - 1 तुलनाएँ लगती हैं और समय घटकर O(n) हो जाता है।
3. Inversion Analysis, Stability & Space Profile (इनवर्जन विश्लेषण, स्थिरता व मेमोरी उपयोग)
[EN] Each swap in Bubble Sort resolves exactly one inversion (a pair where i < j yet arr[i] > arr[j]). Therefore, the worst case occurs on a strictly reverse-sorted array containing n(n-1)/2 inversions, causing both n(n-1)/2 comparisons and n(n-1)/2 swaps. Because swapping strictly checks arr[j] > arr[j+1] (never >=), equal elements never jump past one another—making Bubble Sort both Stable and In-Place with O(1) auxiliary space.
[HI] बबल सॉर्ट में प्रत्येक स्वैप ठीक एक इनवर्जन (उलटे जोड़े, जहाँ i < j पर arr[i] > arr[j]) को समाप्त करता है। अतः रिवर्स-सॉर्टेड एरे में अधिकतम n(n-1)/2 तुलनाएँ और उतने ही n(n-1)/2 स्वैप होते हैं। चूंकि तुलना केवल arr[j] > arr[j+1] (कठोर असमानता, >= नहीं) पर होती है, समान मानों का सापेक्ष क्रम कभी नहीं बदलता—इसलिए बबल सॉर्ट एक स्टेबल (Stable) व इन-प्लेस (O(1) स्पेस) एल्गोरिदम है।
4. Rabbits, Turtles & Cocktail Shaker Variant (रैबिट-टर्टल समस्या व कॉकटेल शेकर सॉर्ट)
[EN] Large elements near the start ('rabbits') travel rapidly rightward to the end within a single pass. Conversely, small elements near the right end ('turtles') move leftward by only one slot per pass, forcing nearly all n-1 passes even if the rest of the array is sorted (e.g., [2, 3, 4, 5, 1]). Cocktail Shaker Sort (Bidirectional Bubble Sort) alternates forward left-to-right and backward right-to-left passes to eliminate turtles rapidly.
[HI] बाएँ छोर के बड़े तत्व ('रैबिट्स') एक ही पास में दाईं ओर पहुंच जाते हैं, परंतु दाएँ छोर पर बैठा छोटा तत्व ('टर्टल', जैसे [2, 3, 4, 5, 1] में 1) हर पास में केवल एक ही स्थान बाएँ खिसकता है। इस समस्या को हल करने के लिए कॉकटेल शेकर सॉर्ट (बायडायरेक्शनल बबल सॉर्ट) एक बार बाएँ से दाएँ और अगली बार दाएँ से बाएँ पास चलाता है।
Syntax, Formula & Technical Example (Bubble Sort: Adjacent Swapping, Adaptive Bubble Sort O(n))
void adaptiveBubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
bool swapped = false;
for (int j = 0; j < n - 1 - i; j++)
if (arr[j] > arr[j + 1]) {
int t = arr[j]; arr[j] = arr[j+1]; arr[j+1] = t; swapped = true;
}
if (!swapped) break; // Early exit -> O(n) best case
}
}
Bubble Sort: Adjacent Swapping, Adaptive Bubble Sort O(n) Quick Reference & Comparison Table
| Bubble Sort Case / Attribute | Exact Metric / Condition | Exam Takeaway |
|---|---|---|
| Unoptimized Best Case | n(n-1)/2 comparisons; Theta(n^2) | Lack of swapped flag forces all n-1 passes |
| Adaptive Best Case (With Flag) | n - 1 comparisons, 0 swaps; O(n) | Exits after Pass 1 when swapped stays false |
| Worst Case (Reverse Order) | n(n-1)/2 comparisons and swaps; O(n^2) | Maximum inversions equal n*(n-1)/2 |
| Stability & Auxiliary Space | Stable (strict >) and In-Place O(1) | Using >= instead of > destroys stability |
Bubble Sort: Adjacent Swapping, Adaptive Bubble Sort O(n) Top 20 Bilingual MCQs with Answers
Q1. How many passes are executed in the worst case by Bubble Sort on an array of n elements?
(n तत्वों वाले एरे को सॉर्ट करने के लिए वर्स्ट केस में बबल सॉर्ट अधिकतम कितने पास (Passes) चलाता है?)
(A) log2(n)
(B) n - 1
(C) n / 2
(D) n
Correct Answer: (B)
[EN] After n - 1 passes place the n - 1 largest elements correctly, the single remaining element at index 0 is automatically sorted.
[HI] n - 1 पास में n - 1 बड़े तत्व सही स्थान पर लग जाते हैं और पहला तत्व स्वतः अपनी सही जगह पर रह जाता है।
Q2. What makes 'Adaptive Bubble Sort' achieve O(n) time complexity on an already sorted array?
('एडैप्टिव बबल सॉर्ट' पहले से सॉर्टेड एरे पर O(n) समय जटिलता कैसे प्राप्त करता है?)
(A) Using a boolean 'swapped' flag to terminate early if zero swaps occur in a pass
(B) Allocating an O(n) helper array
(C) Skipping odd-indexed elements
(D) Replacing adjacent swaps with binary search
Correct Answer: (A)
[EN] When zero swaps happen during the first pass (n-1 comparisons), the array is confirmed sorted and sorting stops.
[HI] पहले ही पास में एक भी स्वैप न होने पर swapped फ्लैग false रहता है और लूप n-1 तुलनाओं के बाद तुरंत रुक जाता है।
Q3. What is the state of the array [5, 1, 4, 2, 8] immediately after Pass 1 of standard ascending Bubble Sort?
(आरोही बबल सॉर्ट के पहले पास (Pass 1) के ठीक बाद एरे [5, 1, 4, 2, 8] की स्थिति क्या होगी?)
(A) [1, 2, 4, 5, 8]
(B) [1, 4, 2, 5, 8]
(C) [1, 5, 4, 2, 8]
(D) [5, 1, 4, 2, 8]
Correct Answer: (B)
[EN] Pass 1: (5,1)->[1,5,4,2,8], (5,4)->[1,4,5,2,8], (5,2)->[1,4,2,5,8], (5,8)->no swap. Largest element 8 sits at end.
[HI] पास 1 में 5 और 1, फिर 5 और 4, फिर 5 और 2 स्वैप होते हैं (8 से स्वैप नहीं होता), जिससे [1, 4, 2, 5, 8] बनता है।
Q4. In the worst case (strictly reverse-sorted array of size n), how many swaps does Bubble Sort perform?
(n आकार के पूर्णतः उलटे (Reverse-Sorted) एरे पर वर्स्ट केस में बबल सॉर्ट कुल कितने स्वैप करेगा?)
(A) n - 1
(B) n^2
(C) n
(D) n(n - 1) / 2
Correct Answer: (D)
[EN] Every pair (i, j) with i < j is an inversion; there are C(n, 2) = n(n-1)/2 pairs, each requiring 1 adjacent swap.
[HI] उलटे एरे में कुल n(n-1)/2 इनवर्जन जोड़े होते हैं और हर स्वैप केवल 1 इनवर्जन हटाता है, अतः n(n-1)/2 स्वैप लगते हैं।
Q5. Why is Bubble Sort considered a Stable sorting algorithm?
(बबल सॉर्ट को एक स्टेबल (Stable) सॉर्टिंग एल्गोरिदम क्यों कहा जाता है?)
(A) Because it swaps adjacent items only when arr[j] > arr[j+1], preserving equal items' relative order
(B) Because its worst-case runtime never exceeds O(n log n)
(C) Because it picks the minimum element first
(D) Because it uses O(n) extra memory buffer
Correct Answer: (A)
[EN] Equal neighbors (arr[j] == arr[j+1]) fail the strict '>' test and are never swapped across each other.
[HI] यह केवल arr[j] > arr[j+1] होने पर ही स्वैप करता है; बराबर तत्व आपस में कभी जगह नहीं बदलते।
Q6. What would happen to stability if a programmer accidentally wrote 'if (arr[j] >= arr[j+1])' in Bubble Sort?
(यदि कोई प्रोग्रामर बबल सॉर्ट में गलती से 'arr[j] > arr[j+1]' के बजाय 'arr[j] >= arr[j+1]' लिख दे, तो क्या होगा?)
(A) Time complexity improves to O(n log n)
(B) It sorts in descending order
(C) It crashes with array out-of-bounds
(D) The algorithm stays correct in value order but becomes Unstable (and does useless swaps)
Correct Answer: (D)
[EN] Swapping equal elements reverses their original arrival order, breaking stability while doing redundant swaps.
[HI] बराबर मान भी आपस में स्वैप हो जाएंगे, जिससे एल्गोरिदम अनस्टेबल (Unstable) हो जाएगा और अनावश्यक स्वैप बढ़ेंगे।
Q7. How many comparisons does standard (unoptimized) Bubble Sort perform for n = 6 elements?
(n = 6 तत्वों पर बिना फ्लैग वाला मानक बबल सॉर्ट कितनी तुलनाएँ करेगा?)
(A) 15
(B) 21
(C) 36
(D) 5
Correct Answer: (A)
[EN] Total comparisons = n(n-1)/2 = 6 * 5 / 2 = 15 (5 + 4 + 3 + 2 + 1).
[HI] कुल तुलनाएँ = 5 + 4 + 3 + 2 + 1 = n(n-1)/2 = 6 * 5 / 2 = 15 होंगी।
Q8. In Bubble Sort terminology, what is a 'turtle'?
(बबल सॉर्ट की शब्दावली में 'टर्टल (Turtle)' किसे कहा जाता है?)
(A) A sentinel added at arr[n]
(B) An element equal to the pivot
(C) A large value near index 0 that moves to the end in 1 pass
(D) A small value located near the end of the array that moves left only one position per pass
Correct Answer: (D)
[EN] Small elements near the tail move backward by just 1 index per left-to-right pass, forcing many passes.
[HI] दाएँ अंत में स्थित छोटे मान को टर्टल कहते हैं क्योंकि वह प्रति पास केवल 1 स्थान बाईं ओर खिसक पाता है।
Q9. Which variant solves the 'turtle' bottleneck in Bubble Sort by alternating pass directions?
(दोनों दिशाओं में बारी-बारी पास चलाकर बबल सॉर्ट की 'टर्टल' समस्या को कौन सा वेरिएंट हल करता है?)
(A) Selection Sort
(B) Shell Sort
(C) Counting Sort
(D) Cocktail Shaker Sort (Bidirectional Bubble Sort)
Correct Answer: (D)
[EN] Cocktail Shaker Sort sweeps left-to-right then right-to-left, moving both large rabbits right and small turtles left.
[HI] कॉकटेल शेकर सॉर्ट बाएँ से दाएँ और फिर दाएँ से बाएँ पास चलाकर बड़े व छोटे दोनों तत्वों को तेजी से स्थान पर लाता है।
Q10. On the array [2, 3, 4, 5, 1] (n = 5), how many adjacent swaps and passes does Bubble Sort with loop 'i < n - 1' require to move turtle '1' to index 0?
(एरे [2, 3, 4, 5, 1] (n = 5) में बबल सॉर्ट ('i < n - 1' लूप के साथ) को '1' को इंडेक्स 0 तक लाने में कितने स्वैप और पास लगेंगे?)
(A) 10 swaps across 5 passes
(B) 1 swap in 1 pass
(C) 2 swaps across 2 passes
(D) 4 swaps across 4 passes
Correct Answer: (D)
[EN] Element '1' moves left by 1 index per pass: pass 0->idx 3, pass 1->idx 2, pass 2->idx 1, pass 3->idx 0 (4 swaps in 4 passes).
[HI] तत्व '1' प्रति पास केवल 1 स्थान बाएँ खिसकता है: 4 पास में कुल 4 स्वैप से यह इंडेक्स 4 से इंडेक्स 0 पर पहुंच जाता है।
Q11. On an already sorted array of 100 elements, how many adjacent comparisons does Adaptive Bubble Sort execute before terminating?
(100 तत्वों के पहले से सॉर्टेड एरे पर एडैप्टिव बबल सॉर्ट रुकने से पहले कितनी तुलनाएँ करेगा?)
(A) 1
(B) 4950
(C) 100
(D) 99
Correct Answer: (D)
[EN] In pass 0, all n - 1 = 99 adjacent pairs are checked; zero swaps occur, so swapped stays false and the algorithm exits immediately.
[HI] पहले ही पास में सभी n - 1 = 99 आसन्न जोड़ों की जांच होती है; कोई स्वैप न होने से एल्गोरिदम तुरंत रुक जाता है।
Q12. What is the auxiliary space complexity of standard Bubble Sort?
(सामान्य बबल सॉर्ट की ऑक्सिलरी स्पेस कॉम्प्लेक्सिटी कितनी होती है?)
(A) O(log n)
(B) O(n)
(C) O(1)
(D) O(n^2)
Correct Answer: (C)
[EN] It swaps elements directly inside the input array using a single temporary variable.
[HI] यह केवल एक अस्थायी वेरिएबल से एरे के भीतर ही अदला-बदली करता है, अतः स्थान जटिलता O(1) है।
Q13. Which condition corresponds to the maximum number of inversions in an array of length n?
(n लंबाई के एरे में अधिकतम इनवर्जन (Inversions) कब मौजूद होते हैं?)
(A) When the array is already sorted ascending
(B) When all elements are identical
(C) When the array is sorted in strictly descending order
(D) When only the first and last items are swapped
Correct Answer: (C)
[EN] Every pair is out of order in a strictly decreasing sequence, yielding n(n-1)/2 inversions.
[HI] जब एरे पूरी तरह अवरोही (Descending) क्रम में हो, तब अधिकतम n(n-1)/2 इनवर्जन होते हैं।
Q14. Which sorting algorithm performs FAR fewer swaps than Bubble Sort (at most n-1 vs n(n-1)/2) in the worst case?
(वर्स्ट केस में बबल सॉर्ट के n(n-1)/2 स्वैप के मुकाबले अधिकतम केवल n-1 स्वैप करने वाला एल्गोरिदम कौन सा है?)
(A) Selection Sort
(B) Cocktail Shaker Sort
(C) Insertion Sort (shifts)
(D) Gnome Sort
Correct Answer: (A)
[EN] Selection Sort finds the minimum first and performs only 1 swap per pass (max n-1 total).
[HI] सिलेक्शन सॉर्ट हर पास में केवल एक बार न्यूनतम तत्व के साथ स्वैप करता है (अधिकतम n-1 स्वैप)।
Q15. Which statement is NOT true regarding Adaptive Bubble Sort?
(एडैप्टिव बबल सॉर्ट के संदर्भ में इनमें से कौन सा कथन सत्य नहीं है?)
(A) It is an in-place sorting algorithm
(B) It preserves the relative order of duplicate keys
(C) Its best-case time complexity is O(n)
(D) Its worst-case time complexity improves from O(n^2) to O(n log n)
Correct Answer: (D)
[EN] The swapped flag only speeds up already/nearly sorted inputs; reverse-sorted input still takes O(n^2).
[HI] swapped फ्लैग केवल बेस्ट केस (सॉर्टेड इनपुट) को O(n) बनाता है; वर्स्ट केस जटिलता O(n^2) ही रहती है।
Q16. How many inversions exist in the array [4, 2, 1, 3], which also equals the exact swaps Adaptive Bubble Sort makes?
(एरे [4, 2, 1, 3] में कुल कितने इनवर्जन (और बबल सॉर्ट द्वारा किए जाने वाले स्वैप) हैं?)
(A) 6
(B) 4
(C) 2
(D) 3
Correct Answer: (B)
[EN] Inverted pairs are (4,2), (4,1), (4,3), and (2,1) — total 4 inversions, so 4 swaps occur.
[HI] इनवर्जन जोड़े (4,2), (4,1), (4,3) और (2,1) यानी कुल 4 हैं, अतः ठीक 4 स्वैप होंगे।
Q17. Within Bubble Sort: Adjacent Swapping, Adaptive Bubble Sort O(n), which bubble sort case / attribute directly maps to: "n(n-1)/2 comparisons; Theta(n^2)"?
(Bubble Sort: Adjacent Swapping, Adaptive Bubble Sort O(n) में कौन सा Bubble Sort Case / Attribute सीधे "n(n-1)/2 comparisons; Theta(n^2)" से संबंधित है?)
(A) Unoptimized Best Case
(B) Worst Case (Reverse Order)
(C) Stability & Auxiliary Space
(D) Adaptive Best Case (With Flag)
Correct Answer: (A)
[EN] In Bubble Sort: Adjacent Swapping, Adaptive Bubble Sort O(n), 'Unoptimized Best Case' handles 'n(n-1)/2 comparisons; Theta(n^2)' (Lack of swapped flag forces all n-1 passes).
[HI] Bubble Sort: Adjacent Swapping, Adaptive Bubble Sort O(n) में 'Unoptimized Best Case' का कार्य/विवरण 'n(n-1)/2 comparisons; Theta(n^2)' (Lack of swapped flag forces all n-1 passes) है।
Q18. Which option accurately describes 'Adaptive Best Case (With Flag)' in Bubble Sort: Adjacent Swapping, Adaptive Bubble Sort O(n)?
(Bubble Sort: Adjacent Swapping, Adaptive Bubble Sort O(n) के संदर्भ में 'Adaptive Best Case (With Flag)' की सही विशेषता कौन सी है?)
(A) n(n-1)/2 comparisons and swaps; O(n^2)
(B) Stable (strict >) and In-Place O(1)
(C) n - 1 comparisons, 0 swaps; O(n)
(D) n(n-1)/2 comparisons; Theta(n^2)
Correct Answer: (C)
[EN] 'Adaptive Best Case (With Flag)' provides 'n - 1 comparisons, 0 swaps; O(n)' — key point: Exits after Pass 1 when swapped stays false.
[HI] 'Adaptive Best Case (With Flag)' का मुख्य विवरण 'n - 1 comparisons, 0 swaps; O(n)' है (Exits after Pass 1 when swapped stays false)।
Q19. In Bubble Sort: Adjacent Swapping, Adaptive Bubble Sort O(n), identify the correct parameter for the specification: "n(n-1)/2 comparisons and swaps; O(n^2)".
(Bubble Sort: Adjacent Swapping, Adaptive Bubble Sort O(n) में "n(n-1)/2 comparisons and swaps; O(n^2)" विवरण किस विकल्प के लिए सही है?)
(A) Stability & Auxiliary Space
(B) Worst Case (Reverse Order)
(C) Unoptimized Best Case
(D) Adaptive Best Case (With Flag)
Correct Answer: (B)
[EN] 'Worst Case (Reverse Order)' corresponds to 'n(n-1)/2 comparisons and swaps; O(n^2)' (Maximum inversions equal n*(n-1)/2).
[HI] 'Worst Case (Reverse Order)' का संबंध 'n(n-1)/2 comparisons and swaps; O(n^2)' (Maximum inversions equal n*(n-1)/2) से है।
Q20. Considering Bubble Sort: Adjacent Swapping, Adaptive Bubble Sort O(n), what key behavior defines 'Stability & Auxiliary Space'?
(Bubble Sort: Adjacent Swapping, Adaptive Bubble Sort O(n) में 'Stability & Auxiliary Space' की मुख्य भूमिका या मान क्या है?)
(A) n(n-1)/2 comparisons; Theta(n^2)
(B) Stable (strict >) and In-Place O(1)
(C) n(n-1)/2 comparisons and swaps; O(n^2)
(D) n - 1 comparisons, 0 swaps; O(n)
Correct Answer: (B)
[EN] 'Stability & Auxiliary Space' represents 'Stable (strict >) and In-Place O(1)' (Using >= instead of > destroys stability).
[HI] 'Stability & Auxiliary Space' का अर्थ/मान 'Stable (strict >) and In-Place O(1)' है (Using >= instead of > destroys stability)।
Bubble Sort: Adjacent Swapping, Adaptive Bubble Sort O(n) — Exam FAQs
Q1: Why is Bubble Sort taught first despite being O(n^2)?
O(n^2) होने के बावजूद बबल सॉर्ट सबसे पहले क्यों पढ़ाया जाता है?
[EN] It demonstrates loop invariants, adjacent pairwise comparison, stability, and how a simple boolean flag makes an algorithm adaptive in O(n) best case.
[HI] यह लूप इनवेरिएंट, तुलना-आधारित स्वैपिंग, स्टेबिलिटी और एक साधारण फ्लैग से एल्गोरिदम को एडैप्टिव बनाने की मूलभूत अवधारणा को स्पष्ट रूप से समझाता है।
Q2: Is Bubble Sort faster than Insertion Sort on nearly sorted data?
क्या लगभग सॉर्टेड डेटा पर बबल सॉर्ट इंसर्शन सॉर्ट से तेज होता है?
[EN] No. Although both are O(n) on fully sorted data, Insertion Sort performs shifts without temporary swap triples and beats Bubble Sort by a large constant factor on nearly sorted arrays.
[HI] नहीं। दोनों सॉर्टेड डेटा पर O(n) लेते हैं, लेकिन इंसर्शन सॉर्ट में स्वैप के 3 असाइनमेंट के बजाय केवल एकल शिफ्ट होता है, इसलिए इंसर्शन सॉर्ट व्यावहारिक रूप से काफी तेज रहता है।
Q3: Does Bubble Sort work on Linked Lists without changing its O(n^2) complexity?
क्या लिंक्ड लिस्ट पर बबल सॉर्ट O(n^2) में काम कर सकता है?
[EN] Yes. Since Bubble Sort only compares and swaps adjacent nodes, sequential node-by-node access fits singly linked lists naturally in O(n^2) time and O(1) space.
[HI] हाँ। चूंकि बबल सॉर्ट केवल पड़ोसी तत्वों को देखता है, इसलिए यह बिना किसी रैंडम इंडेक्सिंग के सिंगली लिंक्ड लिस्ट पर भी O(n^2) समय में काम कर सकता है।
Post a Comment
Post a Comment