January 26, 2021, 10:49:04 AM

Author Topic: [bmx] Top-down merge sort for arrays by Pineapple [ 1+ years ago ]  (Read 641 times)

Offline BlitzBot

  • Jr. Member
  • **
  • Posts: 1
Title : Top-down merge sort for arrays
Author : Pineapple
Posted : 1+ years ago

Description : Simply call MergeSortArray and everything will work out fine.

Code :
Code: BlitzMax
  1. '       --+-----------------------------------------------------------------------------------------+--
  2. '         |   This code was originally written by Sophie Kirschner (sophiek@pineapplemachine.com)   |  
  3. '         | It is released as public domain. Please don't interpret that as liberty to claim credit |  
  4. '         |   that isn't yours, or to sell this code when it could otherwise be obtained for free   |  
  5. '         |                because that would be a really shitty thing of you to do.                |
  6. '       --+-----------------------------------------------------------------------------------------+--
  7.  
  8. SuperStrict
  9.  
  10.  
  11.  
  12. ' Example Code
  13.  
  14. Rem
  15.  
  16. Framework brl.standardio
  17. Import brl.random
  18.  
  19. Const numnodes%=10
  20.  
  21. SeedRnd MilliSecs()
  22.  
  23. Type node
  24.         Field value%=Rand(0,99)
  25.         Method compare%(obj:Object)
  26.                 If value>node(obj).value Return 1
  27.                 Return -1
  28.         End Method
  29. End Type
  30.  
  31. Local nodearray:node[numnodes]
  32. For Local i%=0 Until numnodes
  33.         nodearray[i]=New node
  34. Next
  35.  
  36. Print "~nArray before sorting:"
  37. For Local i%=0 Until numnodes
  38.         Print nodearray[i].value
  39. Next
  40.  
  41. MergeSortArray(nodearray)
  42.  
  43. Print "~nArray after sorting:"
  44. For Local i%=0 Until numnodes
  45.         Print nodearray[i].value
  46. Next
  47.  
  48. EndRem
  49.  
  50.  
  51.  
  52. ' Top-down merge sort
  53. ' algorithm taken from: http://en.wikipedia.org/wiki/Merge_sort#Top-down_implementation
  54.  
  55. Function MergeSortArray(array:Object[],ascending%=True,comparefunc(o1:Object,o2:Object)=_Array_CompareObjects)
  56.         Local buffer:Object[]=New Object[array.length]
  57.         _MergeSortAtoA array,buffer,0,array.length,comparefunc,ascending
  58. End Function
  59.  
  60. Function _MergeSortAtoA(a:Object[],b:Object[],ll%,rr%,comparefunc(o1:Object,o2:Object),ascending%)
  61.         If rr-ll>=2 Then
  62.                 Local mm%=(ll+rr)/2
  63.                 _MergeSortAtoB a,b,ll,mm,comparefunc,ascending
  64.                 _MergeSortAtoB a,b,mm,rr,comparefunc,ascending
  65.                 _MergeSortMerge b,a,ll,mm,rr,comparefunc,ascending
  66.         EndIf
  67. End Function
  68.  
  69. Function _MergeSortAtoB(a:Object[],b:Object[],ll%,rr%,comparefunc(o1:Object,o2:Object),ascending%)
  70.         If rr-ll>=2 Then
  71.                 Local mm%=(ll+rr)/2
  72.                 _MergeSortAtoA a,b,ll,mm,comparefunc,ascending
  73.                 _MergeSortAtoA a,b,mm,rr,comparefunc,ascending
  74.                 _MergeSortMerge a,b,ll,mm,rr,comparefunc,ascending
  75.         ElseIf rr-ll=1
  76.                 b[ll]=a[ll]
  77.         EndIf
  78. End Function
  79.  
  80. Function _MergeSortMerge(a:Object[],b:Object[],ll%,mm%,rr%,comparefunc(o1:Object,o2:Object),ascending%)
  81.         Local l%=ll,r%=mm
  82.         Local comparetarg%=1-ascending*2
  83.         For Local o%=ll Until rr
  84.                 If r>=rr Or ((l<mm) And (comparefunc(a[l],a[r])=comparetarg)) Then ' a[l]<=a[r]
  85.                         b[o]=a[l]
  86.                         l:+1
  87.                 Else
  88.                         b[o]=a[r]
  89.                         r:+1
  90.                 EndIf
  91.         Next
  92. End Function
  93.  
  94. Function _Array_CompareObjects%(o1:Object,o2:Object)
  95.         Return o1.Compare(o2)
  96. End Function


Comments :


TaskMaster(Posted 1+ years ago)

 I have posted this before, and many of you probably know it already, but this is a great site showing the speed of the different sort methods.  With sample code.  The code is in Java, but is fairly easy to convert to BlitzMax.<a href="http://www.cs.ubc.ca/~harrison/Java/sorting-demo.html" target="_blank">http://www.cs.ubc.ca/~harrison/Java/sorting-demo.html[/url]


 

SimplePortal 2.3.6 © 2008-2014, SimplePortal