C++ Program to sort elements using Bubble Sort [DEVCPP/GCC]

BUBBLE SORT

Bubble Sort is a sorting technique which is used to sort elements of an array. This technique involves multiple comparison of adjacent elements in single iteration.

This technique is named as bubble sort because the lighter elements are shifted "upwards" just as bubbles rise upwards. At the end of each iteration the heaviest element gets in its correct position.

EXAMPLE

STEPS

1. Input the elements of an array.

2. Pass the array and its length to the function Bubble_Sort(int list , int length )

3. Initialize i and j with 0.

4. Initialize a boolean variable (flag) with true.

5. Compare the jth element with(j+1)th element. If the value at list(j) is greater then list(j+1) then exchange jth elemet and (j+1)th element.
 
6. Increment j as j=j+1.

7. Repeat steps 4-5 till j<(length-i-1).

8. Check flag, if it remains true then the list is sorted and no further comparisons are required.

9. Increment i as i=i+1.

10. Repeat steps 4-7 till i<(length-1).

PROGRAM

// Program to sort elements in ascending order using Bubble Sort

#include <iostream>

using namespace std;

void Bubble_Sort( int list[], int length )
{
        int i,j,temp;
        bool flag;

        for(i=0 ; i<(length-1) ; i++)
        {
                flag=true;

                for(j=0 ; j<((length-1)-i) ; j++)
                {
                        if( list[j] > list [j+1] )
                       {
                                flag=false;
                                temp = list[j];
                                list[j] = list [j+1];
                                list[j+1] = temp;
                       }
                }

                if(flag)
               {
                         break;
               }
         }

cout<<"\n SORTED ARRAY: \n";

for(i=0 ; i<length ; i++ )
        {
                   cout<<"\nA["<<i<<"]: "<<list[i];
         }
}

int main()
{
        int arr[10],i;

        cout<<"\nENTER LIST OF NUMBERS TO SORT: \n";

        for(i=0 ;i< 10 ; i++ )
        {
                cout<<"A["<<i<<"]: ";
                cin>>arr[i];
        }

        Bubble_Sort(arr,10);

        return 0;
}

TIME COMPLEXITY

BEST CASE: When the List is already sorted.
COMPLEXITY: O(n)

AVERAGE CASE: When the List is not sorted.
COMPLEXITY: O(n^2)

WORST CASE: When the List is already sorted in reverse order.
COMPLEXITY: O(n^2)

OUTPUT

Author : Prateek Gupta

Share this

Related Posts