Friday, March 16, 2012

Bubble Sort Modification

Previous bubble-sort program is inefficient for large arrays.
The following is the modification to that previous program.The program is modify as follow:
  • After the first pass, the largest number is guaranteed to be in the highest-numbered element of the array and so on.Instead of making nine comparisons on every pass, this new program make eight comparisons on the second pass, seven on the third pass, and so on.
  • Check at the end of each pass whether any swaps have been made. If none has been made, then the data must already be in the proper order, so the program should terminated.
/*
   title: bubbleSortModification
   author: aeriqusyairi
   date: Jan25 2012
*/
#include<stdio.h>
#define SIZE 10

int main(){
   int a[ SIZE ] = { 2, 6, 4, 8, 10, 12, 89, 68, 45, 37 };
   int pass, i, j, k, hold;
   
   printf("Data items in original order\n");
   
   /*output original array*/
   for(i =0; i < SIZE; i++){
      printf("%4d", a[i]);        
   }    
   
   /*bubble sort*/
   for(pass = 1, j = 1; pass < SIZE; pass++, j++, k = 0 ){
      for(i = 0 ; i < SIZE - j; i++){
         if(a[i] > a[i+1]){
            hold = a[i];
            a[i] = a[i + 1];
            a[i + 1] = hold; 
            k++;       
         }      
      }   
      /*check if any swap happen*/
      if(k == 0)
         break;      
   }
   
   printf("\nData items in ascending order\n");
   
   for(i = 0; i < SIZE; i++){
      printf("%4d", a[i]);      
   }
   
   printf("\n");
   
   system("pause");
   return 0;
}

2 comments:

  1. I don't think there is a need for additional variable j.
    Given that both pass and j are incremented by 1 each turn and the 1st loop terminates when pass = SIZE i.e. runs until pass < SIZE
    You could have simply used i < SIZE - pass in the 2nd loop.
    Please correct me if I am wrong.

    ReplyDelete