Bubble
sort
Let
a be an array of n numbers. Our aim is to sort the numbers in the array in
ascending order. The principle is to scan the array sequentially n-1 times and
in each scan do the following steps.
Scan – 1
i)
Take the first element and compare it
with the second element. If it is small don’t interchange; or else interchange
the two elements.
ii)
Then compare the second element with the
third element. If it is small don’t interchange; or else interchange the two
elements.
iii)
This process is continued till (n-1)th
element is compared with the nth element.
iv)
At the end of the first scan, the
highest element comes to the nth position.
i)
Take the first element and compare it
with the second element. If it is small don’t interchange; or else interchange
the two elements.
ii)
Then compare the second element with the
third element. If it is small don’t interchange; or else interchange the two
elements.
iii)
This process is continued till (n-2)th
element is compared with the (n-1)th element.
iv)
At the end of the second scan, the
highest element comes to the (n-1)th position.
Scan – (n-1)
In
the (n-1)th scan first element is compared with the second element.
Arrange
the given array of numbers in ascending order. Let the numbers in the array be
a[1]
= 43 a[2] = 72 a[3] = 10 a[4] = 23 a[5] = 1
Let i – is a pointer which counts the number
of scan
j – is a pointer which
is used to compare the first and second element.
a[1]
a[2] a[3] a[4] a[5] j j+1 i
\ Scan-
1
43 72 10 23 1 1 2 1
-
first is small no interchange 43 72 10 23 1 2 3 1
- first
is big interchange
43 10 72 23 1 3 4 1
- interchange
43 10 23 72 1 4 5 1
|
-
interchange
43 10 23 1
|
Scan – 2
43 10 23 1 1 2 2
|
10 43 23 1 2 3 2
|
-
interchange
10 23 43 1 3 4 2
|
|
-
interchange
10 23 1
|
|
Scan – 3
10 23 1 1 2 3
|
|
- no interchange 10 23 1 2 3 3
|
|
|
-
interchange
10 1
|
|
|
10 1 1 2 4
|
|
|
|
|
- interchange
The sorted list is
1 10 23 43 72.
It is clear from the above that for 5 data we need only 4 scan.
Procedure
bubble(a, n) /* a is the name of the array to be sorted
and n is the maximum numbers */
{
for i = 1 to n-1 do // loop to control the number of scan
for j = 1 to i+1 do
if (a[j] > a[j+1]) then // loop to compare elements.
{
temp
= a[j] ;
a[j] = a[j+1] ;
a[j+1] = temp ;
}
}
Complexity
Let f(n) be the number of
comparisons required to sort the given n number using bubble sort. Then
F(n) = sum of comparisons required
in each scan
For I = 1, we required n-1
comparison
For I = 2, we required n-2
comparison
For I = n-1, we required 1 comparison
Therefore
f(n) = (n-1) + (n-2) + ….. + 2 + 1
= (n-1) n
No comments:
Post a Comment