Erlang. Упражнения (продолжение). Сортировка.

Exercise 3-6: Sorting Lists

Implement the following sort algorithms over lists:

Quicksort

The head of the list is taken as the pivot; the list is then split according to those
elements smaller than the pivot and the rest. These two lists are then recursively
sorted by quicksort, and joined together, with the pivot between them.

Надо сказать, это очень инетересное упражнение и заставило прилично вникнуть и понять синтаксис и работу erlang. Допускаю, что решение не самое оптимальное, и можно написать вариант быстрее, но мне кажется, что код очень легко читается, воспринимается и позволяет сразу увидеть суть алгоритма:

-module (test_3_6_qsort).
-compile(export_all).
-import (io).

qsort([]) ->
	[];

qsort([H | T]) ->	
	{Lesser, Bigger} = filter(H, T, {[], []}),
    qsort(Lesser) ++ [H] ++ qsort(Bigger).

filter(_, [], {Lesser, Bigger}) ->	
	{Lesser, Bigger};

filter(H, [Cur | T], {Lesser, Bigger}) ->  
    if
        H > Cur ->
            filter(H, T, {Lesser ++ [Cur], Bigger});
        true ->
            filter(H, T, {Lesser, Bigger ++ [Cur]})
    end.

test() ->    
	qsort([4,1,200,5,9,7,8,55,11,441]).

Comments

comments


Bookmark and Share