Bubble Sort

 

The bubble sort has no reading characteristics. It is very slow, no matter what data it is sorting. This algorithm is included for the shake of completeness not because of any merit. As the largest element is the bubble of sinks up to its final position. It is known as the bubble sort.

ALGORITHM:

1. Compare two adjacent elements and swap them if they are not in the correct order.

2. Do this for all elements in the list.

3. If even one element has been swapped in the above run of N elements, go to Step 1 and repeat the process. If no element has been swapped in the above run for N elements, stop. The list is sorted.

PSEUDOCODE:

bubble (data,n)

Here DATA is an array with N element. This algorithm sorts the element in DATA.

Step 1: [Loop]

Repeat step 2 and step 3 for K=1 to N-1

Step 2: [Initialize pass pointer PTR]

Set[PTR]=1

Step 3: [Execute pass]

Repeat while PTR <=N-K

a. If DATA [PTR] > DATA [PTR+1]

Then interchange DATA [PTR] & DATA [PTR+1]

[End of if structure]

b. Set PTR =PTR+1

[End of Step 1 Loop]

Step 4: Exit

PROTOTYPE CODE:

for ( i = 1 ; i < n ; i++ )

for ( j = n-1 ; j >= i ; j-- )

if ( a[j] < a[j-1] )

swap a[j] and a[j-1]

FUNCTIONING DIAGRAM EXAMPLE:

COMPLEXITY:

The bubble sort method of sorting an array of size n requires (n-1) passes and (n-1)

comparisons on each pass. Thus the total number of comparisons is (n-1) * (n-1) = n2

– 2n + 1, which is O(n2). Therefore bubble sort is very inefficient when there are more

elements to sorting.

Aso, The time for a sorting algorithm is measured in terms of the number of comparisons. The number f(n) of comparisons in the bubble sort is easily computed. There are n-1 comparisons during the first pass, which places the largest element in the last position; there are n-2 comparisons in the second step, which places the second largest element in the next to last position and so on.

F(n)=(n-1)+(n-2)+….+2+1=n(n-1)/2=n^2/2+0(n)=0(n^2)

The time required to execute the bubble sort algorithm is proportional to n^2, Where n is the number of input items.

STABILITY:

Bubble Sort This is stable because no item is swapped past another unless they are in the wrong order. So items with identical keys will have their original order preserved.