Exads - Elixir Algorithms and Abstract Data Structures Collection

Good luck with this Sasha - sounds like an interesting project

Really awesome, and really useful! Starred for future reference

Thank you @ramonsnir Please feel free to contribute in any way if you want. We’re two people working on it so far.

I opened a pull request to add Travis CI and Inch CI badges Cheers!

@uranther Thank you! Already merged and resolved the conflicts for both Travis CI and Credo. The build is passing

Next I’ll be looking to implement the Inspect behaviour and maybe review the Priority Queue based on some things @NobbZ and me talked about.

One thing I thought of is to look at Enum.sort and see if we can implement a better algorithm (if possible).

I noticed you mentioned you are basing your algorithms & data structures on those in Introduction to Algorithms. I took a peek, and about lost it at the stateful, imperative implementations of the algorithms. I guess that is to be expected, but it makes it difficult to translate to a functional language.

For example, compare the imperative pseudo-code of insertion sort with its implementation in Haskell. The latter is so much easier to understand because it captures the high-level concepts.

Check out Purely Functional Data Structures by Chris Okasaki. This book may be more helpful for this project, although it doesn’t have all the ADS you list in the README. There’s also Pearls of Functional Algorithm Design.

Elixir just uses :lists.sort, which is an implementation of merge sort (source).

Yes, I’ve been refering to it because it’s the “standard book” for Algos and ADS (at least it is in most universities I’ve checked, including mine). I didn’t know about that Purely Functional Data Structures book, I’m going to check it out Thanks!

I still hadn’t checked Elixir’s implementation. In that case, shouldn’t Quicksort be better in terms of space, because of in place sorting? Not sure if this only applies to the imperative languages.

According to the internets:

Merge sort is often the best choice for sorting a linked list: in this situation it is relatively easy to implement a merge sort in such a way that it requires only Θ(1) extra space, and the slow random-access performance of a linked list makes some other algorithms (such as quicksort) perform poorly, and others (such as heapsort) completely impossible.

Seems to make sense. Maybe there are more advanced sorting algorithms that are well-suited for linked lists?

Another option is to parallelize the merge sort.

I’ll assign this task for myself, if you don’t mind (research about better sorting algos and write a parallel merge sort)

I will second this book. It goes into details about performance in FP style that most of us (or me at least) didn’t get in Algorithms class. Those classes seem to focus on imperative style analysis. This book introduces amortization and banker’s method. You can check out the full text here.