#include <stdio.h>
/**
* Swaps two integer values in place using pointers.
*/
static inline void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
/**
* Prints the elements of an array formatted on a single line.
*/
void print_array(const int arr[], size_t size) {
for (size_t i = 0; i < size; i++) {
printf("%d%s", arr[i], (i == size - 1) ? "" : " ");
}
printf("\n");
}
/**
* Sorts an array in non-decreasing order using Gnome Sort.
*
* Algorithm Logic (Single Loop):
* - Starts at index 0 and advances as long as elements are in correct order.
* - When an out-of-order adjacent pair is encountered, it swaps them and
* steps back one position to ensure the swapped element is correctly
* placed relative to preceding elements.
* - Time Complexity: O(N) best case (already sorted), O(N^2) worst case.
* - Space Complexity: O(1) auxiliary space.
*/
void gnome_sort(int arr[], size_t size) {
size_t pos = 0;
while (pos < size) {
// Move forward if at the beginning or if the current element pair is sorted
if (pos == 0 || arr[pos] >= arr[pos - 1]) {
pos++;
} else {
// Swap out-of-order elements and step backward to verify order
swap(&arr[pos], &arr[pos - 1]);
pos--;
}
}
}
int main(void) {
int numbers[] = {42, -5, 12, 0, 89, -18, 33, 7};
size_t size = sizeof(numbers) / sizeof(numbers[0]);
printf("Original array:\n");
print_array(numbers, size);
gnome_sort(numbers, size);
printf("\nSorted array:\n");
print_array(numbers, size);
}
/*
run:
Original array:
42 -5 12 0 89 -18 33 7
Sorted array:
-18 -5 0 7 12 33 42 89
*/
