Anonymous

// Bubble Sort Benchmark! v1.0 by d00d
// Heap Sort Mod by Phubra
// 10/08/08

DEFINE INT T_START 0
DEFINE INT T_END 0
DEFINE DOUBLE T_CONVERT 0.0
DEFINE INT START 10

PRINT_TEXT "starting bubblesort benchmark"

FOR i 0 10 1

  DEFINE_GLOBAL ARRAYLIST MyAL 0

  Init MyAL 1 START

  GET_TIME T_START

  HeapSort MyAL 1 MyAL

  GET_TIME T_END
  
  //T_CONVERT =  #D0 + T_END - T_START
  //T_CONVERT = T_CONVERT / #D10000000
  T_CONVERT = T_END - T_START
  T_CONVERT = T_CONVERT / #D10000000
  PRINT_TEXT "<&START&> element bubble sort took <&T_CONVERT&> seconds"
  
  START = START + #I25
  T_START = 0
  T_END = 0
  T_CONVERT = #D0.0

  DELETE_GLOBAL MyAL
  
NEXT

PRINT_TEXT "HeapSort benchmark complete"
  
END_SCRIPT

FUNCTION Init 1 _Count
  DEFINE INT r_Int 0

  FOR i 0 "<&_Count&>" 1
    GET_RAND r_Int -2147483647 2147483646

    //MyAL.PUSH "#i<&r_Int&>"
    MyAL.PUSH r_Int
  NEXT

RETURN MyAL

FUNCTION HeapSort 1 _Object 
  DEFINE INT _Count 0
  DEFINE INT _End 0
  _Count = _Object.Count.CLONE

  Heapify _Object 2 _Object _Count  
  _End = _Count - 1
  WHILE _End > 0
    Swap _Object 3 _Object _End 0
    _End = _End - 1
    SiftDown _Object 3 _Object 0 _End
  WEND
RETURN _Object

FUNCTION Heapify 2 _Object _Count
  DEFINE INT _Start 0
  DEFINE INT _CountSub1 0

  _Start = _Count - 2
  _Start = _Start / 2
  _CountSub1 = _Count - 1

  FOR i "<&_Start&>" -1 -1
    SiftDown _Object 3 _Object i _CountSub1
  NEXT
RETURN _Object

FUNCTION SiftDown 3 _Object _Start _End
  DEFINE INT _Root 0
  DEFINE INT _RootCheck 0
  DEFINE INT _Child 0
  DEFINE INT X 0

  _Root = _Start.CLONE
  _RootCheck = _Root * 2
  _RootCheck = _RootCheck + 1

  WHILE _RootCheck <= _End
    _Child = _Root * 2
    _Child = _Child + 1
    X = _Child + 1
    IF X <= _End
      IF _Object._Child < _Object.X
        _Child = _Child + 1
      ENDIF
    ENDIF

    IF _Object._Root < _Object._Child
      Swap _Object 3 _Object _Child _Root
      _Root = _Child.CLONE
      _RootCheck = _Child * 2
      _RootCheck = _RootCheck + 1
    ELSE
      RETURN _Object
    ENDIF
  WEND  
RETURN _Object

FUNCTION Swap 3 _Object _X _Y
      DEFINE INT TMP 0

      TMP = _Object._X.CLONE
      _Object._X = _Object._Y.CLONE
      _Object._Y = TMP.CLONE
RETURN _Object