Download code

Jump to: navigation, search

Back to Insertion_sort_(Standard_ML)

Download for Windows: zip

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

insertion_sort_immutable.sml

 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/Insertion_sort_(Standard_ML)?oldid=19165
14 *)
15 
16 fun insertion_sort _ [] = []
17   | insertion_sort cmp (x::xs) = insert cmp x (insertion_sort cmp xs)
18 and insert _ x [] = [x]
19   | insert cmp x (l as y::ys) =
20       case cmp (x, y) of GREATER => y :: insert cmp x ys
21                        | _       => x :: l
22 
23 fun is_ordered _ [] = true
24   | is_ordered _ [y] = true
25   | is_ordered cmp (y::ys) = is_ordered cmp ys andalso cmp(y, hd ys) <> GREATER
26 
27 fun random_list _ 0 = []
28   | random_list r n = (Random.randInt(r))::(random_list r (n-1));
29 
30 let
31     val r = Random.rand(12,35)
32     val cmp = Int.compare
33     fun test n = is_ordered cmp (insertion_sort cmp (random_list r n))
34 in
35     if test 1 andalso test 100 andalso test 10000 then
36         print "Success\n"
37     else
38 	print "Error\n"
39 end


hijacker
hijacker
hijacker
hijacker

insertion_sort_mutable.sml

 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/Insertion_sort_(Standard_ML)?oldid=19165
14 *)
15 
16 fun insertion_sort cmp a =
17   Array.appi (fn (i, v) =>
18     (* Insert v into the sorted sublist *)
19     let
20       val j = ref (i - 1)
21     in
22       while !j >= 0 andalso cmp (Array.sub (a, !j), v) = GREATER do (
23         Array.update (a, !j + 1, Array.sub (a, !j));
24         j := !j - 1
25       );
26       Array.update (a, !j + 1, v)
27     end@ text
28 )
29     a
30 
31 
32 fun is_ordered _ [] = true
33   | is_ordered _ [y] = true
34   | is_ordered cmp (y::ys) = is_ordered cmp ys andalso cmp(y, hd ys) <> GREATER
35 
36 fun random_list _ 0 = []
37   | random_list r n = (Random.randInt(r))::(random_list r (n-1));
38 
39 let
40     val r = Random.rand(12,35)
41     val cmp = Int.compare
42     fun toList array = Array.foldr op:: [] array
43     fun test n = let val a = Array.fromList (random_list r n) in
44 		     (insertion_sort cmp a;
45 		      is_ordered cmp (toList a))
46 		 end
47 in
48     if test 1 andalso test 100 andalso test 10000 then
49         print "Success\n"
50     else
51 	print "Error\n"
52 end


hijacker
hijacker
hijacker
hijacker