A small collection of simple data structures, sorting algorithms and searching algorithms. Explained and tested for learning and reference.
| Master | Develop |
|---|---|
 |
 |
To keep things simple, these data structures currently only support int for their data type.
array-list.c is a dynamic array that scales its capacity according to demand.
Pros
- O(1) append and delete from end, get and set from anywhere
- Can use binary search
- Simple
- Contiguous memory allocation
Cons
- O(n) insert and delete from start and within
- Uses more memory than is strictly necessary
Operations
- Mutators - Append, Insert, Set, Delete
- Accessors - Get, Find
- Utility - Sort, Reverse
- Misc - Automatic downscaling
linked-list.c implements a doubly linked list. A good choice if you need to insert at both the start and the end of a list.
Pros
- All mutators are O(1) on the start or the end of a list
- Can be merge sorted in O(1) space
Cons
- All mutators are O(n) within a list
- All accessors are O(n)
- Somewhat complex implementation
Operations
- Mutators - Append, Insert, Set, Delete
- Accessors - Get, Find
- Utility - Sort, Reverse
stack.c is a last in first out abstract data type based on an array list. It has three main operations: push, pop and peek.
Pros
- All operations are O(1)
- Easily implemented from array list
Cons
- Not many - an array list is one of the best ways to implement a stack
Operations
- Mutators - Push, Pop
- Accessors - Peek
queue.c is a first in first out abstract data type based on a linked list. It has two main operations: enqueue and dequeue.
Pros
- All operations are O(1)
- Easily implemented from a singly or doubly linked list
Cons
- Somewhat large memory overhead
Operations
- Mutators - Enqueue, Dequeue
heapsort.c is a fast in-place sort, but it is not suited to a parallel implementation.
Pros
- Fast with O(n log n) average case
- In-place sort (i.e. memory footprint O(1))
Cons
- Not a stable sort
- Not suited to a parallel implementation
mergesort.c is a fast, stable sort; but it uses double the memory footprint of the array it is sorting.
Pros
- Fast with O(n log n) average case
- Stable sort
- Easily parallelisable
Cons
- Large O(n) memory footprint
- Generally not as fast as quicksort due to the large memory copying overhead
simple-algorithms.c implements insertion sort. A simple algorithm that works well on small data sets.
Pros
- Performs better than many O(n log n) sorts on small datasets (n < ~20)
- Stable sort
- In-place sort (i.e. memory footprint O(1))
Cons
- With O(n^2) time complexity, it quickly becomes terrible for larger datasets
quicksort.c is one of the fastest comparison sorts for larger data sets, but can degrade to quadratic performance.
Pros
- Fast with O(n log n) average case
- Decent memory footprint O(log n)
- Easily parallelisable
Cons
- Bad O(n^2) worst case
- Not a stable sort
simple-algorithms.c implements both linear search and binary search.
| Algorithm | Pro | Con |
|---|---|---|
| Linear Search | Can operate on unsorted lists | O(n) |
| Binary Search | O(log n) | List must be sorted prior |
Memory Allocation
mem.c provides basic error handling for the malloc and realloc functions and helps prevents code duplication.
Common Functions
common.c contains simple functions that are shared across multiple files.