## Thursday, December 1, 2011

### 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 etc2. For i = 0 to i < (n - i), repeat step 3 to 43. For j = 0 to j < (n-i-1), repeat step 44. If x[j] > x[j+1] then swap the element as       temp = x[j]       x[j] = x[j+1]       x[j+1] = temp5. Display the sorted array

Source code for Bubble Sort

#include<iostream>using namespace std;class BubbleSort{    private:        int no_of_elements;        int elements[10];    public:        void getarray();        void sortit();        void display();};void BubbleSort::getarray(){    cout<<"How many elements?: ";    cin>>no_of_elements;    cout<<"Insert array of element to sort: ";    for(int i=0;i<no_of_elements;i++){        cin>>elements[i];    }}void BubbleSort::sortit(){    int temp;    for(int i = 0; i < no_of_elements; i++){        for(int j =0; j < no_of_elements - 1 - i; j++){            if(elements[j] > elements[j+1]){                temp = elements[j];                elements[j] = elements[j+1];                elements[j+1] = temp;            }        }    }}void BubbleSort::display(){    cout<<"The sorted element is\n";    for(int i = 0 ; i < no_of_elements; i++){        cout<<elements[i]<<" ";    }}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)

#### 1 comment:

1. ahhh thankyou for this artical sir , i need that one :)