BUBBLE SORT:
This is the most commonly used sorting method. The bubble sort derives its name from the fact that the smallest data item bubbles up to the top of the sorted array.
Principle : The bubble sort method compares the two adjacent elements starting from the start of the list and swaps the two if they are out of order. This is continued up to the last element in the list and after each pass, a check is made to determine whether any interchanges were made during the pass. If no interchanges occurred, then the list must be sorted and no further passes are required.
Algorithm:
Procedure BUBBLESORT( A, N )
/ A is the array containing the list of data items
/ N is the number of data items in the list
Last N – 1
While Last > 0 Exch 0
Repeat For I = 0 to Last Step 1 If A[I] > A[I+1]
Then
A[I] ↔ A[I+1] Exch 1
End If End Repeat
If Exch = 1
Then
Exit Loop
Else
Last Last – 1
End If End While
End BUBBLESORT
|
In Bubble sort algorithm, initially Last is made to point the last element of the list and Exch flag is assumed 0. Starting from the first element, the adjacent elements in the list are compared. If they are found out of order then they are swapped immediately and Exch flag is set to 1. This comparison is continued until the last two elements are compared. After this pass, the Exch flag is checked to determine whether any exchange has taken place. If no exchange has taken place then the control comes out of the loop and the procedure comes to an end as the list
is sorted. If any exchange has taken place during the pass, the last pointer is decremented by 1 and the next pass is continued. This process continues until list is sorted.
Example:
| |||||||||||
N = 10Number of elements in the list
| |||||||||||
LPoints to last element ( Last )
| |||||||||||
Pass 1
| |||||||||||
i = 0 i =1
|
i = 2 i = 3 i = 4 i = 5 i = 6 i = 7 i = 8 i = 9
| ||||||||||
42
|
23
|
74
|
11
|
65
|
58
|
94
|
36
|
99
|
87
| ||
Out of orderSwap
|
L=9
| ||||||||||
23
|
42
|
74
|
11
|
65
|
58
|
94
|
36
|
99
|
87
| ||
Out of orderSwap
|
L=9
| ||||||||||
23
|
42
|
11
|
74
|
65
|
58
|
94
|
36
|
99
|
87
| ||
Out of orderSwap
|
L=9
| ||||||||||
23
|
42
|
11
|
65
|
74
|
58
|
94
|
36
|
99
|
87
| ||
Out of orderSwap
|
L=9
| ||||||||||
23
|
42
|
11
|
65
|
58
|
74
|
94
|
36
|
99
|
87
| ||
Out of orderSwap
|
L=9
| ||||||||||
23
|
42
|
11
|
65
|
58
|
74
|
36
|
94
|
99
|
87
| ||
Out of orderSwap
|
L=9
| ||||||||||
Pass 2
| |||||||||||
23
|
42
|
11
|
65
|
58
|
74
|
36
|
94
|
87
|
99
| ||
Out of orderSwap
|
L=8
| ||||||||||
23
|
11
|
42
|
65
|
58
|
74
|
36
|
94
|
87
|
99
| ||
Out of orderSwap
|
L=8
| ||||||||||
23
|
11
|
42
|
58
|
65
|
74
|
36
|
94
|
87
|
99
| ||
Out of orderSwap
|
L=8
| ||||||||||
23
|
11
|
42
|
58
|
65
|
36
|
74
|
94
|
87
|
99
| ||
Out of orderSwap
|
L=8
| ||||||||||
Pass 3
| |||||||||||
23
|
11
|
42
|
58
|
65
|
36
|
74
|
87
|
94
|
99
| ||
Out of orderSwap
|
L=7
| ||||||||||
23
|
11
|
42
|
58
|
65
|
36
|
74
|
87
|
94
|
99
| ||
Out of orderSwap
|
L=7
| ||||||||||
Pass 4
| |||||||||||
23
|
11
|
42
|
58
|
36
|
65
|
74
|
87
|
94
|
99
| ||
L=6
| |||||||||||
11
|
23
|
42
|
58
|
36
|
65
|
74
|
87
|
94
|
99
| ||
Out of orderSwap
|
L=6
| ||||||||||
Pass 5
| |||||||||||
11
|
23
|
42
|
36
|
58
|
65
|
74
|
87
|
94
|
99
| ||
Out of orderSwap
|
L=5
| ||||||||||
Pass 6
| |||||||||||
Adjacent numbers are compared up to L=4. But no swapping takes place. As there was no swapping taken place in this pass, the procedure comes to an end and we get a sorted list:
11
|
23
|
36
|
42
|
58
|
65
|
74
|
87
|
94
|
99
|
Advantages:
1. Simple and works well for list with less number of elements.
Disadvantages:
1. Inefficient when the list has large number of elements.
2. Requires more number of exchanges for every pass.