program SingleLoopSortProgram;
{$mode objfpc}{$H+}{$J-}
// Generic array type definition for standard dynamic integer arrays
type
TIntArray = array of Integer;
{ Reads and swaps two integer values in place using built-in system routines. }
procedure SwapValues(var A, B: Integer);
var
Temp: Integer;
begin
Temp := A;
A := B;
B := Temp;
end;
{ Prints all elements of a dynamic array on a single line. }
procedure PrintArray(const Arr: TIntArray);
var
I: Integer;
begin
for I := Low(Arr) to High(Arr) do
begin
Write(Arr[I]);
if I < High(Arr) then
Write(' ');
end;
WriteLn;
end;
{
Sorts a dynamic array in-place in non-decreasing order using Gnome Sort.
Algorithm Logic (Single Loop):
- Traverses the array using a single while loop index.
- Advances forward if adjacent elements are already in non-decreasing order.
- When an out-of-order adjacent pair is encountered, swaps the elements
and steps backward one index to verify order against previous items.
- Time Complexity: O(N) best case (already sorted), O(N^2) worst case.
- Space Complexity: O(1) auxiliary space.
}
procedure SingleLoopSort(var Arr: TIntArray);
var
Pos: Integer;
Len: Integer;
begin
Len := Length(Arr);
Pos := 0;
while Pos < Len do
begin
// Move forward if at the beginning or if the current pair is sorted
if (Pos = 0) or (Arr[Pos] >= Arr[Pos - 1]) then
Inc(Pos)
else
begin
// Swap adjacent out-of-order elements and step backward
SwapValues(Arr[Pos], Arr[Pos - 1]);
Dec(Pos);
end;
end;
end;
var
Numbers: TIntArray;
begin
// Initialize dynamic array with standard array literal syntax
Numbers := TIntArray.Create(42, -5, 12, 0, 89, -18, 33, 7);
WriteLn('Original array:');
PrintArray(Numbers);
SingleLoopSort(Numbers);
WriteLn;
WriteLn('Sorted array:');
PrintArray(Numbers);
end.
(*
run:
Original array:
42 -5 12 0 89 -18 33 7
Sorted array:
-18 -5 0 7 12 33 42 89
*)
