Bubble Sort
Contents
Bubble Sort
Definition
Bubble sort is a sorting algorithm that works by repeatedly
stepping through lists that need to be sorted, comparing each pair of adjacent
items and swapping them if they are in the wrong order. This passing procedure
is repeated until no swaps are required, indicating that the list is sorted.
Bubble sort gets its name because smaller elements bubble toward the top of the
list.
Bubble sort is also referred to as sinking sort or comparison
sort.
How bubble sort works?
We take an
unsorted array for our example.
14
|
33
|
27
|
35
|
10
|
Bubble sort starts with very first two elements, comparing
them to check which one is greater.
14
|
33
|
27
|
35
|
10
|
In this case, value 33 is greater than 14, so it is already
in sorted locations. Next, we compare 33 with 27.
14
|
33
|
27
|
35
|
10
|
We find that 27 is smaller than 33 and these two values must
be swapped.
14
|
33
|
27
|
35
|
10
|
The new
array looks like this.
14
|
27
|
33
|
35
|
10
|
Next we compare 33 and 35. We find that both are in already sorted
positions.
14
|
27
|
33
|
35
|
10
|
Then we move
the next three values 35 and 10.
14
|
27
|
33
|
35
|
10
|
We know that 10 is smaller 35. Hence they are not sorted.
14
|
27
|
33
|
35
|
10
|
We swap these values. We find that we have reached the end of
the array. After one iteration, the array should look like this
14
|
27
|
33
|
10
|
35
|
To be precise, we are now showing how an array should look
like after each iteration. After the second iteration, it should look like this
14
|
27
|
10
|
33
|
35
|
Notice that after each iteration, at least one value moves at
the end.
14
|
10
|
27
|
33
|
35
|
And when there's no swap required, bubble sorts learn that an
array is completely sorted.
10
|
14
|
27
|
33
|
35
|
Bubble sort program in c
#include<stdio.h>
#include<conio.h>
int main ()
{
int DATA[100], n,
k ,ptr,swap;
clrscr();
printf("enter
the number of elements ");
scanf("%d", &n);
printf("enter
%d integers \n", n);
for(k=1; k<=n;
k++)
scanf("%d", &DATA[k]);
for(k=1;
k<=n-1; k++)
{
ptr=1;
while (ptr<=(n-k))
{
if
(DATA[ptr] > DATA[ptr+1])
{
swap =DATA[ptr];
DATA[ptr] = DATA[ptr+1];
DATA[ptr+1]= swap;
}
ptr=ptr+1;
}
}
printf("sorted list\n");
for(k=1; k<=n; k++)
printf("%d \n",
DATA[k]);
getch ();
return 0;
}
Sample of program
Comments
Post a Comment