/**
* Sorts a generic array in-place in non-decreasing order using Gnome Sort.
*
* Algorithm Logic (Single Loop):
* - Advances through the array using a single while loop index.
* - Moves forward when adjacent elements are in correct relative order.
* - When an out-of-order adjacent pair is encountered, swaps the elements
* and steps backward one index to verify order against preceding items.
* - Time Complexity: O(N) best case (already sorted), O(N^2) worst case.
* - Space Complexity: O(1) auxiliary space.
*
* @template T - The element type, which must be comparable (primitive number, string, etc.).
* @param {T[]} arr - The mutable array to be sorted in place.
* @returns {T[]} The same array reference, sorted.
*/
function singleLoopSort<T extends number | string | boolean>(arr: T[]): T[] {
let pos: number = 0;
const len: number = arr.length;
while (pos < len) {
// Move forward if at index 0 or if adjacent pair is in correct order
if (pos === 0 || arr[pos] >= arr[pos - 1]) {
pos++;
} else {
// Swap adjacent out-of-order elements using tuple destructuring assignment
[arr[pos], arr[pos - 1]] = [arr[pos - 1], arr[pos]];
pos--;
}
}
return arr;
}
/**
* Main
*/
function main(): void {
const numbers: number[] = [42, -5, 12, 0, 89, -18, 33, 7];
console.log("Original array:");
console.log(numbers.join(" "));
singleLoopSort(numbers);
console.log("\nSorted array:");
console.log(numbers.join(" "));
}
main();
/*
run:
Original array:
42 -5 12 0 89 -18 33 7
Sorted array:
-18 -5 0 7 12 33 42 89
*/
