Bubble Sort in C

Sorting is a necessary concept we need to learn in any programming language. Mostly sorting is done on arrays involving numbers and is a stepping stones to mastering the art of techniques to traversing and accessing data from arrays.
The type of sorting technique we are going to talk about in today's article will Bubble Sort.

Bubble Sort

Bubble sorting is a simple sorting algorithm that works by repeatedly swapping adjacent elements if they are in wrong order. This method of sorting an array is not suitable for large data sets as the time complexity for average and worst case scenarios is very high.

Algorithm of Bubble Sort :

1. Bubble Sort organizes an array by sorting it in multiple passes.
2. First Pass: The largest element moves to the last position, its correct place.
3. Second Pass: The second-largest element moves to the second-to-last position, and this continues for subsequent passes.
4. With each pass, only the unsorted portion of the array is processed.
5. After k passes, the largest k elements are in their correct positions in the last k slots.
6. During each pass:
   • Compare adjacent elements in the unsorted section.
   • Swap the elements if the larger one appears before the smaller one.
   • By the end of the pass, the largest unsorted element moves to its correct position. This process repeats until the entire array is sorted.

How Does Bubble Sort Work ?

Below is the implementation of the bubble sort. It can be optimized by stopping the algorithm if the inner loop didn’t cause any swap.

// Easy implementation of Bubble sort
#include <stdio.h>
int main(){
    int i, j, size, temp, count=0, a[100];
    //Asking the user for size of array
    printf("Enter the size of array you want to enter = \t");
    scanf("%d", &size);
    //taking the input array through loop
    for (i=0;i<size;i++){
        printf("Enter the %dth element",i);
        scanf("%d",&a[i]);
    }
    //printing the unsorted list
    printf("The list you entered is : \n");
    for (i=0;i<size;i++){
        printf("%d,\t",a[i]);
    }
    //sorting the list
    for (i = 0; i < size - 1; i++) {
        count = 1;
        for (j = 0; j < size - i - 1; j++) {
            if (a[j] > a[j + 1]) {
                //swapping elements
                temp=a[j];
                a[j]=a[j+1];
                a[j+1]=temp;
                count = 1;
            }
        }

        // If no two elements were swapped by inner loop,
        // then break
        if (count == 1)
            break;
    }
    // printing the sorted list
    printf("\nThe sorted list is : \n");
    for (i=0;i<size;i++){
        printf("%d,\t",a[i]);
    }
    return 0;

}

Output :

**

Complexity Analysis of Bubble Sort:

Time Complexity: O(n2)
Auxiliary Space: O(1)

Advantages of Bubble Sort:

• Bubble sort is easy to understand and implement.
• It does not require any additional memory space.
• It is a stable sorting algorithm, meaning that elements with the same key value maintain their relative order in the sorted output.

Disadvantages of Bubble Sort:

• Bubble sort has a time complexity of O(n2) which makes it very slow for large data sets.
• Bubble sort is a comparison-based sorting algorithm, which means that it requires a comparison operator to determine the relative order of elements in the input data set. It can limit the efficiency of the algorithm in certain cases.

Do comment if you have any queries !!
And all discussions will be appreciated :)

The above is the detailed content of Bubble Sort in C. For more information, please follow other related articles on the PHP Chinese website!