Bubble Sort Lecture Notes

Introduction to Sorting

• Sorting is the process of arranging data in ascending or descending order.
• Different sorting techniques include:
  • Bubble Sort
  • Insertion Sort
  • Selection Sort
  • Quick Sort
  • Merge Sort
  • Heap Sort

Bubble Sort Overview

• Basic Principle:
  • Compare adjacent elements in an array.
  • Swap them if they are in the wrong order (ascending or descending).
• Goal: Arrange data in ascending order by default.

Example: Sorting the Array [15, 16, 6, 8, 5]

1. Initial Array: 15, 16, 6, 8, 5

2. Pass 1:

   • Compare 15 and 16: No swap (15 < 16)
   • Compare 16 and 6: Swap -> Array: 15, 6, 16, 8, 5
   • Compare 16 and 8: Swap -> Array: 15, 6, 8, 16, 5
   • Compare 16 and 5: Swap -> Array: 15, 6, 8, 5, 16
   • Result after Pass 1: Largest (16) bubbled up.

3. Pass 2:

   • Start with Array: 15, 6, 8, 5, 16
   • Compare and swap accordingly:
     • 15 and 6: Swap -> Array: 6, 15, 8, 5, 16
     • 15 and 8: Swap -> Array: 6, 8, 15, 5, 16
     • 15 and 5: Swap -> Array: 6, 8, 5, 15, 16
   • Result after Pass 2: 15 and 16 are in correct order.

4. Subsequent Passes:

   • Pass 3: Sorts three remaining elements.
   • Pass 4: Sorts the last two elements.
   • Final Sorted Array: 5, 6, 8, 15, 16 after 4 passes.

Pass and Comparison Counts

• General Rule: If n elements, then maximum passes = n - 1.
• Comparisons decrease as the largest elements are positioned correctly.

Pseudocode for Bubble Sort

1. Initialize outer loop for passes (0 to n-1).
2. Initialize inner loop for comparisons (0 to n-1-i).
3. Compare and swap elements accordingly:

   if a[j] > a[j+1]
       // Swap logic using a temporary variable.
   

Optimizing Bubble Sort

• Avoid Unnecessary Comparisons: Reduce comparisons based on the number of passes completed.
• Flag Variable: Introduce a flag to indicate if any swaps occurred during a pass. If no swaps, break the loop early, indicating the array is sorted.

Time Complexity Analysis

• Best Case: O(n) when array is already sorted. Only one pass required.
• Worst Case: O(n^2) when array is sorted in reverse order.

Conclusion

• Bubble Sort is simple but inefficient for large datasets.
• Further study on other sorting algorithms like Insertion Sort will be discussed in the next session.