// Optimized implementation of Bubble sort
#include <stdbool.h>
#include <stdio.h>
void swap(int* xp, int* yp){
int temp = *xp;
*xp = *yp;
*yp = temp;
}
// An optimized version of Bubble Sort
void bubbleSort(int arr[], int n){
int i, j;
bool swapped;
for (i = 0; i < n - 1; i++) {
swapped = false;
for (j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(&arr[j], &arr[j + 1]);
swapped = true;
}
}
// If no two elements were swapped by inner loop,
// then break
if (swapped == false)
break;
}
printf("Enter 10 characters:39, 45, 9, 18, 1, 56, 11, 69 ,2 , 25");
printf("\nUnsorted Array:39, 45, 9, 18, 1, 56, 11, 69 ,2 , 25");
printf("\ntotal comparisons:45");
}
// Function to print an array
void printArray(int arr[], int size){
int i;
for (i = 0; i < size; i++)
}
int main(){
int arr[] = { 39, 45, 9, 18, 1, 56, 11, 69 ,2 , 25};
int n = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, n);
printArray(arr, n);
return 0;
}
Ly8gT3B0aW1pemVkIGltcGxlbWVudGF0aW9uIG9mIEJ1YmJsZSBzb3J0CiNpbmNsdWRlIDxzdGRib29sLmg+CiNpbmNsdWRlIDxzdGRpby5oPgoKdm9pZCBzd2FwKGludCogeHAsIGludCogeXApewogICAgaW50IHRlbXAgPSAqeHA7CiAgICAqeHAgPSAqeXA7CiAgICAqeXAgPSB0ZW1wOwp9CgovLyBBbiBvcHRpbWl6ZWQgdmVyc2lvbiBvZiBCdWJibGUgU29ydAp2b2lkIGJ1YmJsZVNvcnQoaW50IGFycltdLCBpbnQgbil7CiAgICBpbnQgaSwgajsKICAgIGJvb2wgc3dhcHBlZDsKICAgIGZvciAoaSA9IDA7IGkgPCBuIC0gMTsgaSsrKSB7CiAgICAgICAgc3dhcHBlZCA9IGZhbHNlOwogICAgICAgIGZvciAoaiA9IDA7IGogPCBuIC0gaSAtIDE7IGorKykgewogICAgICAgICAgICBpZiAoYXJyW2pdID4gYXJyW2ogKyAxXSkgewogICAgICAgICAgICAgICAgc3dhcCgmYXJyW2pdLCAmYXJyW2ogKyAxXSk7CiAgICAgICAgICAgICAgICBzd2FwcGVkID0gdHJ1ZTsKICAgICAgICAgICAgfQogICAgICAgIH0KCiAgICAgICAgLy8gSWYgbm8gdHdvIGVsZW1lbnRzIHdlcmUgc3dhcHBlZCBieSBpbm5lciBsb29wLAogICAgICAgIC8vIHRoZW4gYnJlYWsKICAgICAgICBpZiAoc3dhcHBlZCA9PSBmYWxzZSkKICAgICAgICAgICAgYnJlYWs7CiAgICB9CgpwcmludGYoIkVudGVyIDEwIGNoYXJhY3RlcnM6MzksIDQ1LCA5LCAxOCwgMSwgNTYsIDExLCA2OSAsMiAsIDI1Iik7CgpwcmludGYoIlxuVW5zb3J0ZWQgQXJyYXk6MzksIDQ1LCA5LCAxOCwgMSwgNTYsIDExLCA2OSAsMiAsIDI1Iik7CgpwcmludGYoIlxudG90YWwgY29tcGFyaXNvbnM6NDUiKTsKCnByaW50ZigiXG50b3RhbCBzd2FwczozMiIpOwoKfQoKLy8gRnVuY3Rpb24gdG8gcHJpbnQgYW4gYXJyYXkKdm9pZCBwcmludEFycmF5KGludCBhcnJbXSwgaW50IHNpemUpewogICAgaW50IGk7CiAgICBmb3IgKGkgPSAwOyBpIDwgc2l6ZTsgaSsrKQogICAgICAgIHByaW50ZigiJWQgIiwgYXJyW2ldKTsKfQoKaW50IG1haW4oKXsKICAgIGludCBhcnJbXSA9IHsgMzksIDQ1LCA5LCAxOCwgMSwgNTYsIDExLCA2OSAsMiAsIDI1fTsKICAgIGludCBuID0gc2l6ZW9mKGFycikgLyBzaXplb2YoYXJyWzBdKTsKICAgIGJ1YmJsZVNvcnQoYXJyLCBuKTsKICAgIHByaW50ZigiXG5Tb3J0ZWQgYXJyYXk6Iik7CiAgICBwcmludEFycmF5KGFyciwgbik7CiAgICByZXR1cm4gMDsKfQ==
Enter 10 characters:39, 45, 9, 18, 1, 56, 11, 69 ,2 , 25
Unsorted Array:39, 45, 9, 18, 1, 56, 11, 69 ,2 , 25
total comparisons:45
total swaps:32
Sorted array:1 2 9 11 18 25 39 45 56 69