Skip to content

Instantly share code, notes, and snippets.

@svdmitrij
Last active December 20, 2015 18:28
Show Gist options
  • Save svdmitrij/5cf2c7b5b4b8268f26d0 to your computer and use it in GitHub Desktop.
Save svdmitrij/5cf2c7b5b4b8268f26d0 to your computer and use it in GitHub Desktop.
Merge sorting with inversions counting
-module('sort').
-export([start/0]).
start() ->
Ctr = spawn_link(counter, loop, [0]),
{ok, Data} = getData(),
{ok, _Sorted} = sortData(Data, Ctr),
counter:get_count(Ctr) .
getData() ->
{ok, Data} = readfile('IntegerArray.txt'),
{ok, Data}.
readfile(FileName) ->
{ok, Binary} = file:read_file(FileName),
Strings = string:tokens(erlang:binary_to_list(Binary), "\r\n"),
Integers = lists:map(fun(X) -> list_to_integer(X) end, Strings),
{ok, Integers}.
sortData(List, Ctr) ->
Sorted = mergesort(List, Ctr),
{ok, Sorted}.
mergesort([], _) -> [];
mergesort([X], _) -> [X];
mergesort(List, Ctr) ->
{Left, Right} = lists:split(length(List) div 2, List),
merge(mergesort(Left, Ctr), mergesort(Right, Ctr), Ctr).
merge(List, [], _) -> List;
merge([], List, _) -> List;
merge([A | Tail1] = Left, [B | Tail2] = Right, Ctr) ->
if
A < B ->
[A | merge(Tail1, Right, Ctr)];
true ->
% {ok, Count} = file:read_file('count'),
% NewCount = binary_to_term(Count) + length(Left),
% file:write_file('count', term_to_binary(NewCount)),
Length = length(Left),
Ctr ! {incr, Length},
[B | merge(Left, Tail2, Ctr)]
end.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment