"use strict"; const {Fragment: _Fragment, jsx: _jsx, jsxs: _jsxs} = arguments[0]; const {useMDXComponents: _provideComponents} = arguments[0]; function _createMdxContent(props) { const _components = { li: "li", ol: "ol", p: "p", span: "span", strong: "strong", table: "table", tbody: "tbody", td: "td", th: "th", thead: "thead", tr: "tr", ul: "ul", ..._provideComponents(), ...props.components }, {Analogy, Answer, Applications, Assessment, BlockDiagram, CodeBlock, ComparisonTable, ContentAttribution, DefinitionEntry, DefinitionGroup, English, Explanation, Hinglish, HowItWorks, ImportantQA, MCQ, Practical, Prompt, QAQuestion, Remember, SubTopicHeader, Theory, TopicOverview} = _components; if (!Analogy) _missingMdxReference("Analogy", true); if (!Answer) _missingMdxReference("Answer", true); if (!Applications) _missingMdxReference("Applications", true); if (!Assessment) _missingMdxReference("Assessment", true); if (!BlockDiagram) _missingMdxReference("BlockDiagram", true); if (!CodeBlock) _missingMdxReference("CodeBlock", true); if (!ComparisonTable) _missingMdxReference("ComparisonTable", true); if (!ContentAttribution) _missingMdxReference("ContentAttribution", true); if (!DefinitionEntry) _missingMdxReference("DefinitionEntry", true); if (!DefinitionGroup) _missingMdxReference("DefinitionGroup", true); if (!English) _missingMdxReference("English", true); if (!Explanation) _missingMdxReference("Explanation", true); if (!Hinglish) _missingMdxReference("Hinglish", true); if (!HowItWorks) _missingMdxReference("HowItWorks", true); if (!ImportantQA) _missingMdxReference("ImportantQA", true); if (!MCQ) _missingMdxReference("MCQ", true); if (!Practical) _missingMdxReference("Practical", true); if (!Prompt) _missingMdxReference("Prompt", true); if (!QAQuestion) _missingMdxReference("QAQuestion", true); if (!Remember) _missingMdxReference("Remember", true); if (!SubTopicHeader) _missingMdxReference("SubTopicHeader", true); if (!Theory) _missingMdxReference("Theory", true); if (!TopicOverview) _missingMdxReference("TopicOverview", true); return _jsxs(_Fragment, { children: [_jsxs(Theory, { children: [_jsx(SubTopicHeader, { id: "2.2", title: "Sorting: Bubble, Selection, Insertion, Quick and Merge Sort" }), _jsx(English, { children: _jsx(TopicOverview, { title: "Sorting Algorithms", topicId: "2.2", readingTime: "12 min read", difficulty: "Hard", children: _jsx(_components.p, { children: "Sorting is the process of arranging elements of an array in ascending or descending order. It makes searching, merging, and data analysis much easier. This subtopic covers five important sorting algorithms: Bubble Sort, Selection Sort, Insertion Sort, Quick Sort, and Merge Sort. Each algorithm has a different approach and time efficiency, making them suitable for different situations." }) }) }), _jsx(Hinglish, { children: _jsx(TopicOverview, { title: "Sorting Algorithms", topicId: "2.2", readingTime: "12 min read", difficulty: "Hard", children: _jsx(_components.p, { children: "Sorting array ke elements ko ascending ya descending order mein arrange karne ka process hai. Yeh searching, merging, aur data analysis ko bahut aasan banata hai. Yeh subtopic paanch important sorting algorithms cover karta hai: Bubble Sort, Selection Sort, Insertion Sort, Quick Sort, aur Merge Sort. Har algorithm ka approach aur time efficiency alag hai, jo unhe alag situations ke liye suitable banata hai." }) }) }), _jsxs(DefinitionGroup, { children: [_jsx(DefinitionEntry, { term: "Bubble Sort", children: _jsx(_components.p, { children: "Bubble Sort repeatedly compares adjacent elements and swaps them if they are in the wrong order. Larger elements \"bubble up\" to the end with each pass. Hinglish: Bubble Sort baar baar adjacent elements ko compare karta hai aur galat order mein hone par swap karta hai. Bade elements har pass mein end tak \"bubble up\" karte hain." }) }), _jsx(DefinitionEntry, { term: "Selection Sort", children: _jsx(_components.p, { children: "Selection Sort finds the minimum element from the unsorted portion and places it at the beginning, one position at a time. Hinglish: Selection Sort unsorted portion se minimum element dhundhta hai aur use beginning mein place karta hai, ek position ek time." }) }), _jsx(DefinitionEntry, { term: "Insertion Sort", children: _jsx(_components.p, { children: "Insertion Sort picks each element and inserts it into its correct position within the already sorted portion, like sorting playing cards in hand. Hinglish: Insertion Sort har element ko pick karta hai aur use already sorted portion mein uski sahi position par insert karta hai, jaise haath mein playing cards sort karna." }) }), _jsx(DefinitionEntry, { term: "Quick Sort", children: _jsx(_components.p, { children: "Quick Sort uses divide and conquer by selecting a pivot, partitioning the array around it, then recursively sorting the sub-arrays. Hinglish: Quick Sort divide and conquer use karta hai — pivot select karta hai, array ko uske around partition karta hai, phir sub-arrays ko recursively sort karta hai." }) }), _jsx(DefinitionEntry, { term: "Merge Sort", children: _jsx(_components.p, { children: "Merge Sort divides the array into halves, recursively sorts each half, then merges the two sorted halves into one sorted array. Hinglish: Merge Sort array ko halves mein divide karta hai, har half ko recursively sort karta hai, phir dono sorted halves ko ek sorted array mein merge karta hai." }) })] }), _jsxs(Explanation, { children: [_jsxs(English, { children: [_jsx("h3", { children: "📌 1. Bubble Sort — The \"Bubble\" That Rises" }), _jsx("p", { children: "Bubble Sort is the simplest sorting algorithm. It works like bubbles rising in water — the largest element \"bubbles up\" to the end of the array after each pass." }), _jsxs("p", { children: [_jsx("strong", { children: "How it works:" }), " Compare the first two elements. If the first is bigger, swap them. Move to the next pair and do the same. After one full pass through the array, the largest element is guaranteed to be at the last position. Now repeat for the remaining elements. After n-1 passes, the entire array is sorted."] }), _jsxs("p", { children: [_jsx("strong", { children: "Optimization:" }), " If during a pass NO swaps happen, the array is already sorted — we can stop early. This makes the best case O(n) for already sorted arrays."] }), _jsx("p", { children: _jsx("strong", { children: "Walkthrough — Sorting [5, 3, 8, 1, 2]:" }) }), _jsxs("p", { children: [_jsx("strong", { children: "Pass 1:" }), " Compare (5,3)→swap→[3,5,8,1,2]. Compare (5,8)→no swap. Compare (8,1)→swap→[3,5,1,8,2]. Compare (8,2)→swap→[3,5,1,2,8]. Largest (8) is now at the end!"] }), _jsxs("p", { children: [_jsx("strong", { children: "Pass 2:" }), " Compare (3,5)→no swap. Compare (5,1)→swap→[3,1,5,2,8]. Compare (5,2)→swap→[3,1,2,5,8]. Second largest (5) is in place."] }), _jsxs("p", { children: [_jsx("strong", { children: "Pass 3:" }), " Compare (3,1)→swap→[1,3,2,5,8]. Compare (3,2)→swap→[1,2,3,5,8]. Sorted!"] }), _jsxs("p", { children: [_jsx("strong", { children: "Time Complexity:" }), " Best O(n) with optimization, Average O(n²), Worst O(n²). Space: O(1) — in-place sorting."] })] }), _jsxs(Hinglish, { children: [_jsx("h3", { children: "📌 1. Bubble Sort — Woh \"Bubble\" Jo Upar Uthta Hai" }), _jsx("p", { children: "Bubble Sort sabse simple sorting algorithm hai. Yeh paani mein ubharte bubbles jaisa kaam karta hai — sabse bada element har pass mein array ke end tak \"bubble up\" hota hai." }), _jsxs("p", { children: [_jsx("strong", { children: "Kaise kaam karta hai:" }), " Pehle do elements compare karo. Agar pehla bada hai toh swap karo. Agle pair par jao aur wahi karo. Ek full pass ke baad sabse bada element last position par guaranteed hota hai. Ab baaki elements ke liye repeat karo. n-1 passes ke baad poora array sorted hota hai."] }), _jsxs("p", { children: [_jsx("strong", { children: "Optimization:" }), " Agar ek pass mein KOI swap nahi hua toh array already sorted hai — hum ruk sakte hain. Yeh best case ko O(n) bana deta hai already sorted arrays ke liye."] }), _jsx("p", { children: _jsx("strong", { children: "Walkthrough — [5, 3, 8, 1, 2] sort karna:" }) }), _jsxs("p", { children: [_jsx("strong", { children: "Pass 1:" }), " (5,3) compare→swap→[3,5,8,1,2]. (5,8) compare→no swap. (8,1) compare→swap→[3,5,1,8,2]. (8,2) compare→swap→[3,5,1,2,8]. Sabse bada (8) ab end par hai!"] }), _jsxs("p", { children: [_jsx("strong", { children: "Pass 2:" }), " (3,5) compare→no swap. (5,1) compare→swap→[3,1,5,2,8]. (5,2) compare→swap→[3,1,2,5,8]. Doosra sabse bada (5) apni jagah par hai."] }), _jsxs("p", { children: [_jsx("strong", { children: "Pass 3:" }), " (3,1) compare→swap→[1,3,2,5,8]. (3,2) compare→swap→[1,2,3,5,8]. Sorted!"] }), _jsxs("p", { children: [_jsx("strong", { children: "Time Complexity:" }), " Best O(n) with optimization, Average O(n²), Worst O(n²). Space: O(1) — in-place sorting."] })] }), _jsxs(HowItWorks, { title: "Bubble Sort — Step by Step Algorithm", children: [_jsxs(_components.ol, { children: ["\n", _jsx(_components.li, { children: "For i = 0 to n-2 (outer loop — number of passes):" }), "\n", _jsx(_components.li, { children: "For j = 0 to n-i-2 (inner loop — compare adjacent pairs):" }), "\n", _jsx(_components.li, { children: "If arr[j] > arr[j+1], swap them." }), "\n", _jsx(_components.li, { children: "After inner loop completes, the (i+1)th largest element is at position n-i-1." }), "\n", _jsx(_components.li, { children: "If no swaps occurred in a pass, break early (array is sorted)." }), "\n"] }), _jsx(_components.p, { children: "Key insight: After pass i, the last i+1 elements are in their final sorted positions." })] }), _jsx(CodeBlock, { language: "c", children: `// Bubble Sort — Optimized with early termination #include void bubbleSort(int arr[], int n) { int i, j, temp, swapped; for (i = 0; i < n - 1; i++) { swapped = 0; for (j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) { temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; swapped = 1; } } // If no swaps, array is already sorted if (swapped == 0) break; } } int main() { int arr[] = {5, 3, 8, 1, 2}; int n = 5, i; bubbleSort(arr, n); printf("Sorted array: "); for (i = 0; i < n; i++) printf("%d ", arr[i]); return 0; } // Output: Sorted array: 1 2 3 5 8` }), _jsxs(English, { children: [_jsx("h3", { children: "⚡ 2. Selection Sort — Pick the Smallest, Place It First" }), _jsx("p", { children: "Selection Sort works by repeatedly finding the minimum element from the unsorted portion and placing it at the beginning. Think of it as picking the shortest student from a line and moving them to the front, one by one." }), _jsxs("p", { children: [_jsx("strong", { children: "How it works:" }), " Start with the first position as the minimum. Scan the entire unsorted portion to find the actual minimum. Swap that minimum with the element at the current position. Now the sorted portion grows by one. Repeat until the entire array is sorted."] }), _jsxs("p", { children: [_jsx("strong", { children: "Key insight:" }), " Selection Sort always makes exactly n-1 swaps — one per pass. This is useful when write operations are expensive (e.g., writing to flash memory)."] }), _jsx("p", { children: _jsx("strong", { children: "Walkthrough — Sorting [64, 25, 12, 22, 11]:" }) }), _jsxs("p", { children: [_jsx("strong", { children: "Pass 1:" }), " Minimum is 11 (index 4). Swap 64 with 11 → [11, 25, 12, 22, 64]. Sorted: [11]"] }), _jsxs("p", { children: [_jsx("strong", { children: "Pass 2:" }), " Minimum of remaining is 12 (index 2). Swap 25 with 12 → [11, 12, 25, 22, 64]. Sorted: [11, 12]"] }), _jsxs("p", { children: [_jsx("strong", { children: "Pass 3:" }), " Minimum of remaining is 22 (index 3). Swap 25 with 22 → [11, 12, 22, 25, 64]. Sorted: [11, 12, 22]"] }), _jsxs("p", { children: [_jsx("strong", { children: "Pass 4:" }), " Minimum of remaining is 25. Swap 25 with 25 → no change. Sorted: [11, 12, 22, 25, 64]. Done!"] }), _jsxs("p", { children: [_jsx("strong", { children: "Time Complexity:" }), " Always O(n²) in all cases — it doesn't benefit from already sorted data. Space: O(1)."] })] }), _jsxs(Hinglish, { children: [_jsx("h3", { children: "⚡ 2. Selection Sort — Sabse Chhota Dhoondo, Aage Rakho" }), _jsx("p", { children: "Selection Sort baar baar unsorted portion se sabse chhota element dhundhke beginning mein rakhne se kaam karta hai. Sochiye jaise ek line mein se sabse chhote student ko dhoondhkar aage lana, ek ek karke." }), _jsxs("p", { children: [_jsx("strong", { children: "Kaise kaam karta hai:" }), " Pehle position ko minimum maano. Poore unsorted portion mein actual minimum dhundho. Uss minimum ko current position ke element se swap karo. Ab sorted portion ek se badh gaya. Tab tak repeat karo jab tak poora array sorted na ho jaye."] }), _jsxs("p", { children: [_jsx("strong", { children: "Key insight:" }), " Selection Sort mein hamesha exactly n-1 swaps hote hain — ek har pass mein. Yeh tab useful hai jab write operations mehenge ho (e.g., flash memory mein likhna)."] }), _jsx("p", { children: _jsx("strong", { children: "Walkthrough — [64, 25, 12, 22, 11] sort karna:" }) }), _jsxs("p", { children: [_jsx("strong", { children: "Pass 1:" }), " Minimum 11 hai (index 4). 64 ko 11 se swap karo → [11, 25, 12, 22, 64]. Sorted: [11]"] }), _jsxs("p", { children: [_jsx("strong", { children: "Pass 2:" }), " Baaki mein minimum 12 hai (index 2). 25 ko 12 se swap karo → [11, 12, 25, 22, 64]. Sorted: [11, 12]"] }), _jsxs("p", { children: [_jsx("strong", { children: "Pass 3:" }), " Baaki mein minimum 22 hai (index 3). 25 ko 22 se swap karo → [11, 12, 22, 25, 64]. Sorted: [11, 12, 22]"] }), _jsxs("p", { children: [_jsx("strong", { children: "Pass 4:" }), " Baaki mein minimum 25 hai. 25 ko 25 se swap karo → koi change nahi. Sorted: [11, 12, 22, 25, 64]. Ho gaya!"] }), _jsxs("p", { children: [_jsx("strong", { children: "Time Complexity:" }), " Hamesha O(n²) sabhi cases mein — already sorted data se koi faida nahi. Space: O(1)."] })] }), _jsx(HowItWorks, { title: "Selection Sort — Step by Step Algorithm", children: _jsxs(_components.ol, { children: ["\n", _jsx(_components.li, { children: "For i = 0 to n-2:" }), "\n", _jsx(_components.li, { children: "Set minIdx = i (assume current position has the minimum)." }), "\n", _jsx(_components.li, { children: "For j = i+1 to n-1 (scan the unsorted portion):" }), "\n", _jsx(_components.li, { children: "If arr[j] < arr[minIdx], update minIdx = j." }), "\n", _jsx(_components.li, { children: "After scanning, swap arr[i] with arr[minIdx]." }), "\n", _jsx(_components.li, { children: "Now elements 0..i are sorted." }), "\n"] }) }), _jsx(CodeBlock, { language: "c", children: `// Selection Sort #include void selectionSort(int arr[], int n) { int i, j, minIdx, temp; for (i = 0; i < n - 1; i++) { minIdx = i; for (j = i + 1; j < n; j++) { if (arr[j] < arr[minIdx]) minIdx = j; } // Swap the found minimum with current position temp = arr[i]; arr[i] = arr[minIdx]; arr[minIdx] = temp; } } int main() { int arr[] = {64, 25, 12, 22, 11}; int n = 5, i; selectionSort(arr, n); printf("Sorted array: "); for (i = 0; i < n; i++) printf("%d ", arr[i]); return 0; } // Output: Sorted array: 11 12 22 25 64` }), _jsxs(English, { children: [_jsx("h3", { children: "🃏 3. Insertion Sort — Like Sorting Cards in Hand" }), _jsx("p", { children: "Insertion Sort is exactly how most people sort playing cards in their hand. You pick one card at a time and insert it into its correct position among the cards you've already sorted." }), _jsxs("p", { children: [_jsx("strong", { children: "How it works:" }), " Start with the second element (first element is \"already sorted\" by itself). Store it as key. Compare it with elements to its left. Shift each larger element one position right. Insert the key at the correct position. Repeat for all remaining elements."] }), _jsxs("p", { children: [_jsx("strong", { children: "Key Strength:" }), " Extremely efficient for SMALL or NEARLY SORTED arrays. If the array is already sorted, it's O(n) — just one comparison per element. Also used as the base case in advanced algorithms like Quick Sort (for small sub-arrays)."] }), _jsx("p", { children: _jsx("strong", { children: "Walkthrough — Sorting [5, 2, 4, 6, 1, 3]:" }) }), _jsxs("p", { children: [_jsx("strong", { children: "Start:" }), " [5] is sorted. Key = 2. Compare with 5 → shift 5 right → insert 2 → [2, 5, 4, 6, 1, 3]"] }), _jsxs("p", { children: [_jsx("strong", { children: "Next:" }), " Key = 4. Compare with 5 → shift 5 right. Compare with 2 → stop. Insert 4 → [2, 4, 5, 6, 1, 3]"] }), _jsxs("p", { children: [_jsx("strong", { children: "Next:" }), " Key = 6. Compare with 5 → stop (6 > 5). Insert 6 → [2, 4, 5, 6, 1, 3]"] }), _jsxs("p", { children: [_jsx("strong", { children: "Next:" }), " Key = 1. Compare with 6,5,4,2 → all shift right → insert 1 → [1, 2, 4, 5, 6, 3]"] }), _jsxs("p", { children: [_jsx("strong", { children: "Next:" }), " Key = 3. Compare with 6,5,4 → shift right. Compare with 2 → stop. Insert 3 → [1, 2, 3, 4, 5, 6]. Sorted!"] }), _jsxs("p", { children: [_jsx("strong", { children: "Time Complexity:" }), " Best O(n) (already sorted), Average O(n²), Worst O(n²) (reverse sorted). Space: O(1)."] })] }), _jsxs(Hinglish, { children: [_jsx("h3", { children: "🃏 3. Insertion Sort — Haath Mein Cards Sort Karna Jaisa" }), _jsx("p", { children: "Insertion Sort bilkul woh hai jaise zyada tar log apne haath mein playing cards sort karte hain. Aap ek ek card uthate hain aur use pehle se sorted cards mein uski sahi jagah par insert karte hain." }), _jsxs("p", { children: [_jsx("strong", { children: "Kaise kaam karta hai:" }), " Doosre element se shuru karo (pehla element \"already sorted\" hai). Use key store karo. Use apne baayein elements se compare karo. Har bade element ko ek position right shift karo. Key ko sahi position par insert karo. Baaki sab remaining elements ke liye repeat karo."] }), _jsxs("p", { children: [_jsx("strong", { children: "Badi Strength:" }), " CHHOTI ya LAGBHAG SORTED arrays ke liye extremely efficient. Agar array already sorted hai toh O(n) hai — har element ke liye sirf ek comparison. Advanced algorithms mein bhi base case ke taur par use hota hai (e.g., Quick Sort mein chhoti sub-arrays ke liye)."] }), _jsx("p", { children: _jsx("strong", { children: "Walkthrough — [5, 2, 4, 6, 1, 3] sort karna:" }) }), _jsxs("p", { children: [_jsx("strong", { children: "Shuru:" }), " [5] sorted hai. Key = 2. 5 se compare→5 ko right shift→2 insert→[2, 5, 4, 6, 1, 3]"] }), _jsxs("p", { children: [_jsx("strong", { children: "Agla:" }), " Key = 4. 5 se compare→5 right shift. 2 se compare→ruk jao. 4 insert→[2, 4, 5, 6, 1, 3]"] }), _jsxs("p", { children: [_jsx("strong", { children: "Agla:" }), " Key = 6. 5 se compare→ruk jao (6 > 5). 6 insert→[2, 4, 5, 6, 1, 3]"] }), _jsxs("p", { children: [_jsx("strong", { children: "Agla:" }), " Key = 1. 6,5,4,2 se compare→saare right shift→1 insert→[1, 2, 4, 5, 6, 3]"] }), _jsxs("p", { children: [_jsx("strong", { children: "Agla:" }), " Key = 3. 6,5,4 se compare→right shift. 2 se compare→ruk jao. 3 insert→[1, 2, 3, 4, 5, 6]. Sorted!"] }), _jsxs("p", { children: [_jsx("strong", { children: "Time Complexity:" }), " Best O(n) (already sorted), Average O(n²), Worst O(n²) (reverse sorted). Space: O(1)."] })] }), _jsx(HowItWorks, { title: "Insertion Sort — Step by Step Algorithm", children: _jsxs(_components.ol, { children: ["\n", _jsx(_components.li, { children: "For i = 1 to n-1 (start from second element):" }), "\n", _jsx(_components.li, { children: "key = arr[i] (store current element)." }), "\n", _jsx(_components.li, { children: "j = i - 1 (start comparing with element to the left)." }), "\n", _jsx(_components.li, { children: "While j >= 0 AND arr[j] > key:" }), "\n", _jsx(_components.li, { children: "Shift arr[j] one position right: arr[j+1] = arr[j]." }), "\n", _jsx(_components.li, { children: "j-- (move left)." }), "\n", _jsx(_components.li, { children: "Insert key at arr[j+1]." }), "\n"] }) }), _jsx(CodeBlock, { language: "c", children: `// Insertion Sort #include void insertionSort(int arr[], int n) { int i, j, key; for (i = 1; i < n; i++) { key = arr[i]; j = i - 1; // Shift elements greater than key to the right while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; } } int main() { int arr[] = {5, 2, 4, 6, 1, 3}; int n = 6, i; insertionSort(arr, n); printf("Sorted array: "); for (i = 0; i < n; i++) printf("%d ", arr[i]); return 0; } // Output: Sorted array: 1 2 3 4 5 6` }), _jsxs(English, { children: [_jsx("h3", { children: "🔄 4. Quick Sort — The Divide and Conquer Champion" }), _jsx("p", { children: "Quick Sort is the most widely used sorting algorithm in practice. It uses divide and conquer: pick a pivot, partition the array around it (smaller left, larger right), then recursively sort the two halves." }), _jsxs("p", { children: [_jsx("strong", { children: "How it works:" }), " Choose a pivot (commonly the last element). Rearrange so all elements smaller than pivot go to the left, and all larger go to the right. The pivot is now in its final sorted position. Recursively apply the same process to the left and right sub-arrays."] }), _jsx("p", { children: _jsx("strong", { children: "Walkthrough — Sorting [8, 3, 1, 7, 0, 10, 2] with pivot = 2]:" }) }), _jsxs("p", { children: [_jsx("strong", { children: "Partition:" }), " Elements smaller than 2: [0, 1]. Pivot: [2]. Elements larger: [8, 3, 7, 10]. After partition: [0, 1, 2, 7, 10, 8, 3]. Pivot 2 is now in its final position!"] }), _jsxs("p", { children: [_jsx("strong", { children: "Recursion:" }), " Sort left [0, 1] → already sorted. Sort right [7, 10, 8, 3] → partition with pivot 3 → [3, 10, 8, 7] → sort right [10, 8, 7] → etc. Final: [0, 1, 2, 3, 7, 8, 10]."] }), _jsxs("p", { children: [_jsx("strong", { children: "Why is it fast?" }), " On average, each partition splits the array roughly in half, giving O(n log n). It's also cache-friendly because it accesses memory sequentially within partitions."] }), _jsxs("p", { children: [_jsx("strong", { children: "Time Complexity:" }), " Best/Average O(n log n), Worst O(n²) (when pivot is always the smallest or largest element — e.g., already sorted array with first element as pivot). Space: O(log n) for the recursion stack."] })] }), _jsxs(Hinglish, { children: [_jsx("h3", { children: "🔄 4. Quick Sort — Divide and Conquer Ka Champion" }), _jsx("p", { children: "Quick Sort sabse zyada use hone wala sorting algorithm hai practice mein. Yeh divide and conquer use karta hai: pivot choose karo, array ko uske around partition karo (chhote baayein, bade daayein), phir dono halves ko recursively sort karo." }), _jsxs("p", { children: [_jsx("strong", { children: "Kaise kaam karta hai:" }), " Pivot choose karo (aamtaur par last element). Rearrange karo taaki pivot se chhote elements baayein jaayein aur bade daayein. Pivot ab apni final sorted position par hai. Same process left aur right sub-arrays par recursively apply karo."] }), _jsx("p", { children: _jsx("strong", { children: "Walkthrough — [8, 3, 1, 7, 0, 10, 2] pivot = 2 se sort karna]:" }) }), _jsxs("p", { children: [_jsx("strong", { children: "Partition:" }), " 2 se chhote elements: [0, 1]. Pivot: [2]. Bade elements: [8, 3, 7, 10]. Partition ke baad: [0, 1, 2, 7, 10, 8, 3]. Pivot 2 ab apni final position par hai!"] }), _jsxs("p", { children: [_jsx("strong", { children: "Recursion:" }), " Left [0, 1] sort karo → already sorted. Right [7, 10, 8, 3] sort karo → pivot 3 se partition→[3, 10, 8, 7]→right sort karo [10, 8, 7]→etc. Final: [0, 1, 2, 3, 7, 8, 10]."] }), _jsxs("p", { children: [_jsx("strong", { children: "Yeh fast kyun hai?" }), " On average, har partition array ko roughly aadha karta hai, jo O(n log n) deta hai. Yeh cache-friendly bhi hai kyunki partitions ke andar memory sequentially access hoti hai."] }), _jsxs("p", { children: [_jsx("strong", { children: "Time Complexity:" }), " Best/Average O(n log n), Worst O(n²) (jab pivot hamesha smallest ya largest ho — e.g., already sorted array mein first element as pivot). Space: O(log n) recursion stack ke liye."] })] }), _jsx(HowItWorks, { title: "Quick Sort — Step by Step Algorithm", children: _jsxs(_components.ol, { children: ["\n", _jsx(_components.li, { children: "If low >= high, return (base case: sub-array has 0 or 1 element)." }), "\n", _jsx(_components.li, { children: "Choose pivot = arr[high] (last element)." }), "\n", _jsxs(_components.li, { children: ["Partition: Rearrange so smaller elements go left, larger go right.", "\n", _jsxs(_components.ul, { children: ["\n", _jsx(_components.li, { children: "i = low - 1 (index for smaller elements)." }), "\n", _jsx(_components.li, { children: "For j = low to high-1: if arr[j] < pivot, increment i and swap arr[i] with arr[j]." }), "\n", _jsx(_components.li, { children: "Finally, swap arr[i+1] with arr[high] (place pivot in correct position)." }), "\n"] }), "\n"] }), "\n", _jsx(_components.li, { children: "pivotIndex = i + 1 (pivot is now sorted)." }), "\n", _jsx(_components.li, { children: "Recursively sort left: quickSort(arr, low, pivotIndex - 1)." }), "\n", _jsx(_components.li, { children: "Recursively sort right: quickSort(arr, pivotIndex + 1, high)." }), "\n"] }) }), _jsx(CodeBlock, { language: "c", children: `// Quick Sort #include int partition(int arr[], int low, int high) { int pivot = arr[high]; int i = low - 1, j, temp; for (j = low; j < high; j++) { if (arr[j] < pivot) { i++; temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } // Place pivot in correct position temp = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = temp; return i + 1; } void quickSort(int arr[], int low, int high) { if (low < high) { int pi = partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } } int main() { int arr[] = {8, 3, 1, 7, 0, 10, 2}; int n = 7, i; quickSort(arr, 0, n - 1); printf("Sorted array: "); for (i = 0; i < n; i++) printf("%d ", arr[i]); return 0; } // Output: Sorted array: 0 1 2 3 7 8 10` }), _jsx(BlockDiagram, { title: "Quick Sort Partitioning — Visual", children: _jsxs("pre", { children: [_jsx(_components.p, { children: "Array: [8, 3, 1, 7, 0, 10, 2] Pivot = 2" }), _jsx(_components.p, { children: "Step-by-step partition:\nj=0: arr[0]=8 >= 2, no swap\nj=1: arr[1]=3 >= 2, no swap\nj=2: arr[2]=1 < 2, i=0, swap arr[0] with arr[2] → [1,3,8,7,0,10,2]\nj=3: arr[3]=7 >= 2, no swap\nj=4: arr[4]=0 < 2, i=1, swap arr[1] with arr[4] → [1,0,8,7,3,10,2]\nj=5: arr[5]=10 >= 2, no swap" }), _jsx(_components.p, { children: "Place pivot: swap arr[2] with arr[6] → [1,0,2,7,3,10,8]" }), _jsx(_components.p, { children: "Result: [1,0] < [2] < [7,3,10,8]\nPivot 2 is in its FINAL sorted position!" })] }) }), _jsxs(English, { children: [_jsx("h3", { children: "🔀 5. Merge Sort — Guaranteed Performance" }), _jsx("p", { children: "Merge Sort is the most reliable sorting algorithm — it guarantees O(n log n) time in ALL cases (best, average, worst). It works by splitting the array in half, sorting each half, then merging them back together in sorted order." }), _jsxs("p", { children: [_jsx("strong", { children: "How it works:" }), " Divide the array into two halves. Recursively sort each half. Merge the two sorted halves into one sorted array. The key operation is \"merge\" — comparing the first elements of each half and placing the smaller one first."] }), _jsx("p", { children: _jsx("strong", { children: "Walkthrough — Sorting [38, 27, 43, 3, 9, 82, 10]:" }) }), _jsxs("p", { children: [_jsx("strong", { children: "Divide:" }), " Left [38, 27, 43, 3], Right [9, 82, 10]"] }), _jsxs("p", { children: [_jsx("strong", { children: "Divide again:" }), " [38, 27] and [43, 3] and [9, 82] and [10]"] }), _jsxs("p", { children: [_jsx("strong", { children: "Divide again:" }), " [38] [27] [43] [3] [9] [82] [10] — all single elements!"] }), _jsxs("p", { children: [_jsx("strong", { children: "Merge:" }), " [27, 38] [3, 43] [9, 82] [10] → [3, 27, 38, 43] [9, 10, 82] → [3, 9, 10, 27, 38, 42, 82]"] }), _jsxs("p", { children: [_jsx("strong", { children: "Time Complexity:" }), " Always O(n log n) — the array is always divided in half (log n levels), and merging takes O(n) at each level. Space: O(n) — needs a temporary array for merging."] })] }), _jsxs(Hinglish, { children: [_jsx("h3", { children: "🔀 5. Merge Sort — Guaranteed Performance" }), _jsx("p", { children: "Merge Sort sabse reliable sorting algorithm hai — yeh O(n log n) time HAR case mein guarantee karta hai (best, average, worst). Yeh array ko aadha karke, har aadha sort karke, phir sorted order mein merge karke kaam karta hai." }), _jsxs("p", { children: [_jsx("strong", { children: "Kaise kaam karta hai:" }), " Array ko do halves mein divide karo. Har half ko recursively sort karo. Dono sorted halves ko ek sorted array mein merge karo. Key operation \"merge\" hai — har half ke pehle elements compare karo aur chhota pehle rakho."] }), _jsx("p", { children: _jsx("strong", { children: "Walkthrough — [38, 27, 43, 3, 9, 82, 10] sort karna]:" }) }), _jsxs("p", { children: [_jsx("strong", { children: "Divide:" }), " Left [38, 27, 43, 3], Right [9, 82, 10]"] }), _jsxs("p", { children: [_jsx("strong", { children: "Phir divide:" }), " [38, 27] aur [43, 3] aur [9, 82] aur [10]"] }), _jsxs("p", { children: [_jsx("strong", { children: "Phir divide:" }), " [38] [27] [43] [3] [9] [82] [10] — sab single elements!"] }), _jsxs("p", { children: [_jsx("strong", { children: "Merge:" }), " [27, 38] [3, 43] [9, 82] [10] → [3, 27, 38, 43] [9, 10, 82] → [3, 9, 10, 27, 38, 42, 82]"] }), _jsxs("p", { children: [_jsx("strong", { children: "Time Complexity:" }), " Hamesha O(n log n) — array hamesha aadha hota hai (log n levels), aur har level par merge O(n) leta hai. Space: O(n) — merge ke liye temporary array chahiye."] })] }), _jsx(HowItWorks, { title: "Merge Sort — Step by Step Algorithm", children: _jsxs(_components.ol, { children: ["\n", _jsx(_components.li, { children: "Divide: Split the array into two halves (left half and right half)." }), "\n", _jsx(_components.li, { children: "Conquer: Recursively sort the left half." }), "\n", _jsx(_components.li, { children: "Conquer: Recursively sort the right half." }), "\n", _jsxs(_components.li, { children: ["Combine: Merge the two sorted halves into one sorted array.", "\n", _jsxs(_components.ul, { children: ["\n", _jsx(_components.li, { children: "Use two pointers, one for each half." }), "\n", _jsx(_components.li, { children: "Compare elements at both pointers, place the smaller one first." }), "\n", _jsx(_components.li, { children: "Repeat until all elements are merged." }), "\n"] }), "\n"] }), "\n", _jsx(_components.li, { children: "Base case: When a sub-array has only 1 element, it's already sorted." }), "\n"] }) }), _jsx(CodeBlock, { language: "c", children: `// Merge Sort #include void merge(int arr[], int left, int mid, int right) { int n1 = mid - left + 1; int n2 = right - mid; int L[n1], R[n2]; int i, j, k; // Copy data to temp arrays for (i = 0; i < n1; i++) L[i] = arr[left + i]; for (j = 0; j < n2; j++) R[j] = arr[mid + 1 + j]; // Merge temp arrays back i = 0; j = 0; k = left; while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k] = L[i]; i++; } else { arr[k] = R[j]; j++; } k++; } while (i < n1) { arr[k] = L[i]; i++; k++; } while (j < n2) { arr[k] = R[j]; j++; k++; } } void mergeSort(int arr[], int left, int right) { if (left < right) { int mid = (left + right) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid + 1, right); merge(arr, left, mid, right); } } int main() { int arr[] = {38, 27, 43, 3, 9, 82, 10}; int n = 7, i; mergeSort(arr, 0, n - 1); printf("Sorted array: "); for (i = 0; i < n; i++) printf("%d ", arr[i]); return 0; } // Output: Sorted array: 3 9 10 27 38 43 82` }), _jsx(ComparisonTable, { title: "Complete Comparison of All Sorting Algorithms", children: _jsxs(_components.table, { children: [_jsx(_components.thead, { children: _jsxs(_components.tr, { children: [_jsx(_components.th, { style: { textAlign: "left" }, children: "Algorithm" }), _jsx(_components.th, { style: { textAlign: "left" }, children: "Best Case" }), _jsx(_components.th, { style: { textAlign: "left" }, children: "Average Case" }), _jsx(_components.th, { style: { textAlign: "left" }, children: "Worst Case" }), _jsx(_components.th, { style: { textAlign: "left" }, children: "Space" }), _jsx(_components.th, { style: { textAlign: "left" }, children: "Stable?" }), _jsx(_components.th, { style: { textAlign: "left" }, children: "In-Place?" })] }) }), _jsxs(_components.tbody, { children: [_jsxs(_components.tr, { children: [_jsx(_components.td, { style: { textAlign: "left" }, children: "Bubble Sort" }), _jsx(_components.td, { style: { textAlign: "left" }, children: "O(n)" }), _jsx(_components.td, { style: { textAlign: "left" }, children: "O(n²)" }), _jsx(_components.td, { style: { textAlign: "left" }, children: "O(n²)" }), _jsx(_components.td, { style: { textAlign: "left" }, children: "O(1)" }), _jsx(_components.td, { style: { textAlign: "left" }, children: "Yes" }), _jsx(_components.td, { style: { textAlign: "left" }, children: "Yes" })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { style: { textAlign: "left" }, children: "Selection Sort" }), _jsx(_components.td, { style: { textAlign: "left" }, children: "O(n²)" }), _jsx(_components.td, { style: { textAlign: "left" }, children: "O(n²)" }), _jsx(_components.td, { style: { textAlign: "left" }, children: "O(n²)" }), _jsx(_components.td, { style: { textAlign: "left" }, children: "O(1)" }), _jsx(_components.td, { style: { textAlign: "left" }, children: "No" }), _jsx(_components.td, { style: { textAlign: "left" }, children: "Yes" })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { style: { textAlign: "left" }, children: "Insertion Sort" }), _jsx(_components.td, { style: { textAlign: "left" }, children: "O(n)" }), _jsx(_components.td, { style: { textAlign: "left" }, children: "O(n²)" }), _jsx(_components.td, { style: { textAlign: "left" }, children: "O(n²)" }), _jsx(_components.td, { style: { textAlign: "left" }, children: "O(1)" }), _jsx(_components.td, { style: { textAlign: "left" }, children: "Yes" }), _jsx(_components.td, { style: { textAlign: "left" }, children: "Yes" })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { style: { textAlign: "left" }, children: "Quick Sort" }), _jsx(_components.td, { style: { textAlign: "left" }, children: "O(n log n)" }), _jsx(_components.td, { style: { textAlign: "left" }, children: "O(n log n)" }), _jsx(_components.td, { style: { textAlign: "left" }, children: "O(n²)" }), _jsx(_components.td, { style: { textAlign: "left" }, children: "O(log n)" }), _jsx(_components.td, { style: { textAlign: "left" }, children: "No" }), _jsx(_components.td, { style: { textAlign: "left" }, children: "Yes" })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { style: { textAlign: "left" }, children: "Merge Sort" }), _jsx(_components.td, { style: { textAlign: "left" }, children: "O(n log n)" }), _jsx(_components.td, { style: { textAlign: "left" }, children: "O(n log n)" }), _jsx(_components.td, { style: { textAlign: "left" }, children: "O(n log n)" }), _jsx(_components.td, { style: { textAlign: "left" }, children: "O(n)" }), _jsx(_components.td, { style: { textAlign: "left" }, children: "Yes" }), _jsx(_components.td, { style: { textAlign: "left" }, children: "No" })] })] })] }) }), _jsx(Remember, { children: _jsxs(_components.ul, { children: ["\n", _jsx(_components.li, { children: "Bubble Sort: Simplest, O(n²), good for nearly sorted data with optimization." }), "\n", _jsx(_components.li, { children: "Selection Sort: Always O(n²), but minimal swaps (n-1). Good when writes are expensive." }), "\n", _jsx(_components.li, { children: "Insertion Sort: Best for small/nearly sorted data. O(n) when already sorted." }), "\n", _jsx(_components.li, { children: "Quick Sort: Fastest in practice, O(n log n) average, but O(n²) worst case." }), "\n", _jsx(_components.li, { children: "Merge Sort: Guaranteed O(n log n) but needs O(n) extra space. Best for linked lists." }), "\n", _jsx(_components.li, { children: "For small arrays (n < 20), Insertion Sort is often fastest in practice." }), "\n", _jsx(_components.li, { children: "\"Stable\" means equal elements preserve their original relative order." }), "\n"] }) }), _jsx(Analogy, { children: _jsxs(_components.p, { children: [_jsx("b", { children: "Analogy: Sorting Students by Height in a Line" }), _jsx("br", {}), "\n", _jsx("strong", { children: "Bubble Sort:" }), " Compare two neighbors. If left is taller, swap them. Walk down the line. After one round, the tallest is at the end. Repeat until sorted.", _jsx("br", {}), "\n", _jsx("strong", { children: "Selection Sort:" }), " Find the shortest student in the line, swap them to the front. Now find the shortest among the remaining, swap to second position. Repeat.", _jsx("br", {}), "\n", _jsx("strong", { children: "Insertion Sort:" }), " Like sorting cards in your hand. Pick the next student, compare with those already sorted, and insert them in the right spot.", _jsx("br", {}), "\n", _jsx("strong", { children: "Quick Sort:" }), " Pick one student as \"pivot.\" Everyone shorter goes left, everyone taller goes right. Then sort each group the same way.", _jsx("br", {}), "\n", _jsx("strong", { children: "Merge Sort:" }), " Split the class in half. Sort each half separately. Then merge the two sorted halves by comparing the front of each line."] }) }), _jsx(Applications, { title: "Applications", children: _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Bubble Sort" }), ": Educational purposes, small datasets, detecting if array is already sorted (with optimization flag)."] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Selection Sort" }), ": When write/swap operations are expensive (e.g., flash memory), small datasets."] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Insertion Sort" }), ": Small datasets, nearly sorted data, as subroutine in Quick Sort for small sub-arrays, online sorting (data arriving one at a time)."] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Quick Sort" }), ": General-purpose sorting (C qsort, Java Arrays.sort for primitives), database systems, most standard library implementations."] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Merge Sort" }), ": External sorting (sorting large files that don't fit in memory), linked list sorting, stable sorting requirements, parallelizable sorting."] }), "\n"] }) })] })] }), "\n", _jsx(Practical, { children: _jsxs(ImportantQA, { children: [_jsxs(QAQuestion, { marks: 2, children: [_jsx(Prompt, { children: "Define sorting and state its purpose." }), _jsxs(Answer, { children: [_jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Sorting" }), " is the process of arranging elements of an array in a specific order (ascending or descending)."] }), _jsx(_components.p, { children: "Its purpose is to make data organized so that operations like searching, merging, and analysis become faster and easier." })] })] }), _jsxs(QAQuestion, { marks: 4, children: [_jsx(Prompt, { children: "Explain Bubble Sort with its time complexity." }), _jsxs(Answer, { children: [_jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Bubble Sort" }), " repeatedly compares adjacent elements and swaps them if they are in the wrong order."] }), _jsx(_components.p, { children: "In each pass, the largest unsorted element moves to its correct position at the end." }), _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Time Complexity" }), ":"] }), _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: ["Best case: ", _jsx(_components.span, { className: "katex", children: _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" })] }) }) }), " (already sorted, with optimized flag)"] }), "\n", _jsxs(_components.li, { children: ["Average and Worst: ", _jsx(_components.span, { className: "katex", children: _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1.0641em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "msupsub", children: _jsx(_components.span, { className: "vlist-t", children: _jsx(_components.span, { className: "vlist-r", children: _jsx(_components.span, { className: "vlist", style: { height: "0.8141em" }, children: _jsxs(_components.span, { style: { top: "-3.063em", marginRight: "0.05em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "2.7em" } }), _jsx(_components.span, { className: "sizing reset-size6 size3 mtight", children: _jsx(_components.span, { className: "mord mtight", children: "2" }) })] }) }) }) }) })] }), _jsx(_components.span, { className: "mclose", children: ")" })] }) }) })] }), "\n"] }), _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Space Complexity" }), ": ", _jsx(_components.span, { className: "katex", children: _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord", children: "1" }), _jsx(_components.span, { className: "mclose", children: ")" })] }) }) }), " (in-place sorting)"] }), _jsx(_components.p, { children: "It is simple to implement but not efficient for large datasets." })] })] }), _jsxs(QAQuestion, { marks: 6, children: [_jsx(Prompt, { children: "Compare Quick Sort and Merge Sort with their advantages and disadvantages." }), _jsxs(Answer, { children: [_jsx(ComparisonTable, { title: "Quick Sort vs Merge Sort", children: _jsxs(_components.table, { children: [_jsx(_components.thead, { children: _jsxs(_components.tr, { children: [_jsx(_components.th, { children: "Aspect" }), _jsx(_components.th, { children: "Quick Sort" }), _jsx(_components.th, { children: "Merge Sort" })] }) }), _jsxs(_components.tbody, { children: [_jsxs(_components.tr, { children: [_jsx(_components.td, { children: "Approach" }), _jsx(_components.td, { children: "Partition in place" }), _jsx(_components.td, { children: "Divide then merge" })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { children: "Average Time" }), _jsx(_components.td, { children: _jsx(_components.span, { className: "katex", children: _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsxs(_components.span, { className: "mop", children: ["lo", _jsx(_components.span, { style: { marginRight: "0.0139em" }, children: "g" })] }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" })] }) }) }) }), _jsx(_components.td, { children: _jsx(_components.span, { className: "katex", children: _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsxs(_components.span, { className: "mop", children: ["lo", _jsx(_components.span, { style: { marginRight: "0.0139em" }, children: "g" })] }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" })] }) }) }) })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { children: "Worst Time" }), _jsx(_components.td, { children: _jsx(_components.span, { className: "katex", children: _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1.0641em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "msupsub", children: _jsx(_components.span, { className: "vlist-t", children: _jsx(_components.span, { className: "vlist-r", children: _jsx(_components.span, { className: "vlist", style: { height: "0.8141em" }, children: _jsxs(_components.span, { style: { top: "-3.063em", marginRight: "0.05em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "2.7em" } }), _jsx(_components.span, { className: "sizing reset-size6 size3 mtight", children: _jsx(_components.span, { className: "mord mtight", children: "2" }) })] }) }) }) }) })] }), _jsx(_components.span, { className: "mclose", children: ")" })] }) }) }) }), _jsx(_components.td, { children: _jsx(_components.span, { className: "katex", children: _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsxs(_components.span, { className: "mop", children: ["lo", _jsx(_components.span, { style: { marginRight: "0.0139em" }, children: "g" })] }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" })] }) }) }) })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { children: "Space" }), _jsx(_components.td, { children: _jsx(_components.span, { className: "katex", children: _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsxs(_components.span, { className: "mop", children: ["lo", _jsx(_components.span, { style: { marginRight: "0.0139em" }, children: "g" })] }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" })] }) }) }) }), _jsx(_components.td, { children: _jsx(_components.span, { className: "katex", children: _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" })] }) }) }) })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { children: "Stable?" }), _jsx(_components.td, { children: "No" }), _jsx(_components.td, { children: "Yes" })] })] })] }) }), _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Quick Sort Advantages" }), ":"] }), _jsxs(_components.ul, { children: ["\n", _jsx(_components.li, { children: "Faster in practice due to cache locality." }), "\n", _jsx(_components.li, { children: "In-place sorting (less memory)." }), "\n"] }), _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Quick Sort Disadvantages" }), ":"] }), _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: ["Worst case ", _jsx(_components.span, { className: "katex", children: _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1.0641em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "msupsub", children: _jsx(_components.span, { className: "vlist-t", children: _jsx(_components.span, { className: "vlist-r", children: _jsx(_components.span, { className: "vlist", style: { height: "0.8141em" }, children: _jsxs(_components.span, { style: { top: "-3.063em", marginRight: "0.05em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "2.7em" } }), _jsx(_components.span, { className: "sizing reset-size6 size3 mtight", children: _jsx(_components.span, { className: "mord mtight", children: "2" }) })] }) }) }) }) })] }), _jsx(_components.span, { className: "mclose", children: ")" })] }) }) }), " on already sorted data with bad pivot."] }), "\n", _jsx(_components.li, { children: "Not stable." }), "\n"] }), _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Merge Sort Advantages" }), ":"] }), _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: ["Guaranteed ", _jsx(_components.span, { className: "katex", children: _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsxs(_components.span, { className: "mop", children: ["lo", _jsx(_components.span, { style: { marginRight: "0.0139em" }, children: "g" })] }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" })] }) }) }), " in all cases."] }), "\n", _jsx(_components.li, { children: "Stable sort." }), "\n"] }), _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Merge Sort Disadvantages" }), ":"] }), _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: ["Requires extra ", _jsx(_components.span, { className: "katex", children: _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" })] }) }) }), " memory."] }), "\n", _jsx(_components.li, { children: "Slower than Quick Sort in practice for arrays." }), "\n"] }), _jsx(_components.p, { children: "Quick Sort is used in most standard libraries, while Merge Sort is preferred for external sorting and linked lists." })] })] })] }) }), "\n", _jsxs(Assessment, { topicId: "2.2", children: [_jsx(MCQ, { questions: [{ "id": "72b1766d-5a92-4877-a6b6-331e78e6d338", "q": "In Bubble Sort, elements are compared:", "options": ["Adjacent pairs only", "First and last only", "Random pairs", "All pairs at once"], "answer": 0, "hint": "Bubble sort compares adjacent elements and swaps if needed.", "explanation": "Bubble sort works by repeatedly comparing adjacent elements and swapping them." }, { "id": "096e358d-d3b1-45e9-ae05-e839fae130f0", "q": "Selection Sort works by:", "options": ["Swapping adjacent elements", "Finding minimum and placing it at the beginning", "Dividing array in halves", "Merging sorted arrays"], "answer": 1, "hint": "Selection sort finds the minimum first.", "explanation": "Selection sort finds the minimum from unsorted portion and places it at the beginning." }, { "id": "29db40ee-1df6-445c-b60a-9776e215c205", "q": "Insertion Sort is similar to:", "options": ["Splitting a deck", "Finding a card", "Sorting playing cards in your hand", "Dealing cards"], "answer": 2, "hint": "Insertion sort is like sorting cards in hand.", "explanation": "Insertion sort picks each element and inserts it into its correct position in the sorted portion." }, { "id": "78af6f3f-23c6-4520-9ee5-73d68380855a", "q": "In Quick Sort, the key operation is:", "options": ["Partitioning around a pivot", "Merging halves", "Finding minimum", "Swapping adjacent only"], "answer": 0, "hint": "Quick sort uses partition around a pivot.", "explanation": "Quick sort picks a pivot and partitions elements around it." }, { "id": "37655e15-01d9-44ad-929d-4bde13e5c142", "q": "Merge Sort works by:", "options": ["Swapping adjacent pairs", "Finding minimum each time", "Inserting elements one by one", "Dividing in halves, sorting, then merging"], "answer": 3, "hint": "Merge sort always divides in half.", "explanation": "Merge sort divides the array into two halves, sorts each, then merges them." }, { "id": "c7076879-d4ea-4ed9-b5ff-56bfa1d6c7f9", "q": "The worst-case time complexity of Bubble Sort is:", "options": ["$O(n)$", "$O(n^2)$", "$O(n \\\\log n)$", "$O(\\\\log n)$"], "answer": 1, "hint": "Bubble sort worst case is O(n^2).", "explanation": "Bubble sort takes O(n^2) in the worst case due to nested loops." }, { "id": "17eca8b0-2ed1-4c37-8fe0-1eece0893d59", "q": "Merge Sort's space complexity is:", "options": ["$O(1)$", "$O(\\\\log n)$", "$O(n)$", "$O(n^2)$"], "answer": 2, "hint": "Merge sort needs O(n) extra space.", "explanation": "Merge sort requires O(n) additional memory to merge the two halves." }, { "id": "183fbe3b-613d-4ab8-81e4-7180a175cba8", "q": "Bubble Sort is not suitable for large datasets because:", "options": ["It has $O(n^2)$ time complexity", "It needs extra memory", "It cannot sort numbers", "It only works on strings"], "answer": 0, "hint": "Bubble sort is simple but not efficient for large data.", "explanation": "Bubble sort has O(n^2) time complexity, making it slow for large datasets." }, { "id": "d8473fd0-3b16-4613-8e57-6483cd2ce08b", "q": "The worst-case time complexity of Quick Sort is:", "options": ["$O(n \\\\log n)$", "$O(n^2)$", "$O(n)$", "$O(\\\\log n)$"], "answer": 1, "hint": "Quick sort worst case is O(n^2).", "explanation": "Quick sort degrades to O(n^2) when pivot choices are poor (e.g., sorted data with first element as pivot)." }, { "id": "6b024561-a787-4bf2-89bc-e0b857e116af", "q": "Which sorting algorithm guarantees O(n log n) in all cases?", "options": ["Bubble Sort", "Selection Sort", "Quick Sort", "Merge Sort"], "answer": 3, "hint": "Merge sort gives O(n log n) guarantee.", "explanation": "Merge sort guarantees O(n log n) in all cases (best, average, and worst)." }], topicId: "2.2" }), _jsx(ContentAttribution, { sourceTitle: "Curriculum Reference", sourceUrl: "https://learningway.in", professor: "Faculty Review Team", model: "Curriculum AI", seoTitle: "Sorting", seoDesc: "Master Sorting with comprehensive notes, real-world examples, and practice quiz on LearningWay.", seoKeywords: "sorting, sorting notes, sorting examples, diploma engineering notes, practice quiz, learningway" })] })] }); } function MDXContent(props = {}) { const {wrapper: MDXLayout} = { ..._provideComponents(), ...props.components }; return MDXLayout ? _jsx(MDXLayout, { ...props, children: _jsx(_createMdxContent, { ...props }) }) : _createMdxContent(props); } return { default: MDXContent }; function _missingMdxReference(id, component) { throw new Error("Expected " + (component ? "component" : "object") + " `" + id + "` to be defined: you likely forgot to import, pass, or provide it."); }