Modified bubble sort in C

prerequisites: Bubble Sort

What if the array is already half sorted?

For example:[23,44,0,1,2,3]

Now as you can see in the above example the array from the element 0 is already sorted.If we use bubble sort here it will still compare all the adjacent elements in the array thereby increasing the time complexity. So we make use of modified bubble sort algorithm thereby making the sorting more efficient. We also make use of an additional variable called as flag.

 #include
 void main()
 {
     int n,i;
     int a[100];
     printf("enter no. of elements\n");
     scanf("%d",&n);
     printf("enter the elements\n");
     for(i=0;i<n;i++)
     {
         scanf("%d",&a[i]);
     }
     printf("array before sorting:\n");
     displ(a,n);
     msort(a,n);
     printf("array after sorting:\n");
     displ(a,n);
 }
void displ(int a[],int n)
 {
     int i;
     for(i=0;i<n;i++)
     {
         printf("%d ",a[i]);
     }
     printf("\n");
 }
void msort(int a[],int n)
 {
     int i,j,temp,flag;
     for(i=0;ia[j+1])
             {
             temp=a[j];
             a[j]=a[j+1];
             a[j+1]=temp;
             flag=1;
             }
         }
         if(flag==0)
             break;
     }
 }

OUTPUT:

enter no. of elements
5
enter the elements
11
66
0
1
2
array before sorting:
11 66 0 1 2
array after sorting:
0 1 2 11 66

Leave a Reply