Data Structures and Algorithms
Sorting
Some rules of thumb for selecting sorting algorithms:
- If sorting a small array, quicksort performs great.
- To perform sorting in place, use quicksort or heap sort.
- Mergesort offers stable sorting with excellent performance at the cost of O(n) extra memory.
- Internal vs external sorting (that is, if the algorithm can operate by splitting files in the hard-drive or if it fits on RAM). Mergesort can work by splitting files into smaller ones.
- If the data supports it, bucket/radix/counting sorts are an excellent pick: Counting for small data, buckets if the distribution of elements is uniform and radix if we can divide the data into number of bits (Note that there are ways of making Radix sort work with other data types).
Resources
- Radix sort implementation
- Radix sort is faster than quicksort
- Engineering radix sort, by McIlroy et al.
- American flag sort (Wikipedia)
- Stabilizing C’s Quicksort, by Chris Wellons
- Mergesort in C
Hash tables/Hashing
Resources
- Write a hash table in C
- Writing a damn fast hash table with tiny memory footprint
- Fibonacci hashing, the optimization that the world forgot, by Malte Skarupke
- Advanced techniques for fast hash tables
- Robin Hood hashing
- Cuckoo hashing (Wikipedia)
- Hopscotch hashing (Wikipedia)
- Hash functions
- Hash Functions and Block Ciphers
Random/Pseudo random
Resources
Graphics
Bresenham’s algorithm for rasterizing lines
- Get the initial (x0, y0) and final (x1, y1) coordinates for the line.
- Calculate the deltas
delta_x,delta_y,2 * delta_xand2 * delta_y - Initialize initail error parameter as:
err = 2_delta_y - delta_x - For each x coordinate point between x0 and x1 (
x_k) iferr < 0the next point is(x_k + 1, y_k); err = err + 2_delta_y. If not, `(x_k + 1, y_k- 1); err = err + 2_delta_y - 2_delta_x`
The previous algorithm will only work when drawing lines in the same direction. Additionally, the inputs may be flipped (e.g. x1 < x0) and the slope can be positive or negative. Here is a C implementation of the line drawing algorithm with these considerations in mind, using exclusively integer arithmetic:
// Draws a line with the given color between (x0,y0) and (x1,y1) using the
// Bresenham's line drawing algorithm using exclusively integer arithmetic.
static void
draw_line(int x0, int y0, int x1, int y1, Color clr) {
// Pointer to the initial position of the screen buffer where we will start
// writing our data.
vu16 *destination = (u16*)(SCREEN_BUFFER + y0 * SCREEN_WIDTH + x0);
// Adjust the step direction and calculate deltas.
int x_step;
int y_step;
int dx;
int dy;
if (x0 > x1) {
x_step = -1;
dx = x0 - x1;
} else {
x_step = 1;
dx = x1 - x0;
}
if (y0 > y1) {
y_step = -SCREEN_WIDTH;
dy = y0 - y1;
} else {
y_step = +SCREEN_WIDTH;
dy = y1 - y0;
}
if(dy == 0) {
// Horizontal line.
for(int i = 0; i <= dx; i++) {
destination[i * x_step] = clr;
}
} else if(dx == 0) {
// Vertical line.
for(int i = 0; i <= dy; i++) {
destination[i * y_step] = clr;
}
} else if (dx >= dy){
// Positive slope.
int diff = 2 * dy - dx;
for (int i = 0; i <= dx; ++i) {
*destination = clr;
if (diff >= 0) {
destination += y_step;
diff -= 2 * dx;
}
destination += x_step;
diff += 2 * dy;
}
} else {
// Negative slope.
int diff = 2 * dx - dy;
for (int i = 0; i <= dy; ++i) {
*destination = clr;
if (diff >= 0) {
destination += x_step;
diff -= 2 * dy;
}
destination += y_step;
diff += 2 * dx;
}
}
}Other
Resources
- Fast median search, an ANSI C implementation
- A fast alternative to the modulo reduction
- Space efficient resizable arrays
- Dictionary of Algorithms and Data Structures
- Base64 encode/decode in C