Bubble Sort

    Bubble sort in C is the most straightforward sorting technique to sort an array. Sorting is the technique used to arrange a variety in a structured way that can be ascending or descending in numerical or lexicographical order. It is a well-known competitive approach that every programmer must know. Sorting is required to reduce the time when data searching is the need for extensive data in companies or organizations. Sorting make more readable data format. The data can be found easily and quickly from the sorted data. There are various types of sorting algorithms available as per the need. Bubble sorting is one of the sorting algorithm techniques.

    Bubble Sort in C

    Let’s start with understanding the basics of Bubble Sort in C.

    What is a Bubble Sort?

    Bubble sort is the simple sorting algorithm that works on the concept of a comparison-based technique. Bubble sort sometimes is also known as sinking sort in case the more significant value (or heavier value) is found at the top of the list, and then this sink to the bottom. This algorithm technique starts with comparing the first two adjacent elements of an array or list . This is named a bubble sort, for the way that larger or smaller elements bubble up to the top position. Bubble sort makes multiples pass through an array or a list to give a sorted output. In each pass, every two adjacent elements are to be compared and swapped if required as per the condition. Once this process is applied to the complete array of elements, this is called the first step. A similar process will continue until the result is out in a sorted output. If n represents the number of, elements then (n-1) steps to be performed by the bubble sort algorithm to produce sorted output. The worst-case and average-case complexity of bubble sort is O(n^2), where n is the number of elements being sorted. If the list is already,y sorted i.e. in the best case, then the complexity of bubble sort is O(n). The time complexity of bubble sort is O(n^2), and space complexity is O(1). Bubble Sort Bubble sort begins by comparing every adjacent pair of elements; if the elements are in the wrong order (the first element is greater than the second element), then they are exchanged from their positions. After each comparison cycle, there is one less element to be compared, and this will continue until there are no more elements left in the list for comparison. Examples of Bubble sort using C and Java are below: -

    Example of Bubble Sort using C Programming

    /*C Program of Bubble Sort in ascending order.*/
    #include <stdio.h>
    int main()
    {
        int data[100],i,n,step,temp;
        printf("Enter the number of elements you want to be sorted: ");
        scanf("%d",&n);
        for(i=0;i<n;++i)
        {
            printf("%d. Enter element here: ",i+1);
            scanf("%d",&data[i]);
        }
        for(step=0;step<n-1;++step)
        for(i=0;i<n-step-1;++i)
        {
            if(data[i]>data[i+1])   /* If you want to sort in descending order, change > to < here only. */
            {
                temp=data[i];
                data[i]=data[i+1];
                data[i+1]=temp;
            }
        }
        printf("In ascending order: ");
        for(i=0;i<n;++i)
             printf("%d  ",data[i]);
        return 0;
    }
    

    Enter the number of elements you want to be sorted: 9

    Enter element here: 12
    Enter element here: 3
    Enter element here: 0
    Enter element here: -11
    Enter element here: 1
    Enter element here: 4
    Enter element here: 9
    Enter element here: -2
    Enter element here: -6

    In ascending order: -11 -6 -2 0 1 3 4 9 12 In this example of a bubble sort in C, first, the user is asked to enter the total number of elements to be entered in the data structure . Using a loop the user enters the data elements. The elements are then compared for sorting. If condition if(data[i]>data[i+1]),  is true for any iteration, elements are swapped and the loop moves to the next comparison. When all elements of the list are compared, the final sorted output is printed on the screen after the comparison between all the elements of the data structure ends. Here the number of elements (n) is 9, so steps in sorting will be (n-1), i.e., 8.

    Example of Bubble Sort using Java

    We can also write the program in java for bubble sort using a class and array of elements.

    // Bubble sort implementation using Java program
    class BubbleSort 
    { 
        void bubbleSort(int arr[]) 
        { 
            int n = arr.length; 
            for (int i = 0; i < n-1; i++) 
                for (int j = 0; j < n-i-1; j++) 
                    if (arr[j] > arr[j+1]) 
                    { 
                        // swap arr[j+1] and arr[i] 
                        int temp = arr[j]; 
                        arr[j] = arr[j+1]; 
                        arr[j+1] = temp; 
                    } 
        } 
         /* Prints the array */
        void printArray(int arr[]) 
        { 
            int n = arr.length; 
            for (int i=0; i<n; ++i) 
                System.out.print(arr[i] + " "); 
            System.out.println(); 
        } 
          // Driver method to test above 
        public static void main(String args[]) 
        { 
            BubbleSort ob = new BubbleSort(); 
            int arr[] = {39, 88, 72, 90, 25, 12, 22, 16}; 
            ob.bubbleSort(arr); 
            System.out.println("Sorted array:"); 
            ob.printArray(arr); 
        } 
    }

    Output:

    Sorted array:

    12 16 22 25 39 72 88 90

    Example of Bubble Sort using C++

    #include <bits/stdc++.h>
    using namespace std;
    
    void swap(int *xp, int *yp)
    {
        int temp = *xp;
        *xp = *yp;
        *yp = temp;
    }
    
    void applyBubbleSort(int arr[], int n)
    {
    int i, j;
    
    for (i = 0; i < n-1; i++)   
        for (j = 0; j < n-i-1; j++)
            if (arr[j] > arr[j+1])
                swap(&arr[j], &arr[j+1]);
    }
    
    int main()
    {
        int arr[] = {5, 4, 1, 2, 3};
    
        int n = sizeof(arr)/sizeof(arr[0]);
    
        applyBubbleSort(arr, n);
    
        for (int i=0; i < n; i++)
            cout<<arr[i]<<" ";
        return 0;
    }

    Output

    1 2 3 4 5

    Example of Bubble Sort using Python

    def applyBubbleSort(arr):
        n = len(arr)
    
        for i in range(n):
    
            for j in range(0, n-i-1):
                if arr[j] > arr[j+1] :
                    arr[j], arr[j+1] = arr[j+1], arr[j]
    
    arr = [5, 4, 1, 2, 3]
    
    applyBubbleSort(arr)
    
    for i in range(len(arr)):
        print(arr[i], end=" ")
    
     

    Output

    1 2 3 4 5

    Real-Time Application

    The only example of bubble sort in the real-time application is a classroom where so many students present with a different height. The teacher starts comparing the heights of the first two adjacent students, and if the front side student is taller than the second, the persons swapped their positions. This repeats until all students stand in their height ascending or descending order. Real time application of Bubble Sort Every sorting algorithm has its advantages and disadvantages. Here is the list of advantages and disadvantages of the Bubble Sort algorithm.

    Advantages

    • It is very simple to write and easy to understand.
    • This sorting requires only a few lines of code and is easy to implement.
    • A sorted array performs greatly and efficiently.
    • Needs no external memory to store temporary data.
    • The stability factor is provided by bubble sort.

    Disadvantages

    • Not efficient for the large collection of data.
    • Not useful in case of a reverse ordered collection of data.
    • It completes the minimum of (n-1) steps even if the comparison is not required.
    • Oldest, but the slowest Algorithm-Bubble sort is very slow in processing. So it is useful for only small sets of data.
    • Even worst-case time complexity is not efficient as other sorting algorithms.

    People are also reading: