from typing import List, TypeVar
# Type variable constrained to types supporting comparison operations
T = TypeVar("T")
def single_loop_sort(data: List[T]) -> None:
"""
Sorts a list in-place in non-decreasing order using Gnome Sort.
Algorithm Logic (Single Loop):
- Advances through the list 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.
Args:
data: The list of comparable elements to be sorted in place.
"""
pos = 0
length = len(data)
while pos < length:
# Move forward if at index 0 or if adjacent pair is in correct order
if pos == 0 or data[pos] >= data[pos - 1]:
pos += 1
else:
# Swap adjacent out-of-order elements using Pythonic tuple unpacking
data[pos], data[pos - 1] = data[pos - 1], data[pos]
pos -= 1
def main() -> None:
"""Main function to demonstrate the single-loop sorting algorithm."""
numbers: List[int] = [42, -5, 12, 0, 89, -18, 33, 7]
print("Original array:")
print(*numbers)
single_loop_sort(numbers)
print("\nSorted array:")
print(*numbers)
if __name__ == "__main__":
main()
"""
run:
Original array:
42 -5 12 0 89 -18 33 7
Sorted array:
-18 -5 0 7 12 33 42 89
"""
