Insertion Sort: Sorting Cards Metaphor, Online Algorithm Notes in Hindi & English : इंसर्शन सॉर्ट: पत्तों की तरह छँटाई, छोटे एरे में सर्वश्रेष्ठ O(n) और 20 महत्वपूर्ण MCQ प्रश्न (Rajasthan IT Exam)

Post a Comment

PGDCA, BCA, B-Tech, MCA, M-Tech, B.Sc computer science राजस्थान सूचना सहायक व कंप्यूटर शिक्षक विशेष नोट्स: इस अध्याय में हम Insertion Sort: Sorting Cards Metaphor, Online Algorithm (इंसर्शन सॉर्ट: पत्तों की तरह छँटाई, छोटे एरे में सर्वश्रेष्ठ O(n)) की संपूर्ण थ्योरी, मुख्य तकनीकी बिंदु, तुलनात्मक तालिका और विगत परीक्षाओं के पैटर्न पर आधारित 20 अति-महत्वपूर्ण बहुविकल्पीय प्रश्न (MCQs) विस्तृत हिंदी व अंग्रेजी व्याख्या सहित पढ़ेंगे।

Overview: Insertion Sort mirrors sorting playing cards in hand by inserting each new element into a growing sorted prefix, operating as a stable, in-place, online algorithm with O(n) best-case efficiency.

अध्याय सार: इंसर्शन सॉर्ट हाथ में ताश के पत्तों को जमाने की तरह प्रत्येक नए तत्व को पहले से सॉर्टेड भाग में सही स्थान पर रखता है; यह एक स्टेबल, इन-प्लेस व ऑनलाइन एल्गोरिदम है जिसका बेस्ट केस O(n) होता है।

Insertion Sort: Sorting Cards Metaphor, Online Algorithm: Detailed Notes & Architecture (इंसर्शन सॉर्ट: पत्तों की तरह छँटाई, छोटे एरे में सर्वश्रेष्ठ O(n))

1. Playing-Cards Metaphor & Shifting Mechanism (ताश के पत्तों की उपमा व शिफ्टिंग विधि)

[EN] Insertion Sort assumes the first element arr[0] forms a trivially sorted hand of size 1. For each subsequent index i from 1 to n-1, it picks key = arr[i], scans backward through arr[i-1..0], and shifts every item strictly greater than key one slot rightward (arr[j+1] = arr[j]) until finding the proper insertion slot where arr[j] <= key. Using one-assignment shifts instead of full 3-step swaps makes its inner loop noticeably faster than Bubble Sort.

[HI] इंसर्शन सॉर्ट मानता है कि पहला तत्व arr[0] पहले से सॉर्टेड है। इसके बाद i = 1 से n-1 तक हर तत्व को key मानकर उसके बाएँ सॉर्टेड भाग में पीछे की ओर जांच की जाती है और key से बड़े सभी तत्वों को एक-एक स्थान दाईं ओर शिफ्ट किया जाता है, फिर खाली सही स्थान पर key रख दिया जाता है। पूरे 3-चरण स्वैप के बजाय सिंगल शिफ्टिंग होने से यह बबल सॉर्ट की तुलना में तेज चलता है।

2. Inversion-Driven Complexity: O(n + I) (इनवर्जन-आधारित समय जटिलता: O(n + I))

[EN] Let I denote the total number of inversions (pairs i < j with arr[i] > arr[j]) in the input. Every inner-loop shift corrects exactly one inversion, so total shifts equal I and running time is tightly Theta(n + I). On an already sorted array (I = 0), only n - 1 comparisons and 0 shifts occur => Best Case O(n). On a reverse-sorted array (I = n(n-1)/2), both comparisons and shifts reach n(n-1)/2 => Worst Case O(n^2), with average time ~n^2/4.

[HI] यदि इनपुट एरे में कुल I इनवर्जन जोड़े हों, तो इंसर्शन सॉर्ट ठीक I शिफ्ट करता है और कुल समय Theta(n + I) लगता है। पहले से सॉर्टेड एरे में I = 0 होने से केवल n - 1 तुलनाएँ व 0 शिफ्ट लगते हैं—अर्थात बेस्ट केस O(n) होता है। इसके विपरीत रिवर्स-सॉर्टेड एरे में I = n(n-1)/2 होने से वर्स्ट केस समय O(n^2) और औसत समय भी O(n^2) (~n^2/4) होता है।

3. Online Algorithm, Adaptivity & Stability (ऑनलाइन एल्गोरिदम, एडैप्टिविटी व स्थिरता)

[EN] Insertion Sort is naturally Adaptive (nearly sorted or k-sorted inputs run in O(k*n) linear time) and In-Place (O(1) auxiliary space). Crucially, it is an Online Algorithm: it can incrementally maintain sorted order as live data elements stream in one at a time, without needing the complete array upfront. Furthermore, shifting strictly on arr[j] > key (not >=) ensures equal elements stay in their original arrival order, making it Stable.

[HI] इंसर्शन सॉर्ट स्वाभाविक रूप से एडैप्टिव (लगभग सॉर्टेड डेटा पर O(n) जैसा तेज) और इन-प्लेस (O(1) स्पेस) है। इसकी एक अनूठी विशेषता 'ऑनलाइन एल्गोरिदम' होना है—अर्थात पूरा डेटा पहले से मौजूद न हो और मान एक-एक करके लाइव स्ट्रीम में आ रहे हों, तब भी यह साथ-साथ सॉर्टेड क्रम बनाए रख सकता है। केवल arr[j] > key पर शिफ्ट करने से यह पूर्णतः स्टेबल भी रहता है।

4. Production Hybrid Use & Binary Insertion Sort (हाइब्रिड प्रयोग (Timsort/Introsort) व बाइनरी इंसर्शन)

[EN] Because Insertion Sort has tiny constant factors and sequential cache access, industrial hybrid algorithms like Python/Java Timsort and C++ Introsort switch from Merge/Quick Sort to Insertion Sort once subarrays shrink below ~16–32 elements. Note that Binary Insertion Sort uses Binary Search to find the insertion spot in O(log i) comparisons (reducing total comparisons to O(n log n)), yet shifting array elements still requires O(n^2) worst-case time.

[HI] कम ओवरहेड व उत्तम कैश प्रदर्शन के कारण Python का Timsort और C++ का Introsort छोटे सब-एरे (आकार <= 16 या 32) के लिए क्विक/मर्ज सॉर्ट के बजाय इंसर्शन सॉर्ट का ही उपयोग करते हैं। बाइनरी इंसर्शन सॉर्ट में स्थान खोजने हेतु बाइनरी सर्च से तुलनाएँ घटकर O(n log n) हो जाती हैं, किंतु एरे शिफ्टिंग के कारण कुल वर्स्ट-केस समय O(n^2) ही रहता है।

Syntax, Formula & Technical Example (Insertion Sort: Sorting Cards Metaphor, Online Algorithm)

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i], j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

Insertion Sort: Sorting Cards Metaphor, Online Algorithm Quick Reference & Comparison Table

Insertion Sort PropertyComplexity / MechanismExam Critical Note
Best & Nearly Sorted CaseTheta(n + I) => O(n) when I = O(n)Already sorted takes n-1 comparisons, 0 shifts
Worst Case (Reverse Order)n(n-1)/2 comparisons & shifts; O(n^2)Maximum inversions I = n*(n-1)/2
Online & Adaptive NatureSorts live streaming items incrementallyProcesses each new element without full input
Binary Insertion VariantO(n log n) comparisons, O(n^2) shiftsBinary search saves comparisons but NOT shifts

Insertion Sort: Sorting Cards Metaphor, Online Algorithm Top 20 Bilingual MCQs with Answers

Q1. What does the 'Online' property of Insertion Sort mean?

(इंसर्शन सॉर्ट के 'ऑनलाइन (Online)' गुण का क्या अर्थ है?)

(A) It requires an active internet connection

(B) It can sort a continuous stream of inputs one element at a time without seeing the whole dataset first

(C) It always runs in O(log n) time

(D) It downloads comparison tables from RAM

Correct Answer: (B)

[EN] Unlike Selection or Merge Sort, Insertion Sort inserts each newly arriving item directly into the existing sorted prefix.

[HI] बिना पूरा डेटा एक साथ प्राप्त किए, जैसे-जैसे नए तत्व आते जाते हैं उन्हें तुरंत सॉर्टेड हिस्से में शामिल किया जा सकता है।

Q2. Which input triggers the O(n) best-case running time in Insertion Sort?

(इंसर्शन सॉर्ट में O(n) बेस्ट-केस टाइम किस प्रकार के इनपुट पर मिलता है?)

(A) A strictly reverse-sorted array

(B) An already sorted array (ascending order)

(C) An array sorted with max at middle

(D) A randomly shuffled array

Correct Answer: (B)

[EN] When input is already ascending, arr[j] > key fails immediately at every i, causing only n - 1 comparisons and 0 shifts.

[HI] पहले से आरोही क्रम में सॉर्टेड एरे में while लूप की शर्त पहली जांच में ही असफल हो जाती है, जिससे मात्र n - 1 तुलनाएँ लगती हैं।

Q3. What is the worst-case time complexity of Binary Insertion Sort (using Binary Search to locate the insertion index)?

(इंसर्शन स्थान खोजने के लिए बाइनरी सर्च का उपयोग करने पर भी 'बाइनरी इंसर्शन सॉर्ट' की वर्स्ट-केस टाइम कॉम्प्लेक्सिटी क्या रहती है?)

(A) O(n)

(B) O(n^2)

(C) O(log n)

(D) O(n log n)

Correct Answer: (B)

[EN] Binary Search reduces comparisons to O(n log n), but shifting array elements right still takes O(n^2) operations in worst case.

[HI] बाइनरी सर्च से तुलनाएँ घटकर O(n log n) हो जाती हैं, परंतु एरे तत्वों को दाईं ओर शिफ्ट करने में अब भी O(n^2) समय लगता है।

Q4. Trace Insertion Sort on [12, 11, 13, 5, 6]. What is the state after inserting index i = 3 (value 5)?

(एरे [12, 11, 13, 5, 6] पर इंसर्शन सॉर्ट चलाते समय इंडेक्स i = 3 (मान 5) को इन्सर्ट करने के ठीक बाद एरे क्या होगा?)

(A) [11, 12, 5, 13, 6]

(B) [5, 11, 12, 13, 6]

(C) [11, 12, 13, 5, 6]

(D) [5, 6, 11, 12, 13]

Correct Answer: (B)

[EN] i=1: [11,12,13,5,6]; i=2: [11,12,13,5,6]; i=3 inserts 5 before 11 -> [5, 11, 12, 13, 6].

[HI] i=1 पर [11,12,13,5,6], i=2 पर कोई बदलाव नहीं, और i=3 पर 5 सबसे आगे लगकर [5, 11, 12, 13, 6] बनता है।

Q5. If an array of length n has at most I inversions, what is the exact asymptotic runtime of Insertion Sort?

(यदि n लंबाई के एरे में कुल I इनवर्जन हों, तो इंसर्शन सॉर्ट का सटीक असिम्प्टोटिक रनिंग टाइम क्या होगा?)

(A) Theta(I log n)

(B) Theta(n + I)

(C) Theta(n * I)

(D) Theta(n^2 / I)

Correct Answer: (B)

[EN] Outer loop executes n - 1 passes and inner loop performs exactly I shifts, giving Theta(n + I).

[HI] बाहरी लूप n-1 बार चलता है और आंतरिक लूप ठीक I शिफ्ट करता है, अतः कुल समय Theta(n + I) होता है।

Q6. Why do hybrid industrial sorters like Timsort (Python) and Introsort (C++) switch to Insertion Sort on small subarrays (n <= 32)?

(Timsort और Introsort जैसे औद्योगिक एल्गोरिदम छोटे सब-एरे (n <= 32) के लिए इंसर्शन सॉर्ट पर क्यों स्विच करते हैं?)

(A) Insertion Sort has very low overhead, no recursion cost, and superior CPU cache locality for tiny arrays

(B) Insertion Sort needs O(n) extra buffer memory

(C) Quick Sort fails mathematically on arrays smaller than 32

(D) Insertion Sort has O(1) worst-case time

Correct Answer: (A)

[EN] Simple sequential loop scanning with O(1) space beats O(n log n) recursion constants when n is small.

[HI] छोटे आकार पर रिकर्शन ओवरहेड न होने और उत्कृष्ट कैश लोकैलिटी के कारण इंसर्शन सॉर्ट व्यवहार में सबसे तेज साबित होता है।

Q7. In an already sorted array of 20 elements, how many comparisons and shifts does Insertion Sort perform?

(20 तत्वों के पहले से सॉर्टेड एरे पर इंसर्शन सॉर्ट कितनी तुलनाएँ और कितने शिफ्ट करेगा?)

(A) 19 comparisons and 19 shifts

(B) 20 comparisons and 20 shifts

(C) 19 comparisons and 0 shifts

(D) 190 comparisons and 0 shifts

Correct Answer: (C)

[EN] For i = 1..19 (19 iterations), each checks arr[i-1] > arr[i] once (false) and performs 0 shifts.

[HI] i = 1 से 19 तक हर चरण में केवल 1 तुलना (कुल 19) होती है और शर्त असत्य होने से 0 शिफ्ट होते हैं।

Q8. Which condition preserves the STABILITY of Insertion Sort?

(इंसर्शन सॉर्ट की स्टेबिलिटी (Stability) बनाए रखने के लिए कौन सी तुलना शर्त आवश्यक है?)

(A) Always start j at 0 instead of i - 1

(B) Swap key with arr[0] first

(C) Shift only while arr[j] > key (strict inequality)

(D) Shift while arr[j] >= key

Correct Answer: (C)

[EN] Stopping when arr[j] == key places the new key strictly to the right of earlier equal elements.

[HI] arr[j] > key लिखने से बराबर तत्व (arr[j] == key) मिलने पर लूप रुक जाता है और बाद वाला तत्व पुराने के दाईं ओर ही रहता है।

Q9. An array is 'k-sorted' if every element is at most k positions away from its sorted index (e.g., k = 3). What is Insertion Sort's runtime on it?

(यदि किसी एरे में हर तत्व अपने सही स्थान से अधिकतम k दूरी पर हो (k-sorted), तो इंसर्शन सॉर्ट की टाइम कॉम्प्लेक्सिटी क्या होगी?)

(A) O(n^2) always

(B) O(k * log n)

(C) O(k * n)

(D) O(n / k)

Correct Answer: (C)

[EN] Each element shifts at most k spots backward, so total work is at most k * n = O(kn) — linear for constant k!

[HI] हर तत्व को पीछे जाने में अधिकतम k कदम शिफ्ट होना पड़ता है, इसलिए कुल समय O(k * n) (नियत k के लिए O(n)) लगता है।

Q10. What is the auxiliary space complexity of Insertion Sort?

(इंसर्शन सॉर्ट की ऑक्सिलरी स्पेस कॉम्प्लेक्सिटी कितनी होती है?)

(A) O(1)

(B) O(k)

(C) O(n)

(D) O(log n)

Correct Answer: (A)

[EN] Only scalar variables i, j, and key are allocated alongside the input array.

[HI] इसमें इनपुट एरे के अलावा केवल i, j और key जैसे नियत वेरिएबल लगते हैं, अतः स्पेस O(1) है।

Q11. In Insertion Sort vs Selection Sort on an array of 100 elements sorted in REVERSE order, which algorithm performs far fewer data writes to memory?

(100 तत्वों के पूर्णतः रिवर्स-सॉर्टेड एरे पर मेमोरी में कम राइट्स (Writes) कौन करेगा: इंसर्शन या सिलेक्शन सॉर्ट?)

(A) Both write the exact same number of times

(B) Insertion Sort performs only 99 writes

(C) Insertion Sort (0 shifts)

(D) Selection Sort (max 99 swaps vs ~4,950 shifts in Insertion Sort)

Correct Answer: (D)

[EN] Reverse order maximizes inversions to 100*99/2 = 4,950 shifts in Insertion Sort, while Selection Sort still caps swaps at 99.

[HI] रिवर्स एरे में इंसर्शन सॉर्ट लगभग 4,950 शिफ्ट राइट्स करेगा जबकि सिलेक्शन सॉर्ट अधिकतम 99 स्वैप पर सीमित रहता है।

Q12. How can Insertion Sort run in O(n^2) worst time on a Linked List while still avoiding element shifts?

(सिंगली या डबली लिंक्ड लिस्ट पर एरे शिफ्ट किए बिना भी इंसर्शन सॉर्ट वर्स्ट केस में O(n^2) क्यों रहता है?)

(A) Locating the insertion spot by traversing the sorted prefix sequentially takes up to O(i) per node

(B) Because pointer relinking takes O(n) time each

(C) Because linked lists cannot store duplicates

(D) Because key allocation uses O(n^2) RAM

Correct Answer: (A)

[EN] Even though inserting a node takes O(1) pointer updates, scanning sorted nodes linearly to find where to insert takes up to i steps.

[HI] लिंक्ड लिस्ट में नोड जोड़ना O(1) है पर सही स्थान ढूंढने के लिए हर बार O(i) क्रमिक स्कैन करना पड़ता है, जिससे कुल समय O(n^2) रहता है।

Q13. Which classic sorting algorithm is generalized by Shell Sort by applying Insertion Sort across decreasing gap sequences?

(घटते हुए गैप (Gap Sequence) के साथ इंसर्शन सॉर्ट को सामान्यीकृत करके कौन सा एल्गोरिदम बनाया गया है?)

(A) Timsort

(B) Radix Sort

(C) Shell Sort

(D) Bucket Sort

Correct Answer: (C)

[EN] Shell Sort performs h-sorted Insertion Sort passes with decreasing gaps ending at gap = 1.

[HI] शेल सॉर्ट बड़े से छोटे गैप (अंत में gap = 1) पर इंसर्शन सॉर्ट चलाकर दूर के इनवर्जन को जल्दी हटा देता है।

Q14. What is the exact number of swaps/shifts performed by Insertion Sort on [5, 4, 3, 2, 1]?

(एरे [5, 4, 3, 2, 1] को आरोही क्रम में करने में इंसर्शन सॉर्ट कुल कितने शिफ्ट (Shifts) करेगा?)

(A) 15

(B) 10

(C) 5

(D) 4

Correct Answer: (B)

[EN] Shifts = 1 + 2 + 3 + 4 = 10 (matching total inversions n(n-1)/2 = 5*4/2 = 10).

[HI] शिफ्ट की संख्या = 1 + 2 + 3 + 4 = 10 होगी (जो कुल इनवर्जन n(n-1)/2 के बराबर है)।

Q15. Which statement is NOT true about Insertion Sort?

(इंसर्शन सॉर्ट के बारे में इनमें से कौन सा कथन सत्य नहीं है?)

(A) It is stable when using strict '>' comparison

(B) It is an adaptive sorting algorithm

(C) Its worst-case time complexity is O(n log n) when using arrays

(D) Its best-case time complexity is O(n)

Correct Answer: (C)

[EN] Worst-case time on arrays is O(n^2) because reverse-ordered data demands n(n-1)/2 shifts.

[HI] एरे पर इसका वर्स्ट-केस समय O(n log n) नहीं बल्कि O(n^2) होता है।

Q16. If you insert one single new element into an already sorted array of size n using one outer iteration of Insertion Sort logic, how long does it take?

(पहले से सॉर्टेड n आकार के एरे में एक नया तत्व सही जगह रखने में इंसर्शन लॉजिक को वर्स्ट केस में कितना समय लगेगा?)

(A) O(1)

(B) O(n log n)

(C) O(n)

(D) O(n^2)

Correct Answer: (C)

[EN] Shifting elements rightward to open a gap at index 0 takes up to n shifts => O(n).

[HI] यदि नया मान सबसे छोटा हो, तो पूरे n तत्वों को 1 स्थान खिसकाने में वर्स्ट केस O(n) समय लगता है।

Q17. Within Insertion Sort: Sorting Cards Metaphor, Online Algorithm, which insertion sort property directly maps to: "Theta(n + I) => O(n) when I = O(n)"?

(Insertion Sort: Sorting Cards Metaphor, Online Algorithm में कौन सा Insertion Sort Property सीधे "Theta(n + I) => O(n) when I = O(n)" से संबंधित है?)

(A) Worst Case (Reverse Order)

(B) Binary Insertion Variant

(C) Online & Adaptive Nature

(D) Best & Nearly Sorted Case

Correct Answer: (D)

[EN] In Insertion Sort: Sorting Cards Metaphor, Online Algorithm, 'Best & Nearly Sorted Case' handles 'Theta(n + I) => O(n) when I = O(n)' (Already sorted takes n-1 comparisons, 0 shifts).

[HI] Insertion Sort: Sorting Cards Metaphor, Online Algorithm में 'Best & Nearly Sorted Case' का कार्य/विवरण 'Theta(n + I) => O(n) when I = O(n)' (Already sorted takes n-1 comparisons, 0 shifts) है।

Q18. Which option accurately describes 'Worst Case (Reverse Order)' in Insertion Sort: Sorting Cards Metaphor, Online Algorithm?

(Insertion Sort: Sorting Cards Metaphor, Online Algorithm के संदर्भ में 'Worst Case (Reverse Order)' की सही विशेषता कौन सी है?)

(A) Sorts live streaming items incrementally

(B) O(n log n) comparisons, O(n^2) shifts

(C) Theta(n + I) => O(n) when I = O(n)

(D) n(n-1)/2 comparisons & shifts; O(n^2)

Correct Answer: (D)

[EN] 'Worst Case (Reverse Order)' provides 'n(n-1)/2 comparisons & shifts; O(n^2)' — key point: Maximum inversions I = n*(n-1)/2.

[HI] 'Worst Case (Reverse Order)' का मुख्य विवरण 'n(n-1)/2 comparisons & shifts; O(n^2)' है (Maximum inversions I = n*(n-1)/2)।

Q19. In Insertion Sort: Sorting Cards Metaphor, Online Algorithm, identify the correct parameter for the specification: "Sorts live streaming items incrementally".

(Insertion Sort: Sorting Cards Metaphor, Online Algorithm में "Sorts live streaming items incrementally" विवरण किस विकल्प के लिए सही है?)

(A) Best & Nearly Sorted Case

(B) Online & Adaptive Nature

(C) Worst Case (Reverse Order)

(D) Binary Insertion Variant

Correct Answer: (B)

[EN] 'Online & Adaptive Nature' corresponds to 'Sorts live streaming items incrementally' (Processes each new element without full input).

[HI] 'Online & Adaptive Nature' का संबंध 'Sorts live streaming items incrementally' (Processes each new element without full input) से है।

Q20. Considering Insertion Sort: Sorting Cards Metaphor, Online Algorithm, what key behavior defines 'Binary Insertion Variant'?

(Insertion Sort: Sorting Cards Metaphor, Online Algorithm में 'Binary Insertion Variant' की मुख्य भूमिका या मान क्या है?)

(A) O(n log n) comparisons, O(n^2) shifts

(B) n(n-1)/2 comparisons & shifts; O(n^2)

(C) Theta(n + I) => O(n) when I = O(n)

(D) Sorts live streaming items incrementally

Correct Answer: (A)

[EN] 'Binary Insertion Variant' represents 'O(n log n) comparisons, O(n^2) shifts' (Binary search saves comparisons but NOT shifts).

[HI] 'Binary Insertion Variant' का अर्थ/मान 'O(n log n) comparisons, O(n^2) shifts' है (Binary search saves comparisons but NOT shifts)।

Insertion Sort: Sorting Cards Metaphor, Online Algorithm — Exam FAQs

Q1: Why is Insertion Sort preferred over Bubble Sort and Selection Sort for small arrays?

छोटे एरे के लिए बबल और सिलेक्शन सॉर्ट की तुलना में इंसर्शन सॉर्ट को क्यों पसंद किया जाता है?

[EN] Insertion Sort adapts to partial order (doing fewer comparisons than Selection Sort on average), uses one-write shifts instead of 3-write swaps like Bubble Sort, and preserves stability.

[HI] इंसर्शन सॉर्ट आंशिक रूप से सॉर्टेड डेटा पर बहुत कम तुलनाएँ करता है, बबल की तरह 3-स्टेप स्वैप की जगह सिंगल शिफ्ट करता है, और स्टेबल भी रहता है।

Q2: How does Binary Insertion Sort differ from standard Insertion Sort?

बाइनरी इंसर्शन सॉर्ट मानक इंसर्शन सॉर्ट से कैसे भिन्न है?

[EN] It replaces the linear backward scan with Binary Search, lowering worst-case comparisons from O(n^2) to O(n log n)—useful when comparing objects (like long strings) is expensive—though shifts stay O(n^2).

[HI] इसमें सही जगह खोजने के लिए रैखिक जांच के बजाय बाइनरी सर्च लगता है जिससे तुलनाएँ O(n log n) रह जाती हैं (लंबी स्ट्रिंग्स में उपयोगी), पर तत्व शिफ्टिंग अब भी O(n^2) रहती है।

Q3: Does Insertion Sort require knowing total array size n beforehand?

क्या इंसर्शन सॉर्ट शुरू करने से पहले कुल तत्वों की संख्या n जानना जरूरी है?

[EN] No. Because it is an online algorithm, each new element arrives and gets inserted into the already sorted prefix immediately.

[HI] नहीं। एक ऑनलाइन एल्गोरिदम होने के कारण यह हर नए आने वाले तत्व को तुरंत मौजूदा सॉर्टेड हिस्से में व्यवस्थित कर सकता है।

Related Posts

  • Loading related posts...

Post a Comment

Search Topic Notes & 20 MCQs (Hindi / English)