Bubble Sort

Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.

• It is not the most efficient sorting algorithm for large datasets but is easy to understand and implement.

Note: Bubble Sort is a stable sorting algorithm, meaning that it maintains the relative order of equal elements in the sorted output. If two elements have equal values, the original order is preserved.

Algorithm Steps:

• Start at the beginning of the list.
• Compare the first two elements. If they are in the wrong order, swap them.
• Move to the next pair of elements and repeat step 2.
• Continue this process until the end of the list is reached.
• Repeat the process for the entire list until no swaps are needed.

For example:

Let’s consider the following array for illustration:

Pass 1: Start with the first element in the list (index 0). Compare the current element with the next element.

• If the current element is greater than the next element, swap them.
• If the current element is smaller or equal, do nothing.

Again, Continue this process until the end of the list is reached in the first pass. compare 5 and 4 (swap)

Again, compare 5 and 2 (swap)

Again, compare 5 and 8 (no swap)

Pass 2: After the first pass, the largest element has moved to the rightmost position. Repeat the process for the remaining unsorted portion of the list (excluding the last element sorted in the previous pass).

Compare 1 and 4 (no swap):

Compare 4 and 2 (swap):

Compare 4 and 5 (no swap):

Compare 5 and 8 (no swap):

Time Complexity of Bubble Sort:

In the worst-case scenario, the time complexity of Bubble Sort is O(n²), where n is the number of elements in the array. This worst-case time complexity occurs when the input array is in reverse order, and every element needs to be compared and swapped in each pass.

In the best-case scenario, the time complexity is O(n). This occurs when the input array is already sorted, and the algorithm requires only one pass to determine that no swaps are needed.

Space Complexity of Bubble Sort:

The space complexity of Bubble Sort is O(1) because the algorithm only uses a constant amount of extra space to store temporary variables, regardless of the input size.