Sorting Algorithms in Python
Chapter 5: Computer Science - Ultimate Study Guide | NCERT Class 12 Notes, Questions, Code Examples & Quiz 2025
Full Chapter Summary & Detailed Notes - Sorting Algorithms in Python Class 12 NCERT
Overview & Key Concepts
- Chapter Goal: Understand sorting as arranging elements; focus on Bubble, Selection, Insertion sorts (O(n²)); time complexity analysis. Exam Focus: Algorithms 5.1-5.3, Programs 5-1 to 5-3, Figures 5.1-5.3 passes; 2025 Updates: Emphasis on efficiency for big data, Python optimizations. Fun Fact: Peter Thiel quote on processing power ties to why efficient sorting matters. Core Idea: Overhead worth for search ease; from unsorted chaos to ordered utility. Real-World: Dictionaries, exam seats. Expanded: All subtopics point-wise with evidence (e.g., Fig 5.1 swaps), examples (e.g., numList=[8,7,13,1,-9,4]), debates (e.g., Bubble vs Insertion for near-sorted).
- Wider Scope: From intro to complexity; sources: Algorithms (5.1-5.3), figures (5.1-5.3), programs (5-1 to 5-3).
- Expanded Content: Include modern aspects like sorted() built-in vs manual; point-wise for recall; add 2025 relevance like ML data prep.
Introduction to Sorting
- Definition: Arranging collection in order (asc/desc, alpha/length). Ex: Numbers asc, strings z-a.
- Importance: Eases search (e.g., dictionary); unsorted tedious. Overhead justified vs unsorted lookup time.
- Real Examples: Dictionary words, exam roll numbers, student height/weight lists.
- Expanded: Evidence: Intro para; debates: Sorting vs hashing; real: Big data (e.g., 2025 AI datasets).
Conceptual Diagram: Unsorted to Sorted Flow
Flow: Unsorted List → Algorithm Passes (Swaps/Inserts) → Sorted List → Efficient Search. Ties to Fig 5.1-5.3.
Why This Guide Stands Out
Comprehensive: All sorts point-wise, program integrations; 2025 with big-O visuals, processes analyzed for real code.
Bubble Sort
- Overview: n-1 passes; adjacent swaps if unordered; largest "bubbles" to end. Fig 5.1: 4 passes for [8,7,13,1,-9,4].
- Algorithm 5.1: Nested loops (i=0 to n-1, j=0 to n-i-1); swap if list[j]>list[j+1].
- Program 5-1: Python impl; output: -9 1 4 7 8 13.
- Optimization: Stop if no swaps (already sorted).
- Expanded: Evidence: Green sorted in Fig 5.1; Activity 5.1 desc order (reverse >); real: Simple but inefficient for large n.
Selection Sort
- Overview: n-1 passes; select min from unsorted, swap to sorted front. Left: sorted, right: unsorted. Fig 5.2 arrows show mins.
- Algorithm 5.2: For i=0 to n-1; find min index j>i; swap if flag.
- Program 5-2: Flag for swap; output same sorted list.
- Characteristics: Fewer swaps than Bubble; good for swap-costly.
- Expanded: Evidence: Blue min in Fig 5.2; Activity 5.3 partial after 4 passes; debates: Vs Bubble swaps.
Insertion Sort
- Overview: Build sorted prefix; insert unsorted element backward. Like card sorting. Fig 5.3 shifts right.
- Algorithm 5.3: For i=1 to n-1; temp=list[i]; shift j>=0 where >temp; insert at j+1.
- Program 5-3: While j>=0 and temp
- Best For: Nearly sorted; fewer shifts.
- Expanded: Evidence: Swaps in Fig 5.3; Activity 5.4 partial after 3 passes; real: Online data insertion.
Exam Code Studies
Program 5-1 Bubble; 5-2 Selection; 5-3 Insertion; compare outputs.
Time Complexity of Algorithms
- Definition: Time for input size n; measure loops.
- Rules: No loop: O(1); Single: O(n); Nested: O(n²).
- For Sorts: All three have nested loops → O(n²) quadratic.
- Analysis: Varies with order (e.g., Insertion best near-sorted); real-world: For huge data, use advanced (e.g., QuickSort O(n log n)).
- Expanded: Evidence: Nested in programs; debates: Bubble worst-case swaps; 2025: Big-O graphs.
Summary & Exercise
- Key Takeaways: Sorting organizes for efficiency; learn three basics (all O(n²)); complexity guides choice.
- Exercise Tease: Partial passes; swaps comparison; median via sort; percentile calc.
Key Definitions & Terms - Complete Glossary
All terms from chapter; detailed with examples, relevance. Expanded: 30+ terms grouped by subtopic; added advanced like "Pass", "Swap" for depth/easy flashcards.
Sorting
Arranging elements in order. Ex: Asc numbers. Relevance: Eases search.
Bubble Sort
Adjacent swaps in passes. Ex: Largest bubbles up. Relevance: Simple impl.
Selection Sort
Select min, swap front. Ex: Build sorted prefix. Relevance: Fewer swaps.
Insertion Sort
Insert into sorted part. Ex: Shift right for place. Relevance: Near-sorted efficient.
Time Complexity
Time vs input size. Ex: O(n²). Relevance: Efficiency measure.
Pass
One iteration over list. Ex: n-1 passes. Relevance: Algorithm step.
Swap
Exchange positions. Ex: list[j], list[j+1]. Relevance: Reorder.
Unsorted/Sorted List
Right: unsorted; left grows sorted. Ex: Selection. Relevance: Divide strategy.
Min Index
Smallest in unsorted. Ex: Flag in Selection. Relevance: Find target.
Temp Variable
Holds insert value. Ex: Insertion shift. Relevance: Avoid overwrite.
Ascending Order
Increasing sequence. Ex: -9,1,4,7,8,13. Relevance: Common sort.
Descending Order
Decreasing. Ex: Activity 5.1 reverse >. Relevance: Variant.
Nested Loop
Loop in loop. Ex: O(n²). Relevance: Complexity source.
Quadratic Time
O(n²). Ex: All three sorts. Relevance: Inefficient large n.
Overhead
Extra sort time. Ex: Worth vs unsorted search. Relevance: Justification.
Flag
Swap indicator. Ex: Selection min found. Relevance: Optimize.
Shift
Move elements right. Ex: Insertion. Relevance: Make space.
Adjacent Elements
Next to each other. Ex: Bubble compare. Relevance: Local check.
Linear Time
O(n). Ex: Single loop. Relevance: Better but not here.
Constant Time
O(1). Ex: No loop. Relevance: Ideal, rare for sort.
Median
Middle value post-sort. Ex: Exercise 4. Relevance: Stats.
Percentile
Relative position. Ex: Exercise 5 sort + index. Relevance: Ranking.
Partially Sorted
After some passes. Ex: Activity 5.2-5.4. Relevance: Trace steps.
Optimization
Early stop. Ex: No swaps in Bubble. Relevance: Efficiency.
Big-O Notation
Worst-case time. Ex: n². Relevance: Analysis.
Real-World Sorting
Dict, exams. Ex: Alphabetical. Relevance: Application.
Custom Sort
User-defined (e.g., length). Ex: Strings. Relevance: Flexible.
Input Size n
List length. Ex: Complexity scales. Relevance: Growth.
Tip: Group by sort; examples for recall. Depth: Debates (e.g., Insertion adaptive). Historical: Early algos. Interlinks: To Ch4 stacks. Advanced: QuickSort. Real-Life: Database queries. Graphs: Complexity table. Coherent: Evidence → Interpretation. For easy learning: Flashcard per term with code.
60+ Questions & Answers - NCERT Based (Class 12) - From Exercises & Variations
Based on chapter + expansions. Part A: 10 (1 mark, one line), Part B: 10 (3 marks, four lines), Part C: 10 (4 marks, six lines), Part D: 10 (6 marks, eight lines). Answers point-wise in black text. Include code where apt.
Part A: 1 Mark Questions (10 Qs - Short)
1. What is sorting?
Arranging in order.
2. Name one sorting algorithm.
Bubble Sort.
3. Passes in Bubble Sort?
n-1.
4. What bubbles in Bubble Sort?
Largest element.
5. Key in Selection Sort?
Min selection.
6. Insertion Sort like what?
Card placing.
7. Time complexity of sorts?
O(n²).
8. Nested loops mean?
Quadratic time.
9. Overhead in sorting?
Extra time worth it.
10. Best for near-sorted?
Insertion Sort.
Part B: 3 Marks Questions (10 Qs - Medium, Exactly 4 Lines Each)
1. Differentiate Bubble vs Selection.
- Bubble: Adjacent swaps.
- Selection: Min swap front.
- Bubble more swaps.
- Both n-1 passes.
2. Steps in Bubble pass.
- Compare adjacent.
- Swap if > (asc).
- Largest to end.
- Reduce range next.
3. Algorithm 5.1 key.
- i=0 to n-1 passes.
- j=0 to n-i-1 compares.
- Swap if list[j]>j+1.
- Ascending order.
4. Selection flag use.
- Flag=0 init.
- Update if smaller found.
- Swap if flag=1.
- Min index track.
5. Insertion shift.
- Temp = list[i].
- While j>=0 and >temp: shift right.
- Insert temp at j+1.
- Backward search.
6. Complexity rules.
7. Why sort? Ex.
- Fast search.
- Ex: Dictionary alpha.
- Exam roll order.
- Student height list.
8. Bubble optimization.
- Check swaps in pass.
- No swaps: Stop.
- Already sorted early.
- Fig 5.1 5th redundant.
9. Selection passes.
- n-1 passes.
- Each: Find min in unsorted.
- Swap with i.
- nth auto placed.
10. Insertion pass 1.
- Sorted: First elem.
- Unsorted: Rest n-1.
- Compare second with first.
- Shift if smaller.
Part C: 4 Marks Questions (10 Qs - Medium-Long, Exactly 6 Lines Each)
1. Explain Bubble Sort with Fig 5.1.
- Adjacent compares/swaps.
- n-1 passes; largest end.
- Fig 5.1: [8,7,13,1,-9,4] → Pass1:13 end.
- Blue compares, green sorted.
- 4 passes sorted.
- Redundant 5th.
2. Algorithm 5.2 steps.
- i=0 to n-1.
- min=i, flag=0.
- j=i+1 to n-1: if smaller, min=j, flag=1.
- If flag: swap i,min.
- Build sorted left.
- Fig 5.2 mins blue.
3. Insertion vs others.
- Insertion: Insert with shifts.
- Bubble: Many swaps.
- Selection: Min swaps.
- All O(n²) nested.
- Insertion adaptive.
- Fig 5.3 shifts.
4. Program 5-1 code key.
- for i in range(n): passes.
- for j in range(n-i-1): compares.
- if list1[j]>j+1: swap.
- numList example.
- Print sorted.
- Output -9 to 13.
5. Time complexity calc.
- Nested loops: n * (n-1)/2 ~ n².
- All three quadratic.
- Input growth: Slows much.
- Real: Huge data need better.
- Tips: Loop count.
- Ex: n=6, passes reduce.
6. Activity 5.2 Bubble [8,7,6,5,4].
- Pass1: [4,7,6,5,8] wait full trace.
- After Pass1: [7,6,5,4,8].
- Pass2: [6,5,4,7,8].
- Pass3: [5,4,6,7,8].
- Last swap Pass4.
- Sorted [4,5,6,7,8].
7. Why O(n²) bad?
- n=1000: 1M ops.
- Slow for big data.
- Compare linear O(n).
- Real: Use mergesort.
- Chapter basics only.
- Overhead analysis.
8. Desc Bubble mod.
- Change > to < in if.
- Smallest bubbles end.
- Activity 5.1.
- Passes same.
- Ex: [1,2,3] → [3,2,1].
- Reverse logic.
9. Selection partial [7,11,3,...].
10. Insertion partial Array.
- Pass1: [7,11,3,...] → [7,11,3,...].
- Pass2: Insert 3: [3,7,11,10,...].
- Pass3: Insert 10: [3,7,10,11,17,...].
- Activity 5.4.
- Shifts for place.
- Sorted prefix grows.
Part D: 6 Marks Questions (10 Qs - Long, Exactly 8 Lines Each)
1. Trace Bubble [7,11,3,10,17,23,1,4,21,5] 3 passes.
- Pass1: Max 23 end: [7,11,3,10,17,1,4,21,5,23].
- Pass2: Next max 21: [7,11,3,10,17,1,4,5,21,23].
- Pass3: 17 end partial: [7,11,3,10,1,4,5,17,21,23].
- Exercise 1.
- Swaps adjacent.
- Green sorted end.
- Full trace Fig like.
- n=10, 9 passes total.
2. Swaps: List1 [63,42,21,9] Bubble vs Selection.
- Bubble: Pass1 3 swaps → [42,21,9,63]; Pass2 2 → [21,9,42,63]; Pass3 1 → [9,21,42,63]. Total 6.
- Selection: Pass1 min9 swap0: [9,42,21,63]; Pass2 min21 swap1: [9,21,42,63]; Pass3 min42 no. Total 2.
- Selection better swaps.
- Compares: Both ~n².
- Exercise 2.
- Bubble more local.
- Selection global min.
- Choose per cost.
3. Insertion compares: List1 [2,3,5,7,11] vs List2 [11,7,5,3,2].
- List1 sorted: Few compares (each insert 1-2).
- Total ~5-10.
- List2 reverse: Many shifts/compares (e.g., 2 insert: 4 compares).
- Total ~20.
- List1 min compares.
- Diagram: List1 shifts minimal.
- Exercise 3.
- Adaptive nature.
4. Median program with Bubble.
- Def median(lst): bubble_sort(lst).
- n=len(lst); if n%2: return lst[n//2].
- Else: (lst[n//2-1] + lst[n//2])/2.
- Ex: [1,3,2] → sort [1,2,3] → 2.
- Code below.
- Exercise 4.
- User func.
- Odd/even handle.
def bubble_sort(lst): ... # From 5-1
def median(lst):
bubble_sort(lst)
n = len(lst)
if n % 2 == 1:
return lst[n//2]
else:
return (lst[n//2 - 1] + lst[n//2]) / 25. Percentile program Selection.
- Def percentile(marks, x): selection_sort(marks).
- import math; index = math.round(x/100 * len(marks)).
- Return marks[index-1] (0-index).
- Steps: Sort asc, calc index, display.
- Ex: 90th for 120: index=108.
- Exercise 5.
- Relative performance.
- XYZ school apt.
6. Ascending names insert program.
- Def insert_name(names, new): Insertion logic for strings.
- Find pos backward where >new.
- Shift right, insert.
- Global list append each call.
- Exercise 6.
- Online insertion.
- Alpha order.
- Admission use.
names = []
def add_name(new):
i = len(names)
while i > 0 and names[i-1] > new:
names[i] = names[i-1]
i -= 1
names[i] = new7. Compare three sorts swaps/complexity.
- All O(n²) nested.
- Bubble: Many swaps worst.
- Selection: Min swaps.
- Insertion: Shifts, adaptive.
- Ex: Reverse list Bubble bad.
- Near-sorted Insertion best.
- Choose per data.
- Figs 5.1-5.3 evidence.
8. Trace Selection [63,42,21,9].
- Pass1: Min9 swap0: [9,42,21,63].
- Pass2: Min21 swap1: [9,21,42,63].
- Pass3: Min42 no swap: [9,21,42,63].
- 2 swaps total.
- Blue mins Fig style.
- Sorted left grows.
- Unsorted right shrinks.
- nth placed.
9. Why complexity important?
- Predict performance.
- n large: n² explodes.
- Compare algos.
- Ex: n=1000 Bubble slow.
- Real apps: Choose fit.
- Chapter: All quadratic.
- Tips: Count operations.
- Ch XI prime link.
10. Custom sort length strings.
- Modify compare by len(str).
- Bubble: if len(s[j])>len(s[j+1]).
- Ex: ["a","bb","c"] → ["a","c","bb"].
- Intro strings mention.
- Flexible orders.
- Python sorted(key=len).
- But manual here.
- App: File names.
Tip: Include traces/code; practice variations. Additional 30 Qs: More partials, mods.
Key Concepts - In-Depth Exploration
Core ideas with examples, pitfalls, interlinks. Expanded: All concepts with steps/examples/pitfalls for easy learning. Depth: Debates, analysis.
Sorting Importance
Steps: 1. Unsorted → Passes → Ordered. Ex: Dict search. Pitfall: Overhead ignore. Interlink: Search ease. Depth: Utility.
Bubble Sort
Steps: 1. Adjacent compare, 2. Swap up, 3. Reduce end. Ex: Fig 5.1. Pitfall: Many swaps reverse. Interlink: Simple. Depth: Bubbles max.
Selection Sort
Steps: 1. Find min, 2. Swap front, 3. Unsorted shrink. Ex: Fig 5.2. Pitfall: Full scan each. Interlink: Swaps min. Depth: Global select.
Insertion Sort
Steps: 1. Take next, 2. Backward shift >, 3. Insert. Ex: Fig 5.3. Pitfall: Reverse worst. Interlink: Adaptive. Depth: Local insert.
Time Complexity
Steps: 1. Count loops, 2. O(f(n)). Ex: Nested n². Pitfall: Ignore input. Interlink: Analysis. Depth: Growth rate.
Passes
Steps: 1. Full traversal, 2. Reduce range. Ex: n-1. Pitfall: Redundant. Interlink: Optimization. Depth: Iteration.
Swaps/Shifts
Steps: 1. Exchange/ move, 2. Position correct. Ex: Bubble swap. Pitfall: Costly ops. Interlink: Efficiency. Depth: Operation type.
Asc/Desc Order
Steps: 1. > for desc, 2. < asc. Ex: Modify if. Pitfall: Wrong logic. Interlink: Variants. Depth: Direction.
Nested Loops
Steps: 1. Outer passes, 2. Inner compares. Ex: O(n²). Pitfall: Inefficient large. Interlink: Complexity. Depth: Quadratic.
Optimization
Steps: 1. Check swaps, 2. Early stop. Ex: Bubble no swap. Pitfall: Miss impl. Interlink: Adaptive. Depth: Improve.
Partially Sorted
Steps: 1. After k passes, 2. Prefix sorted. Ex: Activities. Pitfall: Trace error. Interlink: Trace. Depth: Intermediate.
Real-World Apps
Steps: 1. Sort data, 2. Query fast. Ex: Exams. Pitfall: Wrong type. Interlink: Ch6 files. Depth: Practical.
Adaptive Sorting
Steps: 1. Fewer ops sorted input. Ex: Insertion. Pitfall: Assume random. Interlink: Complexity vary. Depth: Input dep.
Big-O
Steps: 1. Worst case, 2. Asymp. Ex: n². Pitfall: Avg ignore. Interlink: Analysis. Depth: Math bound.
Overhead Justification
Steps: 1. Sort once, 2. Search many. Ex: Dict. Pitfall: Small data. Interlink: Intro. Depth: Trade-off.
Advanced: Stable sort, inversions. Pitfalls: Off-by-one loops. Interlinks: To tuples Ch3. Real: E-commerce sort. Depth: 12 concepts details. Examples: Real traces. Graphs: Pass tables. Errors: Wrong range. Tips: Steps evidence; compare tables (swaps Bubble vs Selection).
Code Examples & Programs - From Text with Simple Explanations
Expanded with evidence, analysis; focus on applications. Added variations for practice.
Example 1: Bubble Sort (Program 5-1)
Simple Explanation: Nested loops swap adjacent.
def bubble_Sort(list1):
n = len(list1)
for i in range(n):
for j in range(0, n-i-1):
if list1[j] > list1[j+1]:
list1[j], list1[j+1] = list1[j+1], list1[j]
numList = [8, 7, 13, 1, -9, 4]
bubble_Sort(numList)
print("The sorted list is :")
for i in range(len(numList)):
print(numList[i], end=" ")- Step 1: Passes outer i.
- Step 2: Inner j compares/swaps.
- Step 3: Output: -9 1 4 7 8 13.
- Simple Way: Asc order.
Example 2: Selection Sort (Program 5-2)
Simple Explanation: Find min, swap front.
def selection_Sort(list2):
n = len(list2)
for i in range(n):
min = i
flag = 0
for j in range(i + 1, len(list2)):
if list2[j] < list2[min]:
min = j
flag = 1
if flag == 1:
list2[min], list2[i] = list2[i], list2[min]
numList = [8, 7, 13, 1, -9, 4]
selection_Sort(numList)
# Print same as above- Step 1: Outer i position.
- Step 2: Inner find min.
- Step 3: Swap if flag.
- Simple Way: Fewer swaps.
Example 3: Insertion Sort (Program 5-3)
Simple Explanation: Shift and insert.
def insertion_Sort(list3):
n = len(list3)
for i in range(1, n):
temp = list3[i]
j = i-1
while j >= 0 and temp < list3[j]:
list3[j+1] = list3[j]
j = j-1
list3[j+1] = temp
numList = [8, 7, 13, 1, -9, 4]
insertion_Sort(numList)
# Print same- Step 1: i from 1, temp hold.
- Step 2: While shift larger.
- Step 3: Insert temp.
- Simple Way: Like cards.
Example 4: Optimization Bubble (Variation)
Simple Explanation: Early stop.
def optimized_bubble(lst):
n = len(lst)
for i in range(n):
swapped = False
for j in range(0, n-i-1):
if lst[j] > lst[j+1]:
lst[j], lst[j+1] = lst[j+1], lst[j]
swapped = True
if not swapped:
break- Step 1: Flag swapped.
- Step 2: Break if no.
- Step 3: Faster sorted input.
- Simple Way: Avoid redundant.
Example 5: Median via Sort (Exercise 4)
Simple Explanation: Sort then middle.
# Use bubble_Sort
def find_median(nums):
bubble_Sort(nums)
n = len(nums)
if n % 2 == 1:
return nums[n//2]
else:
return (nums[n//2 - 1] + nums[n//2]) / 2
print(find_median([3,1,4,1,5])) # 3.0 or int- Step 1: Sort nums.
- Step 2: Odd/even mid.
- Step 3: Return avg/center.
- Simple Way: Stats tool.
Tip: Run traces; vary desc. Added for exercises, optimizations.
Interactive Quiz - Master Sorting Algorithms
10 MCQs in full sentences; 80%+ goal. Covers sorts, complexity.
Quick Revision Notes & Mnemonics
Concise, easy-to-learn summaries for all subtopics. Structured in tables for quick scan: Key points, examples, mnemonics. Covers intro, sorts, complexity. Bold key terms; short phrases for fast reading.
| Subtopic | Key Points | Examples | Mnemonics/Tips |
|---|---|---|---|
| Intro |
|
Alpha words; height list. | SO (Sort-Order). Tip: "Sort Once, Search Often" – Efficiency. |
| Bubble Sort |
|
Program 5-1; [8,7..] → -9..13. | BAP (Bubble-Adjacent-Pass). Tip: "Bubbles Rise" – Largest end. |
| Selection Sort |
|
Program 5-2; Blue mins. | SMF (Select-Min-Flag). Tip: "Select Smallest First" – Prefix grow. |
| Insertion Sort |
|
Program 5-3; Card like. | IST (Insert-Shift-Temp). Tip: "Insert in Place" – Shifts right. |
| Complexity |
|
n=6 ~36 ops. | ONR (O-nested-Rules). Tip: "Nested = Nightmare" – Slow large n. |
| Activities |
|
5.2 last swap Pass4. | PTS (Partial-Trace-Swaps). Tip: "Pass by Pass" – Visualize Figs. |
Overall Tip: Use SO-BAP-SMF-IST-ONR for full scan (5 mins). Flashcards: Front (term), Back (points + mnemonic). Print table for wall revision. Covers 100% chapter – easy for exams!
Key Terms & Processes - All Key
Expanded table 30+ rows; quick ref. Added advanced (e.g., Adaptive, Stable).
| Term/Process | Description | Example | Usage |
|---|---|---|---|
| Sorting | Arrange order | Asc numbers | Search ease |
| Bubble Sort | Adjacent swaps | Alg 5.1 | Simple |
| Selection Sort | Min swap front | Alg 5.2 | Few swaps |
| Insertion Sort | Shift insert | Alg 5.3 | Adaptive |
| Time Complexity | Time vs n | O(n²) | Efficiency |
| Pass | One iteration | n-1 | Step |
| Swap | Exchange pos | list[j],j+1 | Reorder |
| Unsorted List | Right part | Initial all | Target |
| Sorted List | Left grows | Green Fig | Result |
| Min Index | Smallest pos | Flag update | Select |
| Temp Var | Hold value | Insertion | Shift |
| Ascending | Increasing | -9 to 13 | Common |
| Descending | Decreasing | Reverse if | Variant |
| Nested Loop | Loop in loop | O(n²) | Quadratic |
| Quadratic Time | n² growth | All sorts | Slow large |
| Overhead | Extra time | Sort cost | Justified |
| Flag | Indicator | Swap yes | Optimize |
| Shift | Move right | Insertion | Space |
| Adjacent | Next elems | Bubble | Local |
| Linear Time | O(n) | Single loop | Better |
| Constant Time | O(1) | No loop | Rare |
| Median | Middle post-sort | Exercise 4 | Stats |
| Percentile | Position % | Exercise 5 | Ranking |
| Partially Sorted | After passes | Activities | Trace |
| Optimization | Early stop | No swaps | Fast |
| Big-O | Worst time | n² | Analysis |
| Adaptive | Input dep | Insertion | Near-sorted |
| Stable Sort | Equal order preserve | Insertion yes | Advanced |
| Inversions | Out-order pairs | Reverse many | Measure |
| Online Sorting | Insert one-by-one | Exercise 6 | Dynamic |
| Custom Key | Non-num order | String len | Flexible |
| Input Size n | List len | Complexity | Growth |
| Redundant Pass | No change | Fig 5.1 pass5 | Opt target |
Tip: Examples memory; sort subtopic. Easy: Table scan. Added 10 rows depth.
Sorting Processes Step-by-Step
Step-by-step breakdowns of core processes, structured as full questions followed by detailed answers with steps. Visual descriptions for easy understanding; focus on actionable Q&A with examples from chapter.
Question 1: How does Bubble Sort process Pass 1 for [8,7,13,1,-9,4] (Fig 5.1)?
- Step 1: j=0: 8>7 swap → [7,8,13,1,-9,4].
- Step 2: j=1: 8<13 no.
- Step 3: j=2: 13>1 swap → [7,8,1,13,-9,4].
- Step 4: j=3: 13>-9 swap → [7,8,1,-9,13,4].
- Step 5: j=4: 13>4 swap → [7,8,1,-9,4,13].
- Step 6: Largest 13 end (green).
Visual: Blue pairs → Swap arrows → 13 bubbles right. Example: 4 swaps Pass1.
Question 2: What steps in Selection Sort Pass 1 for same list (Fig 5.2)?
- Step 1: i=0, min=0 (8).
- Step 2: j=1:7<8 min=1.
- Step 3: j=2:13>7 no.
- Step 4: j=3:1<7 min=3.
- Step 5: j=4:-9<1 min=4.
- Step 6: j=5:4>-9 no; swap 0 and 4: [-9,7,13,1,8,4].
Visual: Arrows compare → Blue min -9 → Swap to front. Example: 1 swap, full scan.
Question 3: Trace Insertion Sort Pass 2 for [7,8,13,1,-9,4] (Fig 5.3)?
- Step 1: i=2, temp=13 (sorted [7,8]).
- Step 2: j=1:8<13 no shift.
- Step 3: Insert at j+1=2: No change [7,8,13,1,-9,4].
- Step 4: But full: Later passes insert 1 etc.
- Step 5: For 1 (i=3): Shifts all >1 right.
- Step 6: [7,8,1,13,-9,4] → shifts to [1,7,8,13,-9,4].
Visual: Backward arrow from i → Shift blocks → Insert spot. Example: Multi swaps for small.
Question 4: How does time complexity arise in nested loops (Bubble)?
- Step 1: Outer i: n passes.
- Step 2: Inner j: ~n-i compares each.
- Step 3: Total ~ n(n-1)/2 = O(n²).
- Step 4: Swaps up to n²/2 worst.
- Step 5: Scales bad large n.
- Step 6: All sorts similar.
Visual: Outer circle passes → Inner shrinking loops. Example: n=6: 15 compares.
Question 5: Steps for median calc via sort (Exercise 4)?
- Step 1: Input list, bubble_sort.
- Step 2: n=len; if odd: mid = n//2.
- Step 3: Even: avg (n//2-1, n//2).
- Step 4: Return value.
- Step 5: Ex: [1,3] → 2.0.
- Step 6: Handles odd/even.
Visual: List → Sort arrow → Mid pick. Example: Stats post-sort.
Question 6: Process for percentile with Selection (Exercise 5)?
- Step 1: selection_sort(marks).
- Step 2: index = round(x/100 * n).
- Step 3: Value at index (1-based adjust).
- Step 4: Display.
- Step 5: Ex: 90th n=120: index=108.
- Step 6: Relative rank.
Visual: Sort → % calc → Index point. Example: Aptitude test.
Tip: Treat as FAQ; apply to Figs. Easy: Q → Steps + Visual. Full Q&A for exam-like practice.
