Introduction Something that comes up surprisingly often is traversing an array backwards. Maybe you’re emptying a queue. How about my personal favorite, reversing the order of elements. Counting in a for loop is so common you just don’t think about it. But counting backwards can lead to issues if you don’t do it right. The Wrong Way When you count down to and include 0 with an unsigned integer you’d think you could do something like this:...
Checking for bits in 1 byte is easy. Checking in 2 bytes is also easy. Checking an odd number of bits in a variable number bytes isn’t so easy. The hard part is dealing with the boundary between bytes where we need to move from one to the next. Lets say we have 3 bytes. We need to count the number of bits set for the first 19 bits. First we need the block of bytes we want to look at....
Introduction Quicksort is most people’s go to sort function and that’s not a bad thing because it’s a really good general purpose sorting algorithm. A good implementation is really fast and, being an in place algorithm, it uses very little memory. The big drawback of Quicksort is that it’s non-stable. This means there are some situations where using Quicksort a deal breaker and can’t be used. Enter Mergesort which is stable....
Introduction qsort, heapsort, mergesort, bsearch, and many more search and sort functions all take a compar argument to determine the sorting order of elements in an array. The compar function takes the form int (*compar)(const void *, const void *). The compar function’s parameters are the address of two of the elements in the array. The parameters will need to be dereferenced before they can be compared. Any type of value can have a compar function written for it and it can be used to sort an array of any type....
Introduction Quicksort is one of the most common sorting algorithms and one of the most efficient. It’s so common that it’s part of C89. That said, it’s still good to know how it works, its strengths, and it’s weaknesses. It takes as a divide and conquer approach to sorting. An element is selected as a pivot point. The elements are sorted against the pivot so all elements less than the pivot are on the left side and greater than elements are on the right....
Introduction Some times you need to swap bytes. Sometimes you don’t. But right now we do. Well, we don’t but if we were implementing some sorting functions we’d need a good swap function. Sorting typically doesn’t move pointers around, instead it moves the bytes pointed to by the pointer. Generic Swap We only want to have one swap function and not one for every single possible type. We’ll use void pointers and a width (number of bytes the type occupies) to make a generic swap function....