# HG changeset patch # User Franz Glasner # Date 1729880944 -7200 # Node ID 84527b00d29ae9bcac5df6da2ce63be0a0aba0f1 # Parent 3f9b22ddacb8d3a7156bed50fbce2b0b4f35bafe farray.sh: Implement Heapsort in the "standard" implementation. BUGS: Performance here equals Shellsort. diff -r 3f9b22ddacb8 -r 84527b00d29a share/local-bsdtools/farray.sh --- a/share/local-bsdtools/farray.sh Thu Oct 24 11:44:35 2024 +0200 +++ b/share/local-bsdtools/farray.sh Fri Oct 25 20:29:04 2024 +0200 @@ -1792,6 +1792,119 @@ #: +#: Sort an array using Heapsort. +#: +#: Args: +#: $1: The array to sort to +#: +#: See Also: +#: `_farr_array_heapsort` +#: +farray_heapsort() { + local __farr_name + + local __farr_token __farr_gvrname __farr_len \ + __farr_pos __farr_val __farr_val_1 + + _farr_array_get_meta "$@" + + _farr_array_heapsort +} + + +#: +#: Internal sort implementation using Heapsort. +#: +#: Stable: no +#: +#: See: https://en.wikipedia.org/wiki/Heapsort +#: +#: Here the "standard" implementation is used. +#: +#: 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_heapsort() { + + local __farr_name __farr_token __farr_gvrname __farr_len \ + __farr_start __farr_end __farr_root __farr_childp1 \ + __farr_tmpitem __farr_rootitem __farr_childitem __farr_childp1item + + __farr_start=$(( (__farr_len / 2) + 1)) # aka: iParent(of the last element) + __farr_end=$((__farr_len + 1)) + while [ "${__farr_end}" -gt 2 ]; do +# echo "== WHILE: START: $__farr_start, END: $__farr_end" + if [ "${__farr_start}" -gt 1 ]; then +# echo "==== HEAP CONSTRUCTION" + # Heap construction + __farr_start=$((__farr_start - 1)) + else +# echo "==== HEAP EXTRACTION" + # Heap extraction + __farr_end=$((__farr_end - 1)) + # swap(a[end], a[1]) + eval __farr_tmpitem=\"\$\{"${__farr_gvrname}"_1\}\" + eval "${__farr_gvrname}"_1=\"\$\{"${__farr_gvrname}"_"${__farr_end}"\}\" + setvar "${__farr_gvrname}"_"${__farr_end}" "${__farr_tmpitem}" + fi +# echo "==== BEFORE: START: $__farr_start, END: $__farr_end" + #farray_debug "$__farr_name" + # The following is siftDown(a, start, end) + __farr_root="${__farr_start}" + eval __farr_rootitem=\"\$\{"${__farr_gvrname}"_"${__farr_root}"\}\" +# echo "==== NEW ROOT: ${__farr_root}, a[root]: ${__farr_rootitem}" + while [ $((2 * __farr_root)) -lt "${__farr_end}" ]; do + child=$((2 * __farr_root)) + eval __farr_childitem=\"\$\{"${__farr_gvrname}"_"${child}"\}\" +# echo "CHILD: ${child}, ROOT: ${__farr_root}, END: ${__farr_end}, a[child]: ${__farr_childitem}" + # If there is a right child and that child is greater + __farr_childp1=$((child + 1)) + if [ "${__farr_childp1}" -lt "${__farr_end}" ]; then + eval __farr_childp1item=\"\$\{"${__farr_gvrname}"_"${__farr_childp1}"\}\" +# echo "===== a[child+1]: ${__farr_childp1item}" + if [ "${__farr_childitem}" '<' "${__farr_childp1item}" ]; then + #child=$((child + 1)) + child="${__farr_childp1}" + eval __farr_childitem=\"\$\{"${__farr_gvrname}"_"${child}"\}\" +# echo "====== INCR CHILD TO: $child" + fi + fi +# echo "====== a[root]: ${__farr_rootitem}, a[child]: ${__farr_childitem}" + if [ "${__farr_rootitem}" '<' "${__farr_childitem}" ]; then +# echo "====== SWAPPING: root: ${__farr_root}, child: ${child}, a[root]: $__farr_rootitem, a[child]: $__farr_childitem" + # swap(a[root], a[child]) + setvar "${__farr_gvrname}"_"${__farr_root}" "${__farr_childitem}" + setvar "${__farr_gvrname}"_"${child}" "${__farr_rootitem}" + # repeat to continue sifting down + __farr_root="${child}" + + # + # XXX FIXME: Why are these lines not needed? + # + # This gives the *wrong* result + #__farr_rootitem="${__farr_childitem}" + # This does not harm but seems not needed + #eval __farr_rootitem=\"\$\{"${__farr_gvrname}"_"${__farr_root}"\}\" + else + # return to outer loop +# echo "====== BREAK" + break + fi +# echo "====== LOOPING ..." + done +# echo "==== AFTER: START: $__farr_start, END: $__farr_end" + #farray_debug "$__farr_name" + done + + +} + + +#: #: Try to find the index of a given value in an existing array. #: #: It assumes that the array is sorted and uses a binary search algorithm diff -r 3f9b22ddacb8 -r 84527b00d29a tests/farray-array.t --- a/tests/farray-array.t Thu Oct 24 11:44:35 2024 +0200 +++ b/tests/farray-array.t Fri Oct 25 20:29:04 2024 +0200 @@ -1396,6 +1396,19 @@ $ 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 + 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 + $ create_random_array UNSORTED 1000 $ check_array_is_sorted "$UNSORTED" [1] @@ -1416,6 +1429,26 @@ $ check_array_is_sorted "$TEST" $ farray_release TEST + $ farray_create TEST + $ farray_splice "" TEST 1 "" UNSORTED + $ check_array_is_sorted "$TEST" + [1] + $ farray_heapsort TEST + $ check_array_is_sorted "$TEST" + $ farray_release TEST + + $ farray_release UNSORTED + $ check_no_array_artifacts + +# Extra checks for Heapsort + + $ farray_create UNSORTED '189548216' '544226607' '690563482' '224884577' '843524724' '922143089' '917031008' '602352555' '397442038' '350475285' + $ farray_create TEST + $ farray_splice "" TEST 1 "" UNSORTED + $ farray_heapsort TEST + $ check_array_is_sorted "$TEST" + + $ farray_release TEST $ farray_release UNSORTED $ check_no_array_artifacts diff -r 3f9b22ddacb8 -r 84527b00d29a tests/sort-perf/sort-perf.sh --- a/tests/sort-perf/sort-perf.sh Thu Oct 24 11:44:35 2024 +0200 +++ b/tests/sort-perf/sort-perf.sh Fri Oct 25 20:29:04 2024 +0200 @@ -12,6 +12,11 @@ . "${_p_datadir}/farray.sh" +fatal() { + exit 1 "ERROR: $@" 1>&2 +} + + get_ts() { /usr/bin/ntpq -c "rv 0 clock" localhost } @@ -39,23 +44,34 @@ get_ts farray_gnomesort TEST get_ts + check_array_is_sorted "$TEST" || fatal "sort failed" farray_release TEST else echo "===> SKIPPED: Gnome Sort with ${1} items" fi - if [ "${1}" -le 20000 ]; then + if [ "${1}" -le 50000 ]; then farray_create TEST farray_splice "" TEST 1 "" UNSORTED echo "===> Shell Sort with ${1} items" get_ts farray_shellsort TEST get_ts + check_array_is_sorted "$TEST" || fatal "sort failed" farray_release TEST else echo "===> SKIPPED: Shell Sort with ${1} items" fi + farray_create TEST + farray_splice "" TEST 1 "" UNSORTED + echo "===> Heap Sort with ${1} items" + get_ts + farray_heapsort TEST + get_ts + check_array_is_sorted "$TEST" || fatal "sort failed" + farray_release TEST + farray_release UNSORTED }