import scala.math.Ordering
object SingleLoopSortApp {
/**
* Sorts a mutable 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.
*
* @param arr The mutable array to be sorted in place.
* @tparam T Type constrained by the Ordering context bound.
*/
def singleLoopSort[T: Ordering](arr: Array[T]): Unit = {
val ord = Ordering[T]
import ord.mkOrderingOps // Enables concise comparison operators like >=
var pos = 0
val len = 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 += 1
} else {
// Swap out-of-order elements in place using a temporary variable
val temp = arr(pos)
arr(pos) = arr(pos - 1)
arr(pos - 1) = temp
pos -= 1
}
}
}
def main(args: Array[String]): Unit = {
val numbers = Array(42, -5, 12, 0, 89, -18, 33, 7)
println("Original array:")
println(numbers.mkString(" "))
singleLoopSort(numbers)
println("\nSorted array:")
println(numbers.mkString(" "))
}
}
/*
run:
Original array:
42 -5 12 0 89 -18 33 7
Sorted array:
-18 -5 0 7 12 33 42 89
*/
