BUBBLE SORTING: One of the characteristics of this sort is that it is easy to understand and program it is probably the least efficient. The basic idea underlying the bubble sort is to pass through the file sequentially several times. Each pass consists of comparing each element in the file with its successor and interchanging the two elements if they are not in proper order. The method is called the bubble sort because each number slowly “bubbles” up to its proper position.
In this sort, the number of interchanges cannot be greater than the number of comparisons it is likely that it is the number of interchanges rather than the number of comparisons that takes up most times in the program’s execution. The only redeeming features of the bubble sort are that it requires little additional space (one additional record to hold the temporary value for interchanging and several simple integer variables) and that it is O (N) in the case that the file is completely sorted (or most completely sorted).
This follows from the observation that only one pass of (N – 1) comparisons (and no interchanges) is necessary to establish that a sorted file is sorted. The bubble sort technique possesses one very important property- ” Once there is no swapping of elements in a particular pass, there will be no further swapping of elements in the subsequent passes. This property can be exploited to reduce unnecessary (redundant) passes. For this purpose we can use a flag to determine if any under interchange has taken place, if yes only then proceed with the next pass; otherwise, stop. The first pass makes an n – 1 comparison, the second pass makes n – 2 and so on. So total comparisons are (N – 1) + (N -2) + (N – 3) + + 2 + 1 = N (N – 1) / 2 = O(N^2).
Algorithm Bubble sorting in c programming.
BUBBLE_SORT (A,N)
Here A is an array with N elements. This algorithm sorts the array A with N elements in ascending order.
1. Set SWAP: = True.
2. Set I : = 1.
3. Repeat Steps 4 to 6 while I < N AND SWAP = True :
4. Set SWAP: = False.
5. Repeat Steps for J: = 1 to N – 1 :
If A [J] > A [J + 1], then :
Set TEMP : = A [J]
(b) Set A [J] : = A [J + 1].
(c) Set A [J + 1] : = TEMP.
(d) Set SWAP : = True.
[End of If structure.]
[End of Step 5 loop.]
6. Set I : = I + 1.
[End of Step 3 loop.]
7. Return.
Bubble Sorting program in C.
#include<stdio.h>
#include<conio.h>
#define SIZE 10
void bubble_sort(int [], int);
void main()
{
int a[SIZE],n,i;
printf("Enter how many elements");
scanf("%d",&n);
/*input array*/
for(i=0;i<n;i++)
{
printf("Enter element %d ",i+1);
scanf("%d",&a[i]);
}
bubble_sort(a,n);
/*Output Array */
for(i=0;i<n;i++)
printf("%d ",a[i]);
getch();
}
void bubble_sort(int a[], int n)
{
int i,j,SWAP,t;
SWAP=1;
i=1;
while(i < n && swap == 1)
{
SWAP = 0;
for(j=0;j<n-1;j++)
{
if(a[j]>a[j+1])
{
t = a[j];
a[j] = a[j+1];
a[j+1] = t;
SWAP = 1;
}
}
i++;
}
}Also, Read