Data Structure: Implementing Bubble Sort using C/C++

In Bubble sort, each pass consists of comparison each element in the file with its successor (i.e. x[i] with x[i+1]) and interchanging two elements if they are not in the proper order.

Example: Let us consider following array of elements

16

 52 42 35 8

Following comparison are make on the first pass

x[0] with x[1] (16 with 52) No interchange
x[1] with x[2] (52 with 42) Interchange
x[2] with x[3] (52 with 35) Interchange

Thus after first pass, we can get: 16      42     35       8       52

  • Note that after first pass, largest element (i.e. 52) get its proper position
  • In general, x[n-1] will be in its proper position after iteration 1

We can list completer iterations as follows:

Iteration 0:       16          52         42               35                8
Iteration 1:       16          42         35               8                 52
Iteration 2:       16          35         8                42                52
Iteration 3:       16          8          35               42                52
Iteration 4:        8          16         35               42                52

Hence, for ith iteration, n-i iteration is required.

Algorithm

1. Declare and initialize necessary variable such as number of data items n, array, i, j etc
2. For i = 0 to i 3. For j = 0 to j 4. If x[j] > x[j+1] then swap the element as
       temp = x[j]
       x[j] = x[j+1]
       x[j+1] = temp
5. Display the sorted array

Source code for Bubble Sort

 
#include
 
 
 
 
using namespace std;
 
 
 
 
class BubbleSort{
 
 
    private:
 
 
        int no_of_elements;
 
 
        int elements[10];
 
 
    public:
 
 
        void getarray();
 
 
        void sortit();
 
 
        void display();
 
 
};
 
 
 
 
void BubbleSort::getarray(){
 
 
    coutHow many elements?: ";
 
 
    cin>>no_of_elements;
 
 
    coutInsert array of element to sort: ";
 
 
    for(int i=0;i
 
 
        cin>>elements[i];
 
 
    }
 
 
}
 
 
 
 
void BubbleSort::sortit(){
 
 
    int temp;
 
 
    for(int i = 0; i 
 
 
        for(int j =0; j 
 
 
            if(elements[j] > elements[j+1]){
 
 
                temp = elements[j];
 
 
                elements[j] = elements[j+1];
 
 
                elements[j+1] = temp;
 
 
            }
 
 
        }
 
 
    }
 
 
}
 
 
 
 
void BubbleSort::display(){
 
 
    coutThe sorted element is\n";
 
 
    for(int i = 0 ; i 
 
 
        cout ";
 
 
    }
 
 
}
 
 
 
 
int main(){
 
 
    BubbleSort BS;
 
 
    BS.getarray();
 
 
    BS.sortit();
 
 
    BS.display();
 
 
    return 0;
 
 
}
 
 
 
 
Efficiency of Bubble Sort:
 
 
The number of comparison between n elements is equal to (n-1) and total number of passes is also (n-1), The total number of comparison are therefore (n-1) * (n-1). Hence the efficiency of bubble sort is O(n^2)