January 26, 2021, 10:49:04 AM

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

#### BlitzBot

• Jr. Member
• Posts: 1
##### [bmx] Top-down merge sort for arrays by Pineapple [ 1+ years ago ]
« on: June 29, 2017, 12:28:38 AM »
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