Introduction

Bubble Sort Technique: Bubble Sort is a simple sorting algorithm that repeatedly steps through a list, compares adjacent elements, and swaps them if they are in the wrong order.
The process continues until the list is sorted. The algorithm gets its name from the way smaller elements "bubble up" to their correct positions.

How can we sort an array?

• In Bubble Sort, we take the simplest possible approach to sort an array.
• We look through the array in an orderly fashion, comparing only adjacent elements at a time.
• Whenever we see two elements that are out of order, we swap them so that the smaller element comes before the greater element.
• We keep performing the above steps over the array again and again until we achieve the sorted form.

Important Observations

• In the first pass, the largest element will be at the end of the array.
• In the second pass, the second largest element will be at the second last position.
• In the third pass, the third largest element will be at the third last position.
• And so on...
• In the last pass, the smallest element will be at the first position.
• Thus, the array will be sorted in ascending order.

Key Characteristics:

• Iterative and comparison-based sorting technique.
• In-place sorting; no additional space required.
• Stable algorithm (preserves order of equal elements).
• Best for small or nearly sorted datasets.

Advantages:

• Simple to understand and implement.
• Does not require additional memory space.
• Good for small datasets or nearly sorted data.

Disadvantages:

• Not efficient for large datasets.
• Time complexity is (O(n^2)) in the average and worst cases.
• Not suitable for large datasets compared to more advanced algorithms like Quick Sort or Merge Sort.

Time Complexity:

• Best Case: (O(n)) (already sorted list).
• Average Case: (O(n^2)).
• Worst Case: (O(n^2)).