#include <stdio.h>
#include <sys/time.h>
int i, j, temp, flag;
 
void simple(int arr[], int n) {
   for (i = 0; i < n - 1; i++) {
       for (j = 0; j < n - 1; j++) {
           if (arr[j] > arr[j + 1]) {
               temp = arr[j];
               arr[j] = arr[j + 1];
               arr[j + 1] = temp;
           }
       }
   }
}
 
void semi(int arr[], int n) {
   for (i = 0; i < n - 1; i++) {
       for (j = 0; j < n - i - 1; j++) {
           if (arr[j] > arr[j + 1]) {
               temp = arr[j];
               arr[j] = arr[j + 1];
               arr[j + 1] = temp;
           }
       }
   }
}
 
void optimized(int arr[], int n) {
   int flag = 0;
   for (i = 0; i < n - 1; i++) {
       flag = 0;
       for (j = 0; j < n - i - 1; j++) {
           if (arr[j] > arr[j + 1]) {
               temp = arr[j];
               arr[j] = arr[j + 1];
               arr[j + 1] = temp;
               flag = 1;
           }
       }
       if (flag == 0) {
           break;
       }
   }
}
 
int main() {
   int n, choice, t1, t2, tc;
   struct timeval tt;
   struct timezone tz;
   printf("Enter the size:- \n");
   scanf("%d", &n);
   int arr[n];
   printf("Enter %d elements:- \n", n);
   for (i = 0; i < n; i++) {
       scanf("%d", &arr[i]);
   }
   printf("\nSelect type of Bubble Sort\n1:- Simple\n2:- Semi Optimized\n3:- Optimized\n ");
   scanf("%d", &choice);
 
   switch(choice){
       case 1:
       gettimeofday(&tt,&tz);
       t1=tt.tv_usec;
       simple(arr,n);
       gettimeofday(&tt,&tz);
       t2=tt.tv_usec;
       break;
       case 2:
       gettimeofday(&tt,&tz);
       t1=tt.tv_usec;
       semi(arr,n);
       gettimeofday(&tt,&tz);
       t2=tt.tv_usec;
       break;
       case 3:
       gettimeofday(&tt,&tz);
       t1=tt.tv_usec;
       optimized(arr,n);
       gettimeofday(&tt,&tz);
       t2=tt.tv_usec;
       break;
       default:
       printf("\n Invalid Choice\n");
   }
   printf("\nSorted Array\n");
   for (i = 0; i < n; i++) {
       if (i == n - 1) {
           printf("%d", arr[i]);
       } else {
           printf("%d, ", arr[i]);
       }
   }
   tc = t2 - t1;
   printf("\nTime Complexity = %d\n", tc);
   return 0; }

I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzeXMvdGltZS5oPgppbnQgaSwgaiwgdGVtcCwgZmxhZzsKIAp2b2lkIHNpbXBsZShpbnQgYXJyW10sIGludCBuKSB7CiAgIGZvciAoaSA9IDA7IGkgPCBuIC0gMTsgaSsrKSB7CiAgICAgICBmb3IgKGogPSAwOyBqIDwgbiAtIDE7IGorKykgewogICAgICAgICAgIGlmIChhcnJbal0gPiBhcnJbaiArIDFdKSB7CiAgICAgICAgICAgICAgIHRlbXAgPSBhcnJbal07CiAgICAgICAgICAgICAgIGFycltqXSA9IGFycltqICsgMV07CiAgICAgICAgICAgICAgIGFycltqICsgMV0gPSB0ZW1wOwogICAgICAgICAgIH0KICAgICAgIH0KICAgfQp9CiAKdm9pZCBzZW1pKGludCBhcnJbXSwgaW50IG4pIHsKICAgZm9yIChpID0gMDsgaSA8IG4gLSAxOyBpKyspIHsKICAgICAgIGZvciAoaiA9IDA7IGogPCBuIC0gaSAtIDE7IGorKykgewogICAgICAgICAgIGlmIChhcnJbal0gPiBhcnJbaiArIDFdKSB7CiAgICAgICAgICAgICAgIHRlbXAgPSBhcnJbal07CiAgICAgICAgICAgICAgIGFycltqXSA9IGFycltqICsgMV07CiAgICAgICAgICAgICAgIGFycltqICsgMV0gPSB0ZW1wOwogICAgICAgICAgIH0KICAgICAgIH0KICAgfQp9CiAKdm9pZCBvcHRpbWl6ZWQoaW50IGFycltdLCBpbnQgbikgewogICBpbnQgZmxhZyA9IDA7CiAgIGZvciAoaSA9IDA7IGkgPCBuIC0gMTsgaSsrKSB7CiAgICAgICBmbGFnID0gMDsKICAgICAgIGZvciAoaiA9IDA7IGogPCBuIC0gaSAtIDE7IGorKykgewogICAgICAgICAgIGlmIChhcnJbal0gPiBhcnJbaiArIDFdKSB7CiAgICAgICAgICAgICAgIHRlbXAgPSBhcnJbal07CiAgICAgICAgICAgICAgIGFycltqXSA9IGFycltqICsgMV07CiAgICAgICAgICAgICAgIGFycltqICsgMV0gPSB0ZW1wOwogICAgICAgICAgICAgICBmbGFnID0gMTsKICAgICAgICAgICB9CiAgICAgICB9CiAgICAgICBpZiAoZmxhZyA9PSAwKSB7CiAgICAgICAgICAgYnJlYWs7CiAgICAgICB9CiAgIH0KfQogCmludCBtYWluKCkgewogICBpbnQgbiwgY2hvaWNlLCB0MSwgdDIsIHRjOwogICBzdHJ1Y3QgdGltZXZhbCB0dDsKICAgc3RydWN0IHRpbWV6b25lIHR6OwogICBwcmludGYoIkVudGVyIHRoZSBzaXplOi0gXG4iKTsKICAgc2NhbmYoIiVkIiwgJm4pOwogICBpbnQgYXJyW25dOwogICBwcmludGYoIkVudGVyICVkIGVsZW1lbnRzOi0gXG4iLCBuKTsKICAgZm9yIChpID0gMDsgaSA8IG47IGkrKykgewogICAgICAgc2NhbmYoIiVkIiwgJmFycltpXSk7CiAgIH0KICAgcHJpbnRmKCJcblNlbGVjdCB0eXBlIG9mIEJ1YmJsZSBTb3J0XG4xOi0gU2ltcGxlXG4yOi0gU2VtaSBPcHRpbWl6ZWRcbjM6LSBPcHRpbWl6ZWRcbiAiKTsKICAgc2NhbmYoIiVkIiwgJmNob2ljZSk7CiAKICAgc3dpdGNoKGNob2ljZSl7CiAgICAgICBjYXNlIDE6CiAgICAgICBnZXR0aW1lb2ZkYXkoJnR0LCZ0eik7CiAgICAgICB0MT10dC50dl91c2VjOwogICAgICAgc2ltcGxlKGFycixuKTsKICAgICAgIGdldHRpbWVvZmRheSgmdHQsJnR6KTsKICAgICAgIHQyPXR0LnR2X3VzZWM7CiAgICAgICBicmVhazsKICAgICAgIGNhc2UgMjoKICAgICAgIGdldHRpbWVvZmRheSgmdHQsJnR6KTsKICAgICAgIHQxPXR0LnR2X3VzZWM7CiAgICAgICBzZW1pKGFycixuKTsKICAgICAgIGdldHRpbWVvZmRheSgmdHQsJnR6KTsKICAgICAgIHQyPXR0LnR2X3VzZWM7CiAgICAgICBicmVhazsKICAgICAgIGNhc2UgMzoKICAgICAgIGdldHRpbWVvZmRheSgmdHQsJnR6KTsKICAgICAgIHQxPXR0LnR2X3VzZWM7CiAgICAgICBvcHRpbWl6ZWQoYXJyLG4pOwogICAgICAgZ2V0dGltZW9mZGF5KCZ0dCwmdHopOwogICAgICAgdDI9dHQudHZfdXNlYzsKICAgICAgIGJyZWFrOwogICAgICAgZGVmYXVsdDoKICAgICAgIHByaW50ZigiXG4gSW52YWxpZCBDaG9pY2VcbiIpOwogICB9CiAgIHByaW50ZigiXG5Tb3J0ZWQgQXJyYXlcbiIpOwogICBmb3IgKGkgPSAwOyBpIDwgbjsgaSsrKSB7CiAgICAgICBpZiAoaSA9PSBuIC0gMSkgewogICAgICAgICAgIHByaW50ZigiJWQiLCBhcnJbaV0pOwogICAgICAgfSBlbHNlIHsKICAgICAgICAgICBwcmludGYoIiVkLCAiLCBhcnJbaV0pOwogICAgICAgfQogICB9CiAgIHRjID0gdDIgLSB0MTsKICAgcHJpbnRmKCJcblRpbWUgQ29tcGxleGl0eSA9ICVkXG4iLCB0Yyk7CiAgIHJldHVybiAwOyB9