Bubble Sorting : Algorithm And Bubble Sort Program in C

Bubble Sort is a simple way to sort numbers in an array. In this method, each element is compared with its next neighbor. If the first element is larger than the next, we swap them. This keeps going for the whole array. After the first pass, the largest number moves to the end. This process repeats until the array is fully sorted.

Bubble Sort is not good for large arrays because it always takes about O(n²) steps in average and worst cases.

How Bubble Sort Works

Compare Adjacent Items: Starting from the beginning of the list, compare each pair of adjacent items.
Swap if Necessary: If the first item in the pair is greater than the second, swap them. This step ensures that after each complete pass through the list, the largest unsorted item is moved to its correct position.
Repeat: Continue making passes through the list, each time ignoring the last item (as it’s already in its correct place).
End When Sorted: The algorithm stops when a pass through the list requires no swaps, meaning the list is sorted.

Sorting Using Bubble Sort

Suppose we have an array arr of size 5 with array element [12, 8, 5, 11, 15].

First Pass

Compare 12 and 8. Since 12 > 8, swap them: [8, 12, 5, 11, 15]
Compare 12 and 5. Since 12 > 5, swap them: [8, 5, 12, 11, 15]
Compare 12 and 11. Since 12 > 11, swap them: [8, 5, 11, 12, 15]
Compare 12 and 15. Since 12 < 15, do nothing: [8, 5, 11, 12, 15]

Second Pass

Compare 8 and 5. Since 8 > 5, swap them: [5, 8, 11, 12, 15]
Compare 8 and 11. Since 8 < 11, do nothing: [5, 8, 11, 12, 15]
Compare 11 and 12. Since 11 < 12, do nothing: [5, 8, 11, 12, 15]
No need to compare 12 and 15, as 15 is already in place.

Bubble sort algorithm — Second pass of Bubble Sort

Third Pass

Compare 5 and 8. Since 5 < 8, do nothing: [5, 8, 11, 12, 15]
Compare 8 and 11. Since 8 < 11, do nothing: [5, 8, 11, 12, 15]
There’s no need to compare further as the remaining elements are already sorted.

Fourth Pass

At this point, the array is sorted as [5, 8, 11, 12, 15]. Each step involved comparing adjacent elements and swapping them if they were in the wrong order. This process is repeated, ignoring the last element each time since it’s in its correct position, until no swaps are needed, indicating that the array is sorted.

Pseudo Code of Bubble Sort

begin BubbleSort(arr, n)
for I=0 to N-1
    for J=0 to N-I
         if arr[j] > arr[j+1]
             swap(arr[j], arr[j+1])
         end if
     end for
end for
return arr
end BubbleSort

Algorithm of Bubble Sort

Have an array arr[] of size n.
For i = 0 to n - 2 (this runs n-1 passes):
- Set swapped = 0 (used to stop early if already sorted).
- For j = 0 to n - i - 2:
  - If arr[j] > arr[j+1], swap arr[j] and arr[j+1] and set swapped = 1.
- If swapped == 0 after the inner loop, break (the array is already sorted).
End — the array is now sorted.

Bubble Sort Program in C

#include<stdio.h>
#include<conio.h>

void main(){
    int arr[100],i,j,n,key;
    printf("Enter the number of elements you want to sort:\n");
    scanf("%d",&n);
    printf("Now enter the %d elements you want to sort: \n",n);
    for(i=0;i<n;i++){
        scanf("%d",&arr[i]);
    }
    printf("before sorting:\n");
    for(i=0;i<n;i++){
        printf("%d \t",arr[i]);
    }
    for(i=0;i<n;i++)
    {
        for(j=0;j<n-i-1;j++){
            if(arr[j]>arr[j+1])
            {
                key=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=key;
            }
        }
    }
    printf("\n");
    printf("after sorting:\n");
    for(i=0;i<n;i++){
        printf("%d \t",arr[i]);
    }
    getch();
}

Output :

Enter the number of elements you want to sort:
5
Now enter the 5 elements you want to sort: 
78
96
12
2
55
before sorting:
78      96      12      2       55 
after sorting:
2       12      55      78      96

Explanation of Code of Bubble Sort

This above program starts by including the header files stdio.h and conio.h. The stdio.h file allows the program to use input/output functions like printf and scanf, while conio.h is used for getch(), which waits for a key press so the output stays on the screen before the program closes. Inside the main function, the program declares an array arr[100] to store up to 100 numbers, loop counters i and j, a variable n to store the number of elements the user wants to sort, and a temporary variable key used for swapping values. The program first asks the user to enter the number of elements and stores it in n, then prompts the user to input n numbers, storing each number in the array arr. It prints the array before sorting to show the original order. The Bubble Sort algorithm then runs, where the outer loop (i loop) ensures multiple passes through the array so that the largest unsorted number “moves” to its correct position. The inner loop (j loop) compares each element with its next neighbor, and if the current element is greater than the next, the program swaps them using the temporary variable key. This process continues until all numbers are sorted in ascending order. After sorting, the program prints the sorted array to show the result. Finally, getch() is used to pause the program, allowing the user to view the sorted output before the program window closes.

Time & Space Complexity

Time Complexity

Case	Time Complexity
Best Case	O(n)
Average Case	O(n²)
Worst Case	O(n²)

Space Complexity

The space complexity of Bubble Sort is O(1) for all cases – best, average, and worst.

Advantages of Bubble Sort

Simplicity: It’s straightforward to understand and implement, making it a good educational tool.
Detects a Sorted List Early: If the list is already sorted (or nearly sorted), Bubble Sort can detect this and terminate early, making it efficient in such cases.
Stable Sort: Keeps the order of equal elements the same.
In-Place Algorithm: Does not need extra memory, only swaps inside the same array.
Works on Small Data: For small lists, it works fine and is easy to use.

Real-Life Example of Bubble Sort

Think of a deck of number cards mixed up. With Bubble Sort, you compare each card with the next one and swap if the first is bigger. You keep doing this over and over, each time checking one less card, until all the cards are in order from smallest to largest.

Conclusion

Bubble Sort, with its simplicity and intuitive process, is an excellent introduction to sorting algorithms, despite not being the most efficient for large datasets. It teaches important concepts in computer science, like iteration, comparisons, and swaps, which are foundational in more complex algorithms. Its straightforward logic mirrors everyday sorting processes, bridging abstract data structures with tangible, real-world tasks.