1.Bubble sort

Bubble sort is a sorting algorithm that compares two adjacent elements and swaps them until they are in the intended order.

Just like the movement of air bubbles in the water that rise up to the surface, each element of the array moves to the end in each iteration. Therefore, it is called a bubble sort.

Working of Bubble Sort

Suppose we are trying to sort the elements in ascending order.

1. First Iteration (Compare and Swap)
2. Starting from the first index, compare the first and the second elements.
3. If the first element is greater than the second element, they are swapped.
4. Now, compare the second and the third elements. Swap them if they are not in order.
5. The above process goes on until the last element

Example of Bubble Sort

Given Array:
[5, 1, 4, 2, 8]

     Pass 1:

• Compare 5 and 1 → swap → [1, 5, 4, 2, 8]
• Compare 5 and 4 → swap → [1, 4, 5, 2, 8]
• Compare 5 and 2 → swap → [1, 4, 2, 5, 8]
• Compare 5 and 8 → no swap → [1, 4, 2, 5, 8]

Pass 2:

• Compare 1 and 4 → no swap
• Compare 4 and 2 → swap → [1, 2, 4, 5, 8]
• Compare 4 and 5 → no swap
• (8 is already in correct position)

     Pass 3:

• Compare 1 and 2 → no swap
• Compare 2 and 4 → no swap
• (Remaining elements already sorted)

Final Sorted Array:

[1, 2, 4, 5, 8]

Bubble sort Python code:

for i = 0 to n-1:

    for j = 0 to n-i-2:

        if arr[j] > arr[j+1]:

            swap(arr[j], arr[j+1])

Time Complexity of Bubble Sort:

Space Complexity:

• O (1) (in-place sorting, no extra space used)

Note:

Bubble Sort is simple but inefficient for large datasets due to its quadratic time complexity in most cases. It is mainly used for educational purposes.