> For the complete documentation index, see [llms.txt](https://id1019.gitbook.io/exercises/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://id1019.gitbook.io/exercises/concurrency/bitonic.md). # Bitonic sorter ## Getting started In this task we should build a network for sorting. You use similar networks when you want to parallel sorting or have several streams of messages that should be sorted to several outgoing streams. The method we should use is called bitonic sorter and has recursive pattern. ## A bitonic sorting network ![A bitonic sort network of size 16.](/files/-LyyWZ7c_bPvW3ONTRIB) Above you see a sorting network of size 16, it has 16 in-going streams to the left and 16 outgoing streams to the right. The idea is that 16 numbers go through the network so that the smallest number always exits at the uppermost stream and the largest number on the lowermost stream. Where two streams are connected by a vertical line a comparison is performed. The smaller of the two values is forwarded on the upper stream and the larger on the lower. We see that we have a recursive pattern. A network for two streams is of course trivial and only requires one comparison. To sort four streams we 1/ first do a recursive sorting of two streams, then 2/ an operation that in the picture is a brown area and the we will call cross followed by 3/ two operations marked in red that we will call merge. The merge operation actually consist of a recursive repetition of a operation that we call zipc. If you look at how the network is sorting eight streams you see the two merge operations (one for the upper four streams and one for the lower four streams) internally consist of a zipc operation followed by two zipc operations on two streams each. When we implement these networks the comparisons will be processes and the network defined by the route messages are sent. A comparison process will wait for two incoming messages, compare the the values and forward the messages in the graph. ## a comparing process The first you should do is to define a process that receives two messages, compares the values and forwards the smaller to one process and the larger to another. We must keep track of the messages and make sure that they belong to the same group so we keep track of which epoch that should be handled and only accept messages of the current epoch. The messages to the process will have the following structure: * `{:epoch, n, x}` : `x` is a value of two in epoch `n` * `{:done, n}` : the process should terminate When the process is started it expects two messages from epoch $$0$$, two messages in epoch $$1$$ etc. It will forward the messages in the same format and same epoch number. A "done-message" is forwarded to both processes to terminate the whole network. Implement a function `comp/2` that takes two arguments, identifiers to the two processes to which the sorted values should be sent, starts a comparing process and returns the process identifier. The process should expect messages starting with epoch $$0$$. ```elixir def comp(low, high) do spawn(fn() -> comp(0, low, high) end) end def comp(n, low, high) do receive do {:done, ^n} -> send(low, {:done, n}) send(high, {:done, n}) {:epoc, ^n, x1} -> receive do {:epoc, ^n, x2} -> if x1 < x2 do send(low, {:epoc, n, x1}) send(high, {:epoc, n, x2}) else send(low, {:epoc, n, x2}) send(high,{:epoc, n, x1}) end comp(n+1, low, high) end end end ``` ### sorter/1 Assume that we have a function `setup/1` that takes a list of process identifiers and starts all processes needed for the sorting network. The list of process identifiers are the processes, in order, that the network should deliver the sorted values to. The function returns a list of process identifiers that the values in each epoch should be sent to. If we build a sorting network of size $$4$$, the function will start six processes and return a list `[i1,i1,i2,i2]` where `i1` and `i2` are the identifiers of the two first processes in the network. You should not implement `setup/1` now, we assume that it works. Implement a function `sorter/1` that takes a list of process identifiers, the processes to which we shall send the sorted epochs. The function should starta process that accept two messages: a request to sort a number of values and one to terminate the execution. * `{:sort, epoch}` : Where `epoch` is a list of values to be sorted. We assume that there are the same number of values as we have a sorting network for i.e. the values are sent to the in-going streams in the network (order does not matter). Don't forget to set the epoch number and increment a counter so that the next request is marked as the next epoch. * `:done` : terminate the network, forward to both processes To your help you can use the following functions: * `each(list, fun)` Apply a function to each element in the list. * `zip(list1, list2)` Return a list of tuples that consist of elements * from the two lists. A call to Ett anrop till `zip([1,2],[:a,:b])` * would return `[{1,:a},{2,::b]`. ```elixir def sorter(sinks) do spawn(fn() -> init(sinks) end) end def init(sinks) do netw = setup(sinks) sorter(0, netw) end def sorter(n, netw) do receive do {:sort, this} -> each(zip(netw, this), fn({cmp, x}) -> send(cmp,{:epoc, n, x}) end) sorter(n+1, netw) :done -> each(netw, fn(cmp) -> send(cmp, {:done, n}) end) end end ``` ### setup for $$n = 2$$ Time for the tougher part but we start with something simple. You should now implement the function {\tt setup/2} that takes two arguments, a number $$n$$ and a list of $$n$$ process identifiers. The process identifiers are the outgoing streams of the network, the function should start and connect all required processes in the network and return a list of entry points to the network. The function is then used to implement `setup/1` that is given below. We assume that $$n$$ is an even multiple of $$2$$ i.e. $$2,4,8,...$$ ```elixir def setup(sinks) do n = length(sinks) setup(n, sinks) end ``` Since we're starting simple, you should in this question only handle the case when $$n$$ is equal to $$2$$ (which means that the list only has two elements). You should of course use a function that you have defined in a previous question to start a comparison process. ```elixir def setup(2, [s1, s2]) do cmp = comp(s1, s2) [cmp, cmp] end ``` ### merge for $$n = 2$$ You now have all you need to start a network of size $$2$$ but this is of course close to ridiculous so we should extend it to size of $$4$$. You start by implementing a function that will set up a network to do a merge operation i.e. the red part in the Fig\~\ref{fig:bitonic}. The function `merge/2` takes a vale $$n$$ and a list of $$n$$ process identifiers. The function returns a list of process identifiers that make up the entry points of the merging network. We start with something simple, you should implement `merge/2` so that it works for $$n = 2$$. ```elixir def merge(2, [s1,s2]) do cmp1 = comp(s1,s2) [cmp1, cmp1] end ``` ### cross/2 Now for something slightly more complicated, the operation we call cross i.e. the brown operation in the image above. You should implement the function `cross/2` that takes two lists of process identifiers. The lists represent the $$n/2$$ upper and $$n/2$$ lower outgoing streams. The function should return a tuple consisting of two lists, the $$n/2$$ upper and $$n/2$$ lower entry points. The function should work for any $$n$$. You can use the function `reverse/1` that reverses a list. ```elixir def cross(low, high) do cross(low, reverse(high), []) end def cross([], [], crossed) do {reverse(crossed), crossed} end def cross([l|low], [h|high], crossed) do cmp = comp(l, h) cross(low, high, [cmp | crossed]) end ``` ### setup for $$n = 4$$ We now assume that the functions `setup/2`, `merge/2` and `cross/2` works when $$n=2$$, you should use these and extend `setup/2` to work if $$n = 4$$. ```elixir def setupp(4, [s1,s2,s3,s4]) do [m1, m2] = merge(2, [s1,s2]) [m3, m4] = merge(2, [s3,s4]) {[c1, c2], [c3, c4]} = cross([m1, m2], [m3, m4]) [i1, i2] = setup(2, [c1, c2]) [i3, i4] = setup(2, [c3, c4]) [i1, i2, i3, i4] end ``` ### merge/2 Time to extend `merge/2` to be able to handle any value of $$n$$ ($$2,4,8,...$$). The function now becomes a recursive function where you in each recursion perform what we called a zipc operation. The zipc operation is the transformation marked with red in the image above, so start by defining a function `zipc/2` that performs this operation on two set of lists of length $$n/2$$ and returns the entry points that you need. You can use the arithmetic operation `div/2` that performs integer division and the library function `split/2` that takes list and a number $$n$$ and returns a tuple of two sub-lists, the $$n$$ first elements and the rest. ```elixir def merge(n, sinks) do n = div(n,2) {sink_low, sink_high} = split(sinks, n) merged_low = merge(n, sink_low) merged_high = merge(n, sink_high) zipced = zipc(merged_low, merged_high) zipced ++ zipced end def zipc([], []) do [] end def zipc([l|low], [h|high]) do cmp = comp(l,h) [cmp | zipc(low, high)] end ``` ### a network for $$2^n$$ Now it is time to extend `setup/2` to handle arbitrary values of $$n$$ ($$2,4,8,...$$). Extend the function with the general case, use `div/2`, `split/2` and of course the functions `merge/2` and `cross/2` that we now assume works for all $$n$$. ```elixir def setup(n, sinks) do n = div(n,2) {sink_low, sink_high} = split(sinks, n) merge_low = merge(n, sink_low) merge_high = merge(n, sink_high) {cross_low, cross_high} = cross(merge_low, merge_high) in_low = setup(n, cross_low) in_high = setup(n, cross_high) in_low ++ in_high ``` --- # Agent Instructions This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com. ## Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter: ``` GET https://id1019.gitbook.io/exercises/concurrency/bitonic.md?ask=&goal= ``` `ask` is the immediate question: it should be specific, self-contained, and written in natural language. `goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.