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. The pass through the list is repeated until the list is sorted.

1. Start with the first element in the list.
2. Compare it with the next element. If the first element is greater than the second, swap them.
3. Move to the next element and repeat step 2 for the entire list.
4. After the first pass, the largest element is guaranteed to be at the end of the list.
5. Repeat steps 1-4 for the remaining unsorted elements until the entire list is sorted.

   Bubble-Sort(A, N)
1. for i <--- 1 to N-1
2.     for j <--- i to N-1
3.         if A[ j ] > A[ j + 1 ]
4.             exchange A[ j ] <---> A [ j + 1 ]
5. Stop

1. Comparison and Swapping

   • The algorithm starts by comparing the first two elements of the array.
   • If the first element is greater than the second, they are swapped; otherwise, they remain in their positions.

2. Iteration through the Array

   • The algorithm then moves to the next pair of elements (index 1 and index 2) and performs the comparison and swapping.
   • This process continues until the end of the array is reached in the first pass.

3. Largest Element "Bubbles" to the End

   • After the first pass, the largest element is guaranteed to be at the end of the array.
   • This is because in each pass, the algorithm compares and possibly swaps adjacent elements, "bubbling" the largest element to its correct position.

4. Repeat for Remaining Unsorted Elements

   • The algorithm repeats the process for the remaining unsorted elements, excluding the last one (which is already in its correct position).
   • Each subsequent pass guarantees the placement of the next largest unsorted element.

5. Optimization - Early Exit

   • Bubble Sort includes an optimization where the algorithm can exit early if no swaps are performed during a pass.
   • If no swaps occur in a pass, the array is already sorted, and the algorithm terminates.

6. Complete Iterations

   • The process is repeated until the entire array is sorted.
   • In each pass, the largest unsorted element is moved to its correct position.

7. Sorted Array

   • After the final pass, the array is fully sorted, and the algorithm terminates.

Consider an example:

Original List: 5, 3, 8, 4, 2

Pass 1:

• Compare 5 and 3, swap (List: 3, 5, 8, 4, 2)
• Compare 5 and 8, no swap (List: 3, 5, 8, 4, 2)
• Compare 8 and 4, swap (List: 3, 5, 4, 8, 2)
• Compare 8 and 2, swap (List: 3, 5, 4, 2, 8)

Pass 2:

• Compare 3 and 5, no swap (List: 3, 5, 4, 2, 8)
• Compare 5 and 4, swap (List: 3, 4, 5, 2, 8)
• Compare 5 and 2, swap (List: 3, 4, 2, 5, 8)

Pass 3:

• Compare 3 and 4, no swap (List: 3, 4, 2, 5, 8)
• Compare 4 and 2, swap (List: 3, 2, 4, 5, 8)

Pass 4:

• Compare 3 and 2, swap (List: 2, 3, 4, 5, 8)

Pass 5 (no swaps, list is sorted):

• List: 2, 3, 4, 5, 8

#include <stdio.h>

int array[10];

void input_array(int[], int);
void print_array(int[], int);
void bubble_sort(int[], int);

void main()
{
    input_array(array, 5);
    bubble_sort(array, 5);
    print_array(array, 5);
}
 
void input_array(int A[], int N)
{
    int i;

    printf("Enter the values for sorting :-\n");
    for (i = 1; i <= N; i++)
    {
        printf("Value %d :", i);
        scanf("%d", &A[i]);
    }
}

void print_array(int A[], int N)
{
    int i;

    printf("\nSorted array is : {");
    for (i = 1; i <= N; i++)
    {
        printf("%d, ", A[i]);
    }
    printf("}");
}

void bubble_sort(int A[], int N)
{
    int temp, i, j;

    for (i = 1; i <= N - 1; i++)
    {
        for (j = 1; j <= N - i; j++)
        {
            if (A[j] > A[j + 1])
            {
                temp = A[j];
                A[j] = A[j + 1];
                A[j + 1] = temp;
            }
        }
    }
}

• Bubble Sort has a time complexity of O(n^2) in the worst and average cases.
• In the best case (when the list is already sorted), it can have a time complexity of O(n).

• Bubble Sort is an in-place sorting algorithm, meaning it doesn't require additional memory space, resulting in a space complexity of O(1).

• Bubble Sort is a stable sorting algorithm, meaning the relative order of equal elements remains unchanged after sorting.