Download code

Jump to: navigation, search

Back to Merge_sort_(Oz)

Download for Windows: zip

Download for UNIX: zip, tar.gz, tar.bz2

mergesort-tests.oz

 1 % The authors of this work have released all rights to it and placed it
 2 % in the public domain under the Creative Commons CC0 1.0 waiver
 3 % (http://creativecommons.org/publicdomain/zero/1.0/).
 4 % 
 5 % THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 6 % EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 7 % MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 8 % IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
 9 % CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
10 % TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
11 % SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
12 % 
13 % Retrieved from: http://en.literateprograms.org/Merge_sort_(Oz)?oldid=15970
14 
15 functor
16 import
17    Application
18    System
19    Mergesort
20 define
21     proc {TestSort F Order Testname S R}
22        Result
23     in
24        if
25           R == {F S Order}
26        then
27           Result = "passed"
28        else 
29           Result =  "failed"
30        end
31        {System.showInfo
32         {System.printName F} # " - " # Result # " - " # Testname # "."}
33     end
34     proc {TestNumericSort F}
35        Stimulus = [3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3]
36        Response = [1 1 2 3 3 3 4 5 5 5 6 7 8 9 9 9]
37     in
38        {TestSort F Value.'=<' "numeric sort" Stimulus Response}
39     end
40        proc {TestStableSort F}
41           Stimulus = ["bbb" "aaa" "ccc" "zzz" "fff"]
42           Response = ["bbb" "aaa" "ccc" "zzz" "fff"]
43        in
44           {TestSort F fun {$ X Y} {List.length X}=<{List.length Y} end
45            "stable sort" Stimulus Response}
46        end
47 in   
48    {TestNumericSort Mergesort.mergesort}
49    {TestStableSort Mergesort.mergesort}   
50    {TestNumericSort Mergesort.mergesortCustom}
51    {TestStableSort Mergesort.mergesortCustom}   
52    
53    {Application.exit 0}
54 end


hijacker
hijacker
hijacker
hijacker

mergesort.oz

 1 % The authors of this work have released all rights to it and placed it
 2 % in the public domain under the Creative Commons CC0 1.0 waiver
 3 % (http://creativecommons.org/publicdomain/zero/1.0/).
 4 % 
 5 % THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 6 % EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 7 % MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 8 % IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
 9 % CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
10 % TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
11 % SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
12 % 
13 % Retrieved from: http://en.literateprograms.org/Merge_sort_(Oz)?oldid=15970
14 
15 functor
16 export
17    Mergesort
18    MergesortCustom
19 define
20    fun {Mergesort Xs P}
21       case Xs
22       of nil then nil
23       [] [X] then [X]
24       else
25          Len Ys Zs
26       in
27          {List.length Xs Len}
28          {List.takeDrop Xs (Len div 2) Ys Zs}  % split the list in two
29          {List.merge {Mergesort Ys P} {Mergesort Zs P} P}
30       end
31    end
32 
33    fun {MergesortCustom Xs P}
34       fun {Split Xs}
35          fun {SplitRec Xs Ys Ws}
36             case Xs
37             of nil then {List.reverse Ws} # Ys
38             [] [_] then {List.reverse Ws} # Ys
39             [] _ | _ | Xss then
40                Y1 | Yss = Ys
41             in
42                {SplitRec Xss Yss (Y1 | Ws)}
43             end
44          end
45       in {SplitRec Xs Xs nil} end
46       fun {Merge Xs Ys}
47          case Xs # Ys
48          of nil # Ys then Ys
49          [] Xs # nil then Xs
50          [] ( X | Xss ) # ( Y | Yss) then
51             if {P X Y} then
52                X | {Merge Xss Ys}
53             else
54                Y | {Merge Xs Yss}
55             end
56          end
57       end
58       fun {Mergesort Xs}
59          case Xs
60          of nil then nil
61          [] [X] then [X]
62          else
63             Ys # Zs = {Split Xs}
64          in
65             {Merge {Mergesort Ys} {Mergesort Zs}}
66          end
67       end
68    in
69       {Mergesort Xs}
70    end
71 end


hijacker
hijacker
hijacker
hijacker