Standard Algorithm & Logic Patterns: Bubble Sort Algorithm Explained Step By Step (Copy)

Bubble Sort Algorithm Explained Step By Step

What Bubble Sort Does

• Bubble sort is a sorting algorithm that:
  • Repeatedly compares adjacent elements
  • Swaps them if they are in the wrong order
  • After each full pass, the largest unsorted value “bubbles” to the end
• Works for:
  • Integers, reals, strings (lexicographic), characters (if rules provided)
• Used in exam questions because:
  • Easy to trace
  • Clear loop structure
  • Clear swap logic

---

When Bubble Sort Is Appropriate

• Use bubble sort when:
  • Dataset is small
  • You need a simple, traceable sorting method
  • The question explicitly asks for bubble sort
• Avoid using bubble sort when:
  • Dataset is large (too many comparisons)
  • Another algorithm is requested

---

Core Concepts You Must Know Before Writing Bubble Sort

Key Terms

• Pass: one full traversal through the unsorted section of the array
• Comparison: checking adjacent values arr[j] and arr[j + 1]
• Swap: exchanging values using a temporary variable
• Sorted section: the part of the array that is already in final position (usually at the end)

Why A Swap Needs A Temporary Variable

• You cannot do:
  • arr[j] ← arr[j+1] and then arr[j+1] ← arr[j] (because arr[j] is overwritten)
• Correct swap method:
  • Use temp

---

Swap Pattern (Copy-Paste Safe)

temp ← arr[j]
arr[j] ← arr[j + 1]
arr[j + 1] ← temp

---

Bubble Sort Step-By-Step Logic (Ascending Order)

Step 1: Decide Bounds

• Array: arr[1..n]
• Each pass pushes the largest unsorted item to the end
• That means after pass 1:
  • Last item is correct
• After pass 2:
  • Last two items are correct
• So inner loop range shrinks each pass

---

Step 2: Outer Loop Controls Number Of Passes

• Maximum required passes:
  • n - 1
• Outer loop often written:
  • FOR pass ← 1 TO n - 1

---

Step 3: Inner Loop Compares Adjacent Items

• Compare:
  • arr[j] and arr[j + 1]
• Swap if:
  • arr[j] > arr[j + 1] (for ascending order)

---

Bubble Sort Standard Pseudocode (Ascending, Exam-Favourite)

FOR pass ← 1 TO n - 1
  FOR j ← 1 TO n - pass
    IF arr[j] > arr[j + 1] THEN
      temp ← arr[j]
      arr[j] ← arr[j + 1]
      arr[j + 1] ← temp
    ENDIF
  NEXT j
NEXT pass

---

Written and Compiled By Sir Hunain Zia (AYLOTI), World Record Holder With 154 Total A Grades, 7 Distinctions and 11 World Records For Educate A Change AS Level Computer Science Full Scale Course

Why The Inner Loop Stops At n - pass

• Because the biggest values move to the end after each pass
• So the end part becomes sorted and untouched
• Inner loop comparison uses j + 1
  • So j must never reach n
• If you mistakenly loop j ← 1 TO n, you will attempt arr[n + 1] (out of range)

---

Bubble Sort Trace Example (Ascending) With Full Passes

Initial Array

• arr = [5, 1, 4, 2, 8]
• n = 5

Pass 1 (j from 1 to 4)

• Compare and swap adjacent pairs

Comparison	Pair	Action	Array After
j=1	(5,1)	swap	[1, 5, 4, 2, 8]
j=2	(5,4)	swap	[1, 4, 5, 2, 8]
j=3	(5,2)	swap	[1, 4, 2, 5, 8]
j=4	(5,8)	no swap	[1, 4, 2, 5, 8]

• End of pass 1:
  • Largest value 8 is correctly at the end

Pass 2 (j from 1 to 3)

Comparison	Pair	Action	Array After
j=1	(1,4)	no swap	[1, 4, 2, 5, 8]
j=2	(4,2)	swap	[1, 2, 4, 5, 8]
j=3	(4,5)	no swap	[1, 2, 4, 5, 8]

Pass 3 (j from 1 to 2)

Comparison	Pair	Action	Array After
j=1	(1,2)	no swap	[1, 2, 4, 5, 8]
j=2	(2,4)	no swap	[1, 2, 4, 5, 8]

Pass 4 (j from 1 to 1)

Comparison	Pair	Action	Array After
j=1	(1,2)	no swap	[1, 2, 4, 5, 8]

• Final sorted array:
  • [1, 2, 4, 5, 8]

---

Bubble Sort In Descending Order

• Only change the comparison condition

Descending Pseudocode

FOR pass ← 1 TO n - 1
  FOR j ← 1 TO n - pass
    IF arr[j] < arr[j + 1] THEN
      temp ← arr[j]
      arr[j] ← arr[j + 1]
      arr[j + 1] ← temp
    ENDIF
  NEXT j
NEXT pass

---

Written and Compiled By Sir Hunain Zia (AYLOTI), World Record Holder With 154 Total A Grades, 7 Distinctions and 11 World Records For Educate A Change AS Level Computer Science Full Scale Course

Efficiency Improvement Without Big-O Notation (Early Stopping)

• If a full pass makes no swaps, the list is already sorted
• Add a Boolean flag:
  • swapped

Optimised Bubble Sort Pseudocode (Ascending)

pass ← 1
swapped ← TRUE

WHILE pass <= n - 1 AND swapped = TRUE DO
  swapped ← FALSE

  FOR j ← 1 TO n - pass
    IF arr[j] > arr[j + 1] THEN
      temp ← arr[j]
      arr[j] ← arr[j + 1]
      arr[j + 1] ← temp
      swapped ← TRUE
    ENDIF
  NEXT j

  pass ← pass + 1
ENDWHILE

What This Improves

• If the array becomes sorted early:
  • The algorithm stops instead of doing extra passes

---

Bubble Sort “Pass Summary” Table (Quick Revision)

Part	Purpose	Key Risk
Outer loop (pass)	Controls number of passes	wrong pass count (n instead of n-1)
Inner loop (j)	Compares adjacent elements	out-of-range (j+1)
IF condition	Determines swap	wrong sign for ascending/descending
temp variable	Enables swap safely	forgetting temp destroys values
swapped flag (optional)	early termination	forgetting to reset swapped each pass

---

Most Common Exam Pitfalls (And How To Fix Them)

Pitfall 1: Out-Of-Range Access

• Wrong:

FOR j ← 1 TO n
  IF arr[j] > arr[j+1] THEN

• Why wrong:
  • When j = n, arr[j+1] becomes arr[n+1]
• Correct:

FOR j ← 1 TO n - pass

(or at least FOR j ← 1 TO n - 1 for the unshrunk version)

---

Pitfall 2: Forgetting temp

• Wrong:

arr[j] ← arr[j+1]
arr[j+1] ← arr[j]

• Correct swap:

temp ← arr[j]
arr[j] ← arr[j+1]
arr[j+1] ← temp

---

Pitfall 3: Wrong Comparison Sign

• Ascending should swap when:
  • arr[j] > arr[j+1]
• Descending should swap when:
  • arr[j] < arr[j+1]

---

Pitfall 4: Swapped Flag Not Reset

• Wrong:
  • swapped never set to FALSE at start of each pass
• Correct:
  • swapped ← FALSE at the beginning of each pass

---

Written and Compiled By Sir Hunain Zia (AYLOTI), World Record Holder With 154 Total A Grades, 7 Distinctions and 11 World Records For Educate A Change AS Level Computer Science Full Scale Course

How To Write Bubble Sort In An Exam (Mark-Winning Structure)

Examiner-Friendly Layout

• Declare variables clearly
• Use correct loop bounds
• Keep swap code clean
• Do not add unnecessary features unless asked

“Full Marks” Minimal Bubble Sort Answer (Ascending)

FOR pass ← 1 TO n - 1
  FOR j ← 1 TO n - pass
    IF arr[j] > arr[j + 1] THEN
      temp ← arr[j]
      arr[j] ← arr[j + 1]
      arr[j + 1] ← temp
    ENDIF
  NEXT j
NEXT pass

---

Dry-Run / Trace Table Technique For Bubble Sort Questions

What To Track

• Current pass number
• Each comparison (which two values)
• Whether swap happens
• Array after swap

Quick Trace Table Template (Exam-Ready)

pass	j	arr[j]	arr[j+1]	swap?	array after

---

Bubble Sort Variations Examiners Might Ask

Variation 1: Sort Only Part Of Array

• Example: sort first k items
• Inner loop becomes:
  • FOR j ← 1 TO k - pass

Variation 2: Sort Strings Alphabetically

• Use same structure
• Comparison becomes:
  • IF names[j] > names[j+1] THEN
    (lexicographic comparison assumed as given)

Variation 3: Sort In Descending

• Swap condition changes only

---

Bubble Sort “Spot The Bug” Mini Practice

Bug 1 (Out Of Range)

FOR pass ← 1 TO n - 1
  FOR j ← 1 TO n
    IF arr[j] > arr[j + 1] THEN
      ...
    ENDIF
  NEXT j
NEXT pass

• Fix:
  • FOR j ← 1 TO n - pass

---

Bug 2 (Swap Wrong)

temp ← arr[j+1]
arr[j+1] ← arr[j]
arr[j] ← temp

• This is actually fine (swap still works) but must be consistent
• Safer standard:

temp ← arr[j]
arr[j] ← arr[j+1]
arr[j+1] ← temp

---

Bug 3 (Descending Confusion)

IF arr[j] > arr[j+1] THEN

• If question asks descending, fix to:
  • IF arr[j] < arr[j+1] THEN

---

Written and Compiled By Sir Hunain Zia (AYLOTI), World Record Holder With 154 Total A Grades, 7 Distinctions and 11 World Records For Educate A Change AS Level Computer Science Full Scale Course

Copy-Paste Bubble Sort Toolkit (Fast Revision)

Ascending Bubble Sort (Shrinking Inner Loop)

FOR pass ← 1 TO n - 1
  FOR j ← 1 TO n - pass
    IF arr[j] > arr[j + 1] THEN
      temp ← arr[j]
      arr[j] ← arr[j + 1]
      arr[j + 1] ← temp
    ENDIF
  NEXT j
NEXT pass

Descending Bubble Sort (Shrinking Inner Loop)

FOR pass ← 1 TO n - 1
  FOR j ← 1 TO n - pass
    IF arr[j] < arr[j + 1] THEN
      temp ← arr[j]
      arr[j] ← arr[j + 1]
      arr[j + 1] ← temp
    ENDIF
  NEXT j
NEXT pass

Optimised Bubble Sort With Early Stop (Ascending)

pass ← 1
swapped ← TRUE

WHILE pass <= n - 1 AND swapped = TRUE DO
  swapped ← FALSE
  FOR j ← 1 TO n - pass
    IF arr[j] > arr[j + 1] THEN
      temp ← arr[j]
      arr[j] ← arr[j + 1]
      arr[j + 1] ← temp
      swapped ← TRUE
    ENDIF
  NEXT j
  pass ← pass + 1
ENDWHILE