<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">I completely understand that it’s artificial task and is not intended to be used in production. And, of course, I understand that I need to use the functions from the lists module. I just faced with the reverse issue a few times in other cases and that’s why this question has arisen. The quick sort function was just an example to demonstrate what I mean. Thanks for the “continuations” idea - it’s very helpful. Thank you, guys, for your responses. They are very impressing.<div class="">
<div style="color: rgb(0, 0, 0); letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div style="color: rgb(0, 0, 0); letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div class="">________________</div><div class="">Best Regards,</div><div class="">Andrey Koleshko</div><div class=""><a href="mailto:ka8725@gmail.com" class="">ka8725@gmail.com</a></div><div class=""><br class=""></div></div></div><br class="Apple-interchange-newline">
</div>
<br class=""><div><blockquote type="cite" class=""><div class="">On Dec 31, 2015, at 3:09 AM, <<a href="mailto:ok@cs.otago.ac.nz" class="">ok@cs.otago.ac.nz</a>> <<a href="mailto:ok@cs.otago.ac.nz" class="">ok@cs.otago.ac.nz</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div class=""><blockquote type="cite" class="">Hi, guys! I recently started to learn Erlang (migrating from Ruby) by<br class="">reading âErlang Programmingâ Cesarini book. After the 3rd chapter<br class="">there is a task to implement quick sort and I implemented it like this:<br class=""><a href="https://gist.github.com/ka8725/f3fcc264e12bcefa6035" class="">https://gist.github.com/ka8725/f3fcc264e12bcefa6035</a><br class=""></blockquote><br class="">This was an exercise, so whatever you learn from is right.<br class=""><br class="">In practice, you should be using the list reversal and sorting<br class="">functions from the lists: module.<br class=""><br class="">Instead of returning a compound data structure, it's often<br class="">useful to think "continuations":<br class=""> f(...) -> ...; f(...) -> {A,B,C}.<br class=""> g(...) -> {A,B,C} = f(...), h(A, B. C).<br class="">=><br class=""> g(...) -> f(.....).<br class=""> f(.....) -> ...; f(.....) -> h(A, B, C, ...).<br class=""><br class="">In the case of things like sorting, you can think of even and<br class="">odd layers, working in opposite directions. I'll leave you<br class="">to work out the details.<br class=""><br class="">Once you've eliminated reversing, the next thing would be<br class="">to reduce concatenation. (The wow-neat version of qsort<br class="">in Prolog uses list differences for this purpose; Erlang<br class="">would pass an accumulator, so<br class=""> qsort(List, Acc) === qsort(List) ++ Acc)<br class=""><br class="">However, you've missed the REALLY major point about the<br class="">code, the reason you should never use it.<br class=""><br class="">(A) It's quicksort, which has O(N**2) worst case.<br class=""> Yes, I know the books say this will almost never happen,<br class=""> but in practice it happens surprisingly often.<br class=""><br class=""> As Bentley and McIlroy pointed out in their "Engineering<br class=""> a Quicksort" paper, repeated values can kill a simple-<br class=""> minded quicksort. You need a "fat pivot", that is, you<br class=""> need to split the list THREE ways:<br class=""><br class=""> part([X|Xs], P, L, E, G, A) -><br class=""> if X < P -> part(Xs, P, [X|L], E, G, A)<br class=""> ; P < X -> part(Xs, P, L, E, [X|G], A)<br class=""> ; true -> part(Xs, P, L, [X|E], G, A)<br class=""> end;<br class=""> part([], _, L, E, G, A) -><br class=""> sort(L, E ++ sort(G, A)).<br class=""><br class=""> sort(List = [_,Pivot|_], Acc) -><br class=""> part(List, Pivot, [], [], [], Acc);<br class=""> sort(List, Acc) -><br class=""> List ++ Acc.<br class=""><br class=""> sort(List) -><br class=""> sort(List, []).<br class=""><br class=""><br class=""> Oh, by the way, you will notice that this does no<br class=""> reversal. Why would it? Yes, the intermediate<br class=""> lists L and G are delivered in reverse order, but<br class=""> we're going to *sort* them, so we don't *care* what<br class=""> order they are in. We would care if we were trying<br class=""> to make a stable sorting routine, but quicksort is<br class=""> not a stable sorting routine anyway. Reversing a<br class=""> list whose order you don't care about is pointless.<br class=""><br class="">(B) Even with a "fat pivot" quicksort can still go<br class=""> quadratic. Taking the first element of the list<br class=""> as the pivot means it WILL go quadratic if the<br class=""> input is already sorted or nearly sorted, which turns<br class=""> out to be quite common in practice. This is why<br class=""> array-based quicksorts use median-of-three pivot<br class=""> selection and the Bentley & McIlroy version uses<br class=""> the median of three medians of three for large enough<br class=""> inputs.<br class=""><br class="">Many people are impressed by the name "quick"sort and<br class="">don't look into the background. When Hoare invented quick<br class="">sort, he (a) already worked out most of the improvements<br class="">people talk about and (b) KNEW that on a good day with the<br class="">wind behind it quicksort would do more comparisons than<br class="">merge sort. BUT he needed to sort a bunch of numbers on<br class="">a machine with an amount of memory that would disgrace a<br class="">modern singing greeting card and just didn't have enough<br class="">memory for workspace. If comparisons are costly, it's<br class="">easy for a well-written merge sort to beat quicksort.<br class=""><br class="">For what it's worth, I have tested the code above but not<br class="">benchmarked it.<br class=""><br class=""><br class=""><br class=""></div></div></blockquote></div><br class=""></body></html>