Bubble sort in C
Bubble sorting is a simple sorting technique in which we arrange the elements of the list by forming pairs of adjacent elements. That means we form the pair of the ith and (i+1)th element. If the order is ascending, we interchange the elements of the pair if the first element of the pair is greater than the second element. That means for every pair (list[i],list[i+1]) for i :=1 to (n−1) if list[i] > list[i+1], we need to interchange list[i] and list[i+1]. Carrying this out once will move the element with the highest value to the last or nth position. Therefore, we repeat this process the next time with the elements from the first to (n−1)th positions. This will bring the highest value from among the remaining (n−1) values to the (n−1)th position. We repeat the process with the remaining (n−2) values and so on. Finally, we arrange the elements in ascending order. This requires to perform (n−1) passes. In the first pass we have (n−1) pairs, in the second pass we have (n−2) pairs, and in the last (or (n−1)th) pass, we have only one pair. Therefore, the number of probes or comparisons that are required to be carried out is :
(n-1)+(n-2)+(n-3)+…..1 = n(n-1)/2 and the order of the algorithm is O(n2).
Example
#include <stdio.h>
#define MAX 10
void swap(int *x,int *y)
{
int temp;
temp = *x;
*x = *y;
*y = temp;
}
void bsort(int list[], int n)
{
int i,j;
for(i=0;i<(n-1);i++)
for(j=0;j<(n-(i+1));j++)
if(list[j] > list[j+1])
swap(&list[j],&list[j+1]);
}
void readlist(int list[],int n)
{
int i;
printf("Enter the elements\n");
for(i=0;i<n;i++)
scanf("%d",&list[i]);
}
void printlist(int list[],int n)
{
int i;
printf("The elements of the list are: \n");
for(i=0;i<n;i++)
printf("%d\t",list[i]);
}
int main()
{
int list[MAX], n;
printf("Enter the number of elements in the list max = 10\n");
scanf("%d",&n);
readlist(list,n);
printf("The list before sorting is:\n");
printlist(list,n);
bsort(list,n);
printf("The list after sorting is:\n");
printlist(list,n);
getchar();
return 0;
}
