Bubble Sort | Algorithm | MyCodingNetwork

Bubble Sort

Bubble sort is a sorting algorithm which is used to sort the elements of an array and its time complexity O(N²). This algorithm’s time complexity is not as efficient as Merge Sort but still it is one of the simplest sorting algorithms.

Source Code:

Output:

The highlighted part is the sorted array (ascending order).

Working:

In the program shown above, we have used bubble sort technique to sort the array in ascending order, given by the user as the input (in the main( ) function). The entire bubble sorting algorithm (in the program) takes place in the function bubblesort(), the function takes two parameters. 

When an array undergoes bubble sort, continuous swapping takes place (if the array is not in desired order). The program given above is to arrange the array in ascending order, it can be changed to descending order, simply by changing “greater than” symbol to “less than” symbol on line 33. Swapping takes place from line 36(swapping takes place only if the elements are not in the desired order). Further, there is a boolean variable f for improving the time complexity of the algorithm, it is used to check whether the array is completely swapped or not at each iteration of first for(at line 28 of the program) loop.

Worst-case time complexity: O (N²)

Best-case time complexity: O(N)

Algorithm:

For ascending order:

for(int i=0; i<length-1 ;i++)
        {   f=false;
            for(int j=0; j<(length-i-1);j++)
            {
                if(arr[j]>arr[j+1])
                {
                    temp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                    f=true;
                }
            }
            if(f==false)
            break;
        }

For descending order:

for(int i=0; i<length-1 ;i++)

        {   f=false;

            for(int j=0; j<(length-i-1);j++)

            {

                if(arr[j]<arr[j+1])//Only greater than

                //symbol is converted to less than symbol

                {

                    temp=arr[j];

                    arr[j]=arr[j+1];

                    arr[j+1]=temp;

                    f=true;

                }

            }

            if(f==false)

            break;

        }

Hope you liked this explanation, for any doubt or feedback you can write down in the comment section.