Example: Gnome Sort Implementation in C

// Gnome Sort Implementation
#include <stdio.h>

// Function to swap two elements
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Function to implement Gnome Sort
void gnomeSort(int arr[], int n) {
    int index = 0; // Start at the beginning of the array

    while (index < n) {
        // Step 1: If we are at the beginning of the array,
        // or the current element is greater than or equal to the previous element,
        // it means elements are in order (or we can't move back further).
        // So, we move one step forward.
        if (index == 0 || arr[index] >= arr[index - 1]) {
            index++;
        }
        // Step 2: If the current element is smaller than the previous element,
        // they are out of order. We need to swap them and move back
        // one step to re-check the swapped element with its new predecessor.
        else {
            swap(&arr[index], &arr[index - 1]);
            index--; // Move back to re-check
        }
    }
}

// Function to print an array
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    // Step 1: Define an unsorted array
    int arr[] = {34, 12, 56, 2, 89, 7};
    int n = sizeof(arr) / sizeof(arr[0]); // Calculate the size of the array

    // Step 2: Print the original array
    printf("Original array: ");
    printArray(arr, n);

    // Step 3: Apply Gnome Sort
    gnomeSort(arr, n);

    // Step 4: Print the sorted array
    printf("Sorted array: ");
    printArray(arr, n);

    return 0;
}