# HG changeset patch
# User Franz Glasner <fzglas.hg@dom66.de>
# Date 1728505786 -7200
# Node ID 6787e216285e6601c8d487000b558f09f64ea5a4
# Parent  7e2279d6db0f5b568b0b57feb788d1bb879d9d9d
farray.sh: Implement the first simple sorting algorithm using Gnome Sort

diff -r 7e2279d6db0f -r 6787e216285e share/local-bsdtools/farray.sh
--- a/share/local-bsdtools/farray.sh	Tue Oct 08 18:11:24 2024 +0200
+++ b/share/local-bsdtools/farray.sh	Wed Oct 09 22:29:46 2024 +0200
@@ -1411,6 +1411,46 @@
 
 
 #:
+#: Sort using Gnome Sort.
+#:
+#: This is a very simple stable sort (a variant of insertion sort).
+#:
+#: See: https://en.wikipedia.org/wiki/Gnome_sort
+#:
+#: Args:
+#:   $1: The array to sort to
+#:
+farray_sort() {
+    local __farr_name
+
+    local __farr_token __farr_gvrname __farr_len
+    local __farr_pos
+    local __farr_val __farr_val_1
+
+    _farr_array_get_meta "$@"
+
+    __farr_pos=1
+    while [ ${__farr_pos} -le "${__farr_len}" ]; do
+        if [ ${__farr_pos} -eq 1 ]; then
+            __farr_pos=$((__farr_pos + 1))
+        else
+            eval __farr_val=\"\$\{${__farr_gvrname}_${__farr_pos}\}\"
+            eval __farr_val_1=\"\$\{${__farr_gvrname}_$((__farr_pos - 1))\}\"
+            # shellcheck disable=SC3012  # POSIX sh: lexicographical > undef
+            if [ \( "${__farr_val}" '>' "${__farr_val_1}" \) -o \( "${__farr_val}" '=' "${__farr_val_1}" \) ] ; then
+                __farr_pos=$((__farr_pos + 1))
+            else
+                # swap
+                eval ${__farr_gvrname}_${__farr_pos}=\"\$\{__farr_val_1\}\"
+                eval ${__farr_gvrname}_$((__farr_pos - 1))=\"\$\{__farr_val\}\"
+                __farr_pos=$((__farr_pos - 1))
+            fi
+        fi
+    done
+}
+
+
+#:
 #: Join all the elements in given array with a separator and put the result
 #: into a variable.
 #:
diff -r 7e2279d6db0f -r 6787e216285e tests/farray-array.t
--- a/tests/farray-array.t	Tue Oct 08 18:11:24 2024 +0200
+++ b/tests/farray-array.t	Wed Oct 09 22:29:46 2024 +0200
@@ -1250,6 +1250,22 @@
   $ check_no_array_artifacts
 
 
+Sort
+====
+
+  $ farray_create TEST 5 3 2 4
+  $ farray_sort TEST
+  $ farray_debug TEST
+  DEBUG: array `TEST' has length 4
+  DEBUG:   the items:
+  DEBUG:     1: `2'
+  DEBUG:     2: `3'
+  DEBUG:     3: `4'
+  DEBUG:     4: `5'
+  $ farray_release TEST
+  $ check_no_array_artifacts
+
+
 Generic Destruction
 ===================