Download code

Jump to: navigation, search

Back to Quicksort_(Erlang)

Download for Windows: zip

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

qsort.erl

 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/Quicksort_(Erlang)?oldid=6960
14 
15 -module(qsort).
16 -export([qsort1/1, qsort2/1, qsort3/1]).
17 
18 qsort1([]) ->
19     [];
20 qsort1([H | T]) -> 
21     qsort1([ X || X <- T, X < H ]) ++ [H] ++ qsort1([ X || X <- T, X >= H ]).
22 
23 qsort2([]) ->
24     [];
25 qsort2([H | T]) ->
26     {Less, Equal, Greater} = part(H, T, {[], [H], []}),
27     qsort2(Less) ++ Equal ++ qsort2(Greater).
28 
29 part(_, [], {L, E, G}) ->
30     {L, E, G};
31 part(X, [H | T], {L, E, G}) ->
32     if
33         H < X ->
34             part(X, T, {[H | L], E, G});
35         H > X ->
36             part(X, T, {L, E, [H | G]});
37         true ->
38             part(X, T, {L, [H | E], G})
39     end.
40 qsort3([]) ->
41     [];
42 qsort3([H | T]) ->
43     qsort3_acc([H | T], []).
44 
45 qsort3_acc([], Acc) ->
46     Acc;
47 qsort3_acc([H | T], Acc) ->
48     part_acc(H, T, {[], [H], []}, Acc).
49 
50 part_acc(_, [], {L, E, G}, Acc) ->
51     qsort3_acc(L, (E ++ qsort3_acc(G, Acc)));
52 part_acc(X, [H | T], {L, E, G}, Acc) ->
53     if
54         H < X ->
55             part_acc(X, T, {[H | L], E, G}, Acc);
56         H > X ->
57             part_acc(X, T, {L, E, [H | G]}, Acc);
58         true ->
59             part_acc(X, T, {L, [H | E], G}, Acc)
60     end.
61 


hijacker
hijacker
hijacker
hijacker

test_qsort.erl

 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/Quicksort_(Erlang)?oldid=6960
14 
15 -module(test_qsort).
16 -export([start/0]).
17 
18 start() ->
19     io:format("Testing qsort...~n"),
20     test_numeric_sort({qsort, qsort1}),
21     test_string_sort({qsort, qsort1}),
22     test_numeric_sort({qsort, qsort2}),
23     test_string_sort({qsort, qsort2}),
24     test_numeric_sort({qsort, qsort3}),
25     test_string_sort({qsort, qsort3}),
26     halt().
27 
28 test_numeric_sort({M,F}) ->
29     Stimulus = [3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3],
30     Response = [1,1,2,3,3,3,4,5,5,5,6,7,8,9,9,9],
31     test_sort({M, F}, "numeric sort", Stimulus, Response).
32     
33 test_string_sort({M, F}) ->
34     Stimulus = ["bob","alice","barry","zoe","charlotte","fred","marvin"],
35     Response = ["alice","barry","bob","charlotte","fred","marvin","zoe"],
36     test_sort({M, F}, "string sort", Stimulus, Response).
37     
38 test_sort({M, F}, Testname, S, R) ->
39     FunName = erlang:atom_to_list(F),
40     ModName = erlang:atom_to_list(M),
41     Result =  M:F(S),
42     if
43         R == Result -> 
44             io:format("~s:~s - passed - ~s.~n", [ModName, FunName, Testname]);
45         true -> 
46             io:format("~s:~s - failed - ~s.~n", [ModName, FunName, Testname])
47     end.


hijacker
hijacker
hijacker
hijacker