' ** Several sorting routines
' ** Converted to uBasic, J.L. Bezemer - 2013,2015
' **
' ** Taken from various Rosetta code examples
' ** http://rosettacode.org

PRINT "Shellsort:"
  n = FUNC (_InitArray)
  PROC _ShowArray (n)
  PROC _Shellsort (n)
  PROC _ShowArray (n)
PRINT

PRINT "Combsort:"
  n = FUNC (_InitArray)
  PROC _ShowArray (n)
  PROC _Combsort (n)
  PROC _ShowArray (n)
PRINT

PRINT "Insertion sort:"
  n = FUNC (_InitArray)
  PROC _ShowArray (n)
  PROC _Insertionsort (n)
  PROC _ShowArray (n)
PRINT

PRINT "Selection sort:"
  n = FUNC (_InitArray)
  PROC _ShowArray (n)
  PROC _Selectionsort (n)
  PROC _ShowArray (n)
PRINT

PRINT "Bubble sort:"
  n = FUNC (_InitArray)
  PROC _ShowArray (n)
  PROC _Bubblesort (n)
  PROC _ShowArray (n)
PRINT

PRINT "Gnome sort:"
  n = FUNC (_InitArray)
  PROC _ShowArray (n)
  PROC _Gnomesort (n)
  PROC _ShowArray (n)
PRINT

PRINT "Cocktail sort:"
  n = FUNC (_InitArray)
  PROC _ShowArray (n)
  PROC _Cocktailsort (n)
  PROC _ShowArray (n)
PRINT

PRINT "Circle sort:"
  n = FUNC (_InitArray)
  PROC _ShowArray (n)
  PROC _Circlesort (n)
  PROC _ShowArray (n)
PRINT

END


_Shellsort PARAM (1)                   ' Shellsort subroutine
  h = a@

  DO WHILE h
    h = h / 2
    FOR i = h TO a@ - 1
      k = @(i)
      j = i
      DO WHILE (j > h-1) * (k < @(ABS(j - h)))
        @(j) = @(j - h)
        j = j - h
      LOOP
      @(j) = k
    NEXT
  LOOP
RETURN


_Combsort PARAM (1)                    ' Combsort subroutine
  g = a@
  p = 1

  DO WHILE (g > 1) + p

    g = (g * 10) / 13

    IF (g = 9) + (g = 10) THEN
      g = 11
    ENDIF

    IF g < 1 THEN
      g = 1
    ENDIF

    p = 0
    i = 0
    j = g

    DO WHILE j < a@
      IF @(i) > @(j) THEN
        PUSH @(i)
        @(i) = @(j)
        @(j) = POP()
        p = 1
      ENDIF

      i = i + 1
      j = j + 1
    LOOP
  LOOP
RETURN


_Insertionsort PARAM (1)               ' Insertion sort
  FOR i = 1 TO a@-1
    t = @(i)
    j = i
    DO WHILE (j>0) * (t < @(ABS(j-1)))
        @(j) = @(j-1)
        j = j - 1
    LOOP
    @(j) = t
  NEXT
RETURN


_Selectionsort PARAM (1)               ' Selection sort
  FOR i = 0 TO a@-1
    l = i

    FOR j = i TO a@-1
      IF @(j) < @(l) THEN
        l = j
      ENDIF
    NEXT

    IF i # l THEN
      PUSH @(i)
      @(i) = @(l)
      @(l) = POP()
    ENDIF

  NEXT
RETURN


_Bubblesort PARAM(1)                   ' Bubble sort
  DO
    l = 0
    FOR i = 1 TO a@-1
      IF @(i-1) > @(i) THEN
        PUSH @(i-1)
        @(i-1) = @(i)
        @(i) = POP()
        l = i
      ENDIF
    NEXT
    a@ = l
    UNTIL l = 0
  LOOP

RETURN


_Gnomesort PARAM (1)                   ' Gnome sort
  i=1
  j=2

  DO WHILE i < a@
    IF @(i-1) > @(i) THEN
      PUSH @(i-1)
      @(i-1) = @(i)
      @(i) = POP()
      i = i - 1
      IF i THEN
        CONTINUE
      ENDIF
    ENDIF
    i = j
    j = j + 1
  LOOP
RETURN


_Cocktailsort PARAM (1)                ' Cocktail sort
  t = 0

  DO WHILE t = 0
    t = 1
    FOR i=1 TO a@-1
      IF @(i) < @(i-1) THEN
        PUSH @(i-1)
        @(i-1) = @(i)
        @(i) = POP()
        t = 0
      ENDIF
    NEXT

    IF t THEN
      BREAK
    ENDIF

    t = 1
    FOR i=a@-1 TO 1 STEP -1
      IF @(i) < @(i-1) THEN
        PUSH @(i-1)
        @(i-1) = @(i)
        @(i) = POP()
        t = 0
      ENDIF
    NEXT
  LOOP
RETURN


_Circle PARAM (3)
  IF a@ = b@ THEN RETURN (c@)

  LOCAL (3)
  d@ = a@
  e@ = b@
  f@ = (b@-a@)/2

  DO WHILE a@ < b@
    IF @(a@) > @(b@) THEN
       PUSH @(a@)
       @(a@) = @(b@)
       @(b@) = POP()
       c@ = c@ + 1
    ENDIF
    a@ = a@ + 1
    b@ = b@ - 1
  LOOP

  IF a@ = b@ THEN
     IF @(a@) > @(b@+1) THEN
        PUSH @(a@)
        @(a@) = @(b@+1)
        @(b@+1) = POP()
        c@ = c@ + 1
     ENDIF
  ENDIF

  c@ = FUNC (_Circle (d@, d@+f@, c@))
  c@ = FUNC (_Circle (d@+f@+1, e@, c@))
RETURN (c@)


_Circlesort PARAM(1)                   ' Circle sort

  DO WHILE FUNC (_Circle (0, a@-1, 0))
  LOOP

RETURN


_InitArray                             ' Init example array
  PUSH 4, 65, 2, -31, 0, 99, 2, 83, 782, 1

  FOR i = 0 TO 9
    @(i) = POP()
  NEXT

RETURN (i)


_ShowArray PARAM (1)                   ' Show array subroutine
  FOR i = 0 TO a@-1
    PRINT @(i),
  NEXT

  PRINT
RETURN
