/*
 * sort.b:
 *	Shell and Quick sorting routines for the library
 *
 * This implementation Copyright (c) 2020-2021 Gordon Henderson
 *********************************************************************************
 */

SECTION "sort"

GET "libhdr.h"
GET "sort.h"

/*
 * bubbleSort:
 *	The worlds worst sort. Do not use.
 *********************************************************************************
 */

LET bubbleSort (array, elements, compare) BE
{
  FOR i = 0 TO elements DO
  {
    FOR j = i TO elements DO
      IF compare (array!i, array!j) > 0 THEN
      {
	LET t    = array!i
	array!i := array!j
	array!j := t
      }
  }
}


/*
 * shellSort:
 *	Efficient BCPL shell sort - good for use when stack space is tight.
 *********************************************************************************
 */

LET shellSort (array, elements, compare) BE
{
  LET m = 1

  UNTIL m > elements DO
    m := m * 3 + 1  // Find first suitable value in the series:  1, 4, 13, 40, 121, 364, ...

  {
    m := m / 3
    FOR i = m TO elements DO
    {
      LET vi = array!i
      LET j  = i
      {
	LET k = j - m
        IF k < 0 | (compare (array!k, vi) < 0)
	  BREAK
        array!j := array!k
        j := k
      } REPEAT
      array!j := vi
    }
 } REPEATUNTIL m = 1

}


/*
 * quickSort:
 *	Faster than shellSort, but needs more stack
 *********************************************************************************
 */

AND quickSort (array, elements, compare) BE
  qSort (array, compare, 0, elements)

AND qSort (array, compare, left, right) BE
{
  LET i, j, x = ?, ?, ?

  i := left
  j := right
  x := array!((left + right) / 2)

  {
    WHILE ((compare (array!i, x) < 0) & (i < right))
      i := i + 1

    WHILE ((compare (array!j, x) > 0) & (j > left))
      j := j - 1

    IF i <= j THEN
    {
      LET    t = array!i
      array!i := array!j
      array!j := t
      i := i + 1
      j := j - 1
     }

  } REPEATWHILE i <= j

  IF left < j
     qSort (array, compare, left, j)
  
  IF i < right
     qSort (array, compare, i, right)
}