Very simple Vector implementation with add, add_all, get and delete operations using arrays of void pointers.
The downside to this as compared to simply using an array is that here we have an array of pointers, which means the data will most likely be scattered over the memory, not coalesced.
Continue reading “Vector”
Mergesort is an important sorting algorithm when you don’t have efficient random memory access, since it doesn’t rely on that and has good time complexity – O(n logn) specifically.
As a typical divide-and-conquer algorithm, Mergesort has two steps: first it recursively splits the lists in two until each half is unitary, then it recursively mends back the lists until it reaches the original size.
But before we dive into the actual algorithm, we need to make some changes to the linked list algorithm we’ll be using.
Continue reading “Mergesort”
Here’s a very simple implementation of the linked list data structure.
A pointer to the head element is enough to define a linked list. Each element consists of one pointer to the subsequent element in the list and one pointer to the element’s data:
Continue reading “Linked List”
As most major IT companies would tell you, it is important to keep sharp at basic algorithms and Computer Science theory. If you’re not fresh out of school, chances are that most of the basic stuff will start fading away.
I was starting to feel that about 1 year after graduation, so I decided to go back to the practical core of Computer Science: algorithms and data structures, aided by the classic Introduction to Algorithms by Cromen & Leiserson. C was my language of choice: although by this point I’m more comfortable with Java, C gives the programmer much more control over what’s going on in the machine, which in my opinion is extremely relevant to the process of learning algorithms.
I’ve deliberately chosen to use the bare minimum in terms of libraries, which means I’ll be using basically only C standard library. I do the actual coding in Notepad++ and compile with gcc. Up-to-date code can be found at my github account, linked to the right, on the sidebar.
My goal with this blog is both to relearn and to provide useful code and explanations for other students who are starting out at CS. For that purpose, I try being as instructive and didactical I can. However, understand that no material here is fail-proof; there will inevitably be (many) errors, bugs and typos – please don’t hold them against me. I will be happy if you point them out.
— Leonardo Brito