📝 Bubble Sort Algorithm Report

I. Project Introduction

1.1 Overview

This report analyzes the Bubble Sort algorithm, one of the simplest comparison-based sorting methods.
The algorithm repeatedly compares and swaps adjacent elements until the list is sorted. While Bubble Sort is not efficient for large datasets, it remains a fundamental algorithm for learning the basics of sorting and algorithm analysis.

1.2 Problem & Solution

The project focuses on:

• Determining the time complexity of Bubble Sort across best, average, and worst cases.
• Analyzing the space complexity and stability of the algorithm.
• Highlighting performance limitations compared to other sorting techniques.
• Supporting the analysis with theoretical derivations, formula breakdowns, and example implementations in Java (screenshots only).

1.3 Justification

Bubble Sort is chosen as a subject of analysis because:

• It is simple and easy to implement.
• It demonstrates core algorithmic concepts like comparisons, swaps, and pass-based iteration.
• It provides a foundation for comparing more advanced sorting algorithms.

---

II. Theoretical Analysis

2.1 Number of Comparisons

• Comparisons are constant across input arrangements → always O(n²).
• For average case analysis, the sum of positional differences gives approximately n²/2 swaps.

2.2 Time Complexity

• Worst Case: O(n²) → list is in reverse order.
• Average Case: O(n²) → depends on swaps but comparisons remain quadratic.
• Best Case: O(n) → when the list is already sorted, requiring only one pass.

2.3 Space Complexity

• Bubble Sort is in-place, requiring no extra memory proportional to input size.
• Space complexity = O(1).

2.4 Stability

• Bubble Sort is stable → equal elements retain their relative order.

2.5 Performance Notes

• Not suitable for large datasets due to high time complexity.
• Useful for small lists or nearly sorted lists.

---

III. Implementation (Illustrated in Report)

• The algorithm was demonstrated in Java (with output screenshots included in the report).
• No separate code files are provided — the implementation serves as supporting evidence for the theoretical analysis.

---

IV. Results & Output

• Step-by-step execution confirms the iterative swap mechanism.
• The sample outputs validate the time complexity findings.
• Visual traces (included in the report) help understand pass-by-pass behavior.

---

V. Conclusion

Bubble Sort is:

• Simple and intuitive, making it ideal for educational purposes.
• Inefficient for large datasets, where more advanced algorithms (Merge Sort, Quick Sort, Heap Sort) should be used.
• Still valuable as a foundation algorithm for learning sorting concepts and algorithmic analysis.

Understanding sorting algorithms is a key step for programmers and data scientists. Bubble Sort highlights the trade-off between simplicity and efficiency.

---

VI. References

1. Programiz: Bubble Sort
2. Searching and Sorting (AISSMS)
3. GeeksforGeeks: Bubble Sort
4. IEEE Xplore Reference
5. Analysis of Algorithms: An Active Learning Approach, Jeffrey J. McConnell
6. GeeksforGeeks Output Examples

---

VII. Appendix

The report includes a comparison of Bubble Sort with other sorting algorithms in terms of:

• Time complexity
• Space complexity
• Suitability for different input sizes

Each algorithm has trade-offs, and the choice depends on the problem requirements.

---

VIII. Team Members

• Layan AlRushaid
• Jana Alrasheed
• Rana Alhazzaa
• Nada alghulaygah
• Ghaida AlZahrani