# HG changeset patch
# User Franz Glasner <fzglas.hg@dom66.de>
# Date 1729960537 -7200
# Node ID 11f3101c19805242b3b6c999ab6c6a8612fac85e
# Parent  aead7cf1cb9a8c1471ea7cc3dd70404be72459e6
farray.sh: Implemented plain Insertionsort.

Using the optimized algorithm already used in Shell sort, just without manx
gaps and using only the fixed last step 1.

diff -r aead7cf1cb9a -r 11f3101c1980 share/local-bsdtools/farray.sh
--- a/share/local-bsdtools/farray.sh	Sat Oct 26 14:09:47 2024 +0200
+++ b/share/local-bsdtools/farray.sh	Sat Oct 26 18:35:37 2024 +0200
@@ -1628,7 +1628,7 @@
     _farr_array_get_meta "$@"
 
     # XXX TBD: Select a method depenting on `__farr_len`.
-    _farr_array_gnomesort
+    _farr_array_insertionsort
 }
 
 
@@ -1695,6 +1695,66 @@
 
 
 #:
+#: Sort an array using Insertion Sort.
+#:
+#: Args:
+#:   $1: The array to sort to
+#:
+#: See Also:
+#:   `_farr_array_gnomesort`
+#:
+farray_insertionsort() {
+    local __farr_name
+
+    local __farr_token __farr_gvrname __farr_len \
+          __farr_pos __farr_val __farr_val_1
+
+    _farr_array_get_meta "$@"
+
+    _farr_array_insertionsort
+}
+
+
+#:
+#: Internal sort implementation using Insertion Sort.
+#:
+#: Stable: yes
+#:
+#: This is a very simple stable sort (a variant of insertion sort).
+#:
+#: See: https://en.wikipedia.org/wiki/Insertion_sort
+#:
+#: Input (Globals):
+#:   All the "Output (Globals)" from `farr_array_get_meta`:
+#:   __farr_name, __farr_token, __farr_gvrname and __farr_len.
+#:   These variables are declared local in this function but the shell
+#:   initializes them from the same variables in the nearest dynamic scope.
+#:   So they are really input variables and not also output variables.
+#:
+_farr_array_insertionsort() {
+
+    local __farr_name __farr_token __farr_gvrname __farr_len \
+          __farr_i __farr_j __farr_tmpitem __farr_tmpprevitem
+
+    __farr_i=2
+    while [ "${__farr_i}" -le "${__farr_len}" ]; do
+        # Save a[i] in temp and make a hole at position i
+        eval __farr_tmpitem=\"\$\{"${__farr_gvrname}"_"${__farr_i}"\}\"
+        __farr_j="${__farr_i}"
+        while [ "${__farr_j}" -gt 1 ]; do
+            eval __farr_tmpprevitem=\"\$\{"${__farr_gvrname}"_$((__farr_j - 1))\}\"
+            [ "${__farr_tmpprevitem}" = "${__farr_tmpitem}" ] || [ "${__farr_tmpprevitem}" '<' "${__farr_tmpitem}" ] && break
+            setvar "${__farr_gvrname}"_"${__farr_j}" "${__farr_tmpprevitem}"
+            __farr_j=$((__farr_j - 1))
+        done
+        # Put temp (the original a[i]) in its correct location
+        setvar "${__farr_gvrname}"_"${__farr_j}" "${__farr_tmpitem}"
+        __farr_i=$((__farr_i + 1))
+    done
+}
+
+
+#:
 #: Sort an array using Shell Sort.
 #:
 #: Args:
diff -r aead7cf1cb9a -r 11f3101c1980 tests/farray-array.t
--- a/tests/farray-array.t	Sat Oct 26 14:09:47 2024 +0200
+++ b/tests/farray-array.t	Sat Oct 26 18:35:37 2024 +0200
@@ -1397,6 +1397,19 @@
   $ check_no_array_artifacts
 
   $ farray_create TEST 5 3 2 4
+  $ farray_insertionsort TEST
+  $ check_array_is_sorted "$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
+
+  $ farray_create TEST 5 3 2 4
   $ farray_heapsort TEST
   $ check_array_is_sorted "$TEST"
   $ farray_debug TEST
@@ -1438,6 +1451,14 @@
   $ farray_splice "" TEST 1 "" UNSORTED
   $ check_array_is_sorted "$TEST"
   [1]
+  $ farray_insertionsort TEST
+  $ check_array_is_sorted "$TEST"
+  $ farray_release TEST
+
+  $ farray_create TEST
+  $ farray_splice "" TEST 1 "" UNSORTED
+  $ check_array_is_sorted "$TEST"
+  [1]
   $ farray_shellsort TEST
   $ check_array_is_sorted "$TEST"
   $ farray_release TEST
@@ -1945,5 +1966,3 @@
 =========
 
   $ check_no_local_artifacts
-
-  $ set
diff -r aead7cf1cb9a -r 11f3101c1980 tests/sort-perf/sort-perf.sh
--- a/tests/sort-perf/sort-perf.sh	Sat Oct 26 14:09:47 2024 +0200
+++ b/tests/sort-perf/sort-perf.sh	Sat Oct 26 18:35:37 2024 +0200
@@ -50,6 +50,20 @@
 	echo "===> SKIPPED: Gnome Sort with ${1} items"
     fi
 
+
+    if [ "${1}" -le 2000 ]; then
+	farray_create TEST
+	farray_splice "" TEST 1 "" UNSORTED
+	echo "===> Insertion Sort with ${1} items"
+	get_ts
+	farray_insertionsort TEST
+	get_ts
+	check_array_is_sorted "$TEST" || fatal "sort failed"
+	farray_release TEST
+    else
+	echo "===> SKIPPED: Insertion Sort with ${1} items"
+    fi    
+
     if [ "${1}" -le 50000 ]; then
 	farray_create TEST
 	farray_splice "" TEST 1 "" UNSORTED