Get new post automatically.

Enter your email address:


7.1 Bubble Sort

The next O(N^2) algorithm that we will analyze is the bubble sort. The bubble sort works from the bottom-up (back to front), and evaluates each element to the one before it. If the element on the bottom has a smaller value than the top, the two are swapped, if not - they remain in their original position. The algorithm compares the next two elements from the bottom-up, no matter what the outcome of the previous comparison was. In this fashion, the smallest value "bubbles up" to the top in each iteration. In subsequent comparisons, the values that were bubbled up in previous iterations are no longer compared, since they are in place.
The code for the bubble sort is shown below, using a standard array of int variables. Two nested for loops are used. The first loop has n iterations, the number of elements. Each iteration, at least one element is set into its proper sorted position. The inner for loop runs from the bottom-up, comparing adjacent values, and stops at the group of values that have already been set in place, this position being one more each iteration of the outer loop.
void BubbleSort(int *nums, int n)
{
   for (int i=0; i<n-1; i++)
      for (int j=n-1; j>i; j--)
         if(nums[j] < nums[j-1]
            swap(j,j-1);
}

Another variant of this procedure, called bubble sort, is commonly taught: 
/* Bubble sort for integers */
#define SWAP(a,b)   { int t; t=a; a=b; b=t; }

void bubble( int a[], int n )
/* Pre-condition: a contains n items to be sorted */
    {
    int i, j;
    /* Make n passes through the array */
    for(i=0;i<n;i++)
        {
        /* From the first element to the end
           of the unsorted section */
        for(j=1;j<(n-i);j++)
           {
           /* If adjacent items are out of order, swap them */
           if( a[j-1]>a[j] ) SWAP(a[j-1],a[j]);
           }
        }
    }

Analysis

Each of these algorithms requires n-1 passes: each pass places one item in its correct place. (The nth is then in the correct place also.) The ith pass makes either ior n - i comparisons and moves. So:
or O(n2) - but we already know we can use heaps to get an O(n logn) algorithm. Thus these algorithms are only suitable for small problems where their simple code makes them faster than the more complex code of the O(n logn) algorithm. As a rule of thumb, expect to find an O(n logn) algorithm faster for n>10 - but the exact value depends very much on individual machines!. 


C Program - Implementing Bubble Sort Technique:
//Analysis of Algorithms 
//Sorting Techniques - C Data Structures 
//WACP  to Iimplement Bubble Sort Technique. 
//Program by:- GAURAV AKRANI.  
//TESTED:- OK 


#include<stdio.h> 
#include<conio.h> 
  
  void bubble(int a[],int n) 
  { 
      int i,j,t; 
      for(i=n-2;i>=0;i--) 
      { 
         for(j=0;j<=i;j++) 
         { 
             if(a[j]>a[j+1]) 
             { 
                   t=a[j]; 
                   a[j]=a[j+1]; 
                   a[j+1]=t; 
              } 
          }
     }//end for 1.
  }//end function. 
     
  void main() 
  {    
     int a[100],n,i;  
     clrscr(); 
         printf("\n\n Enter integer value for total no.s of elements to be sorted: "); 
         scanf("%d",&n); 
 
         for( i=0;i<=n-1;i++) 
         {
        printf("\n\n Enter integer value for element no.%d : ",i+1); 
            scanf("%d",&a[i]); 
         } 
  
         bubble(a,n); 
  
         printf("\n\n Finally sorted array is: "); 
         for( i=0;i<=n-1;i++) 
         printf("%3d",a[i]); 
  
         } //end program.


/*--------SAMPLE OUTPUT-------------------------
Enter integer value for total no.s of elements to be sorted: 6
Enter integer value for element no.1 : 89
Enter integer value for element no.2 : -4
Enter integer value for element no.3 : -67
Enter integer value for element no.4 : 5
Enter integer value for element no.5 : 78
Enter integer value for element no.6 : 11
Finally sorted array is: -67 -4 5 11 78 89
------------------------------------------ */  

Example:

Input: an array a[n].
Output: elements of a[n] in ascending order.
1. Set i to be the length of the entire sequence.
2. While i>1 do
2.1. inx = 0;
2.2. j = 1;
2.3. While j<i do
2.3.1. If a[inx]<a[j] then inx=j;
2.3.2. j =  j + 1;
2.4. swap a[inx] and a[i-1]
2.5. i = i - 1;

The pseudo code is depicted as the following flowchart:

This flowchart is implemented as below:
 
#include <stdio.h>

int main( ) {
  int data[10] = {5, 12, 6, 8, 3, 10, 4, 5, 7, 9};
  int i, j, inx, max;

  printf("The initial sequence:");
  for (i=0; i<10; i++) printf("%3d", data[i]);
  printf("\n");

  for (i=10; i>1; i--) {
    inx = 0;
    for (j=1; j<i; j++)
      if (data[inx]<data[j]) inx = j;
    max = data[inx];
    data[inx] = data[i-1];
    data[i-1] = max;
  }

  printf("The sorted sequence:");
  for (i=0; i<10; i++) printf("%3d", data[i]);
  printf("\n");

  return 0;
}

===========================================

Here is the program to sort the given integer in ascending order using bubble sort method. Please find the pictorial tutor of the bubble sorting.
Logic :  The entered integers are stored in the array A. Here, to sort the data in ascending order, any number is compared with the next numbers for orderliness. i.e. first element A[0] is compared with the second  element A[1]. If forth is greater than the prior element then swapping them, else no change. Then second element is compared with third element, and procedure is continued. Hence, after the first iteration of the outer for loop, largest element is placed at the end of the array. In the second iteration, the comparisons are made till the last but one position and now second largest element is placed at the last but one position. The procedure is traced till the array length.
If we complement the if condition in this program, it will give out the sorted array in descending order. Sorting can also be done in other methods, like selection sorting and insertion sorting, which follows in the next pages.

Here is the C program to sort the numbers using Bubble sort

#include<stdio.h>
void main()
{
 int A[20], N, Temp, i, j;
 clrscr();
 printf(“\n\n\t ENTER THE NUMBER OF TERMS…: “);
 scanf(“%d”,&N);
 printf(“\n\t ENTER THE ELEMENTS OF THE ARRAY…:”);
 for(i=0; i<N; i++)
 {
  gotoxy(25, 11+i);
  scanf(“\n\t\t%d”, &A[i]);
 }
 for(i=0; i<N-1; i++)
  for(j=0; j<N-i;j++)
   if(A[j]>A[j+1])
   {
    Temp = A[j];
    A[j] = A[j+1];
    A[j+1] = Temp;
   }
 printf(“\n\tTHE ASCENDING ORDER LIST IS…:\n”);
 for(i=0; i<N; i++)
  printf(“\n\t\t\t%d”,A[i]);
 getch();
}