Bubble Sort

Implement a program that sorts the given array elements using Bubble Sort algorithm.

Bubble Sort is a simple sorting algorithm that works by repeatedly swapping adjacent elements if they are in the wrong order until the list is sorted. The theory behind bubble sort can be summarized in the following steps:

- Compare adjacent elements: Bubble sort compares adjacent elements in a list and swaps them if they are in the wrong order. The first pass of the algorithm compares the first and second elements, the second pass compares the second and third elements, and so on.
- Repeat until sorted: Bubble Sort continues to repeat this process until the list is completely sorted. In each pass, the largest unsorted element will "Bubble up" to its correct position at the end of the list.
- Optimization: Bubble Sort can be optimized by adding a flag to check if any swaps were made in a pass. If no swaps were made, the list is already sorted and the algorithm can terminate early.
- Time complexity: The time complexity of bubble sort is O(n^2) in the worst and average case, where n is the number of elements in the list. This makes bubble sort inefficient for large lists, but it can be useful for small lists or as a teaching tool for introductory sorting algorithms.

Consider the following unsorted list: 5, 2, 9, 1, 5, 6

Now, walk through the steps of the bubble sort algorithm:

- First pass:
- Compare 5 and 2. Swap them because 5 > 2.
- Compare 5 and 9. No swap needed because 5 < 9.
- Compare 9 and 1. Swap them because 9 > 1.
- Compare 9 and 5. Swap them because 9 > 5.
- Compare 9 and 6. Swap them because 9 > 6.

After the first pass: 2, 5, 1, 5, 6, 9

- Second pass:
- Compare 2 and 5. No swap needed because 2 < 5.
- Compare 5 and 1. Swap them because 5 > 1.
- Compare 5 and 5. No swap needed because they are equal.
- Compare 5 and 6. No swap needed because 5 < 6.

After the second pass: 2, 1, 5, 5, 6, 9

- Third pass:
- Compare 2 and 1. Swap them because 2 > 1.
- Compare 2 and 5. No swap needed because 2 < 5.
- Compare 5 and 5. No swap needed.

After the third pass: 1, 2, 5, 5, 6, 9

- Fourth pass:
- Compare 1 and 2. No swap needed.
- Compare 2 and 5. No swap needed.
- Compare 5 and 5. No swap needed.

After the fourth pass: 1, 2, 5, 5, 6, 9

Now, the list is sorted, and the algorithm will terminate.

The minimum number of passes required to sort a list of n elements using the bubble sort algorithm is n−1. Bubble sort sorts the elements in-place, meaning that it doesn't require additional memory space for temporary storage. Bubble sort is a stable sorting algorithm. Stability in sorting means that equal elements (in the above example number 5) maintain their relative order in the sorted output as they appeared in the original input.

- Understanding the concept of sorting: Bubble Sort helps learners understand the basic concept of sorting, which is arranging data in a particular order.
- Improved problem-solving skills: Bubble Sort helps learners develop better problem-solving skills, as they need to understand how to compare and swap elements to sort data.
- Improved algorithmic thinking: Bubble Sort helps learners develop their algorithmic thinking, as they need to come up with a set of steps to sort data effectively.
- Enhanced understanding of complexity: Bubble Sort helps learners understand the complexity of sorting algorithms, as they need to analyze the number of comparisons and swaps required to sort data.
- Understanding of optimization techniques: Bubble Sort can be optimized by using various techniques, such as stopping the algorithm early if the list is already sorted. This helps learners understand the concept of optimization and how to apply it to algorithms.
- Improved coding skills: Implementing Bubble Sort in code helps learners improve their coding skills, as they need to understand how to write a working algorithm in a programming language.