//Time Complexity O(n^2)
//Space Complexity O(1)
//neighbours change places until a pass makes no swaps:
//the largest element "bubbles up" to the end on every pass
void bubbleSort(int arr[], size_t count) {
for (size_t end = count; end > 1; end--) {
bool swapped = false;
for (size_t j = 1; j < end; j++) {
if (arr[j] < arr[j - 1]) {
int tmp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = tmp;
swapped = true;
}
}
if (!swapped) {
break;
}
}
}
void printArray(const char *name, const int arr[], size_t count) {
printf("%s is {", name);
for (size_t i = 0; i < count; i++) {
if (i > 0) {
printf(", ");
}
printf("%d", arr[i]);
}
printf("}\n");
}
int items[] = {4, 1, 5, 3, 2};
size_t count = sizeof items / sizeof items[0];
//the sort works in place: a copy keeps items as they are
int sortItems[5];
memcpy(sortItems, items, sizeof items);
bubbleSort(sortItems, count);
//sortItems is {1, 2, 3, 4, 5}
printArray("items", items, count);
printArray("sortItems", sortItems, count);