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

| 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 < (n - i), repeat step 3 to 4

3. For j = 0 to j < (n-i-1), repeat step 4

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<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)

## No comments:

## Post a Comment