 # 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).

## Graphics

### Bresenham’s algorithm for rasterizing lines

1. Get the initial (x0, y0) and final (x1, y1) coordinates for the line.
2. Calculate the deltas `delta_x`, `delta_y`, `2 * delta_x` and `2 * delta_y`
3. Initialize initail error parameter as: `err = 2_delta_y - delta_x`
4. For each x coordinate point between x0 and x1 (`x_k`) if `err < 0` the 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;
}
}
}``````