Skip to content

anonymous /sorting.c
Created

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Decided to brush up on my sorting algorithms, and got a little sidetracked writing a memswap() while I was at it.
/*
* In a recent interview I was asked to write a function to sort an array on the whiteboard. I
* wrote a simple compare function, included stdlib.h, and called qsort(3). I was told that didn't
* count and I had to manually sort the array. Seeing as it had been several years since I had
* done that, it was more challenging than it should have been. After the interview I decided to
* brush up on my sorting algorithms, which lead to this.
*
* The following sorting algorithms are not optimized. They are short and simple, meant purely
* to refresh my memory and be easy to understand. There are helper functions along the way that
* take arguments that may not be used, but I have left those in place so I can go back later
* and add error checking/asserts if I so wish.
*
* Enjoy.
*/
#include <limits.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
/*
* not safe, but saves declaration and assignment, and I'm using it correctly...for now
* (4 days from now "ow, what's this hole in my foot?")
*/
#define MIN(x, y) ((x) <= (y) ? (x) : (y))
//#define MIN(x, y) ({ typeof(x) _x = (x), _y = (y); _x <= _y ? _x : _y; })
/*
* swap two chunks of memory of size 'size' pointed to by 'x' and 'y' one 'type' at a time
* based on glibc's SWAP for qsort
* NOTES: I hope/assume the compiler changes the division to a shift because sizeof(type)
* should always be a power of 2. How can I go from sizeof() to log2(sizeof()) so I
* can make it a shift anyway?
* I also assume here that the single divide/shift up front with decrements in the
* loop is faster than no divide/shift and doing 'size -= sizeof()' in the loop
* TODO: Figure out why glibc uses do while instead of while. Performance? Style?
*/
#define SWAP(type, x, y, size) ({ \
register size_t _size = (size) / sizeof(type); \
register type *_x = (type *)(x); \
register type *_y = (type *)(y); \
while (_size-- > 0) { \
type _t = *_x; \
*_x++ = *_y; \
*_y++ = _t; \
} \
})
#define SWAP_BYTEWISE(x, y, size) SWAP(char , x, y, size)
#define SWAP_WORDWISE(x, y, size) SWAP(uintptr_t, x, y, size)
/*
* find nearest word aligned address, and how far we are from it
* do this both in the forward and backward directions
* NOTE: assuming uintptr_t is word sized. Is this a good assumption?
*/
#define ALIGN(x) ((uintptr_t)((x) + sizeof(uintptr_t) - 1) & ~(sizeof(uintptr_t) - 1))
#define OFFSET(x) (ALIGN(x) - (uintptr_t)(x))
#define ALIGN_BACK(x) ((uintptr_t)(x) & ~(sizeof(uintptr_t) - 1))
#define OFFSET_BACK(x) ((uintptr_t)(x) - (ALIGN_BACK(x)))
/*
* perform the swaps a word at a time when possible, taking care of leading and trailing bytes
* when is it better to just use a big temporary buffer and memcpy around for the swap?
* NOTES: I felt it was too big to be a macro, but is called often enough that it should be inline,
* is that a good idea or a bad idea? In its current form, memswap causes my quicksort to be
* faster than glibc's qsort under specific circumstances. e.g. large array of unsigned long long
* and compiled with -O3 (very specific circumstances...).
* TODO: figure out if it's better to have an 'else' clause, or to set x, y, and size to leftovers
* and have a bytewise swap outside the if that takes care of innequal offsets and leftovers.
* Compile glibc's qsort with their SWAP() and this memswap and compare
* Figure out if this is faster due to word boundaries, or just because it's swaping 8 times as
* much every time
* If the offsets are not equal, could I still do this by reading/masking/writing out of phase?
*/
inline void memswap(char *x, char *y, size_t size)
{
size_t xoff = OFFSET(x);
if (xoff == OFFSET(y)) { // if x and y have the same offset from word alignment
SWAP_BYTEWISE(x , y , xoff );
SWAP_WORDWISE(x + xoff , y + xoff , size - xoff );
SWAP_BYTEWISE(ALIGN_BACK(x + size), ALIGN_BACK(y + size), OFFSET_BACK(x + size));
} else {
SWAP_BYTEWISE(x, y, size);
}
}
/*
* macro to define comparison functions for native types
*/
#define CMP_FUNC(name, type) \
int name(const void *a, const void *b) \
{ \
const type *_a = (const type *)a; \
const type *_b = (const type *)b; \
return ((*_a > *_b) - (*_b > *_a)); \
}
CMP_FUNC( char_cmp, char )
CMP_FUNC(short_cmp, short )
CMP_FUNC( int_cmp, int )
CMP_FUNC( ull_cmp, unsigned long long)
/*
* macro to define print functions for native types
*/
#define PRINT_FUNC(name, type, conv) void name(const void *a) { printf("%" conv " ", *(type*)a); }
PRINT_FUNC(print_char , char , "hhd")
PRINT_FUNC(print_short, short , "hd" )
PRINT_FUNC(print_int , int , "d" )
PRINT_FUNC(print_ull , unsigned long long, "llu")
/*
* print an array using 'print' on each element
*/
void print_array(void *base, size_t nmemb, size_t size, void (*print)(const void *))
{
char *p, *end;
for(p = (char*)base, end = p + nmemb * size; p < end; p+= size)
print((void*)p);
}
/*
* shuffle an arary
*/
void shuffle(void *base, size_t nmemb, size_t size)
{
size_t i;
char *pbase = (char *) base;
for (i = nmemb - 1; i > 0; i--)
memswap(pbase + i * size, pbase + (random() % (i + 1)) * size, size);
}
/*
* check if an array is sorted
*/
int is_sorted(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *))
{
char *p = (char *)base, *end = p + nmemb * size;
for (p += size; p < end && compar((void*)p - size, (void*)p) <= 0; p += size)
;
return (p == end);
}
/*
* check if an array is a heap using 'compar' to compare elements
*/
int is_heap(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *))
{
char *pbase = (char *)base;
size_t i;
for (i = 1; i < nmemb && compar((void*)(pbase + i * size), (void*)(pbase + (i - 1) / 2 * size)) <= 0; i++)
;
return (i == nmemb);
}
/*
* sorting algorithms
*/
/*
* bubble sort: let's make some computer scientists cry
* repeatedly step through array, swapping adjacent elements if they are out of order
* after each pass one more element at the end of the array is quaranteed to be in place
*/
void bubble_sort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *))
{
char *left, *right, *pbase = (char *)base;
for (right = pbase + nmemb * size - size; right > pbase; right -= size)
for (left = pbase; left < right; left += size)
if (compar((void*)left, (void*)right) > 0)
memswap(left, right, size);
}
/*
* insertion sort: for each element (starting with the second), copy it, move backwards
* through the array shifting up each element we pass and then insert the current element
* into the correct place
*/
void insert_sort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *))
{
char *p, *ins, tmp[size], *pbase = (char *)base, *end = pbase + size * nmemb;
for (p = pbase + size; p < end; p += size) {
memcpy(tmp, p, size);
for (ins = p - size; ins >= pbase && compar((void*)ins, (void*)tmp) > 0; ins -= size)
memcpy(ins + size, ins, size);
memcpy(ins + size, tmp, size);
}
}
/*
* selection sort: loop through the array to find the minimum element, then swap it with the
* leftmost unsorted element.
*/
void select_sort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *))
{
char *left, *right, *min, *pbase = (char *)base, *end = pbase + size * nmemb;
for (left = pbase; left < end; left += size) {
for (min = right = left; right < end; right += size)
if (compar((void*)right, (void*)min) < 0)
min = right;
memswap(min, left, size);
}
}
/*
* bogo sort: this one's worse than bubble sort. More of a joke, it was too easy to leave out.
* while the array isn't sorted, shuffle and try again
*/
void bogo_sort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *))
{
while(!is_sorted(base, nmemb, size, compar))
shuffle(base, nmemb, size);
}
/*
* sift down: move an element down a heap until it is correctly place
*/
void sift_down(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *), size_t top, size_t bottom)
{
char *pbase = (char *)base;
size_t child;
for (; top * 2 + 1 <= bottom; top = child) {
child = top * 2 + 1;
if (child + 1 <= bottom && compar((void*)(pbase + child * size), (void*)(pbase + (child + 1) * size)) < 0)
child++;
if (compar((void*)(pbase + child * size), (void*)(pbase + top * size)) < 0)
return;
memswap(pbase + child * size, pbase + top * size, size);
}
}
/*
* sift_up: move an element up a heap until it is correctly placed
*/
void sift_up(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *), size_t top, size_t bottom)
{
char *pbase = (char *)base;
size_t child, parent;
for (child = bottom; child > top; child = parent) {
parent = (child - 1) / 2;
if (compar((void*)(pbase + parent * size), (void*)(pbase + child * size)) < 0)
memswap(pbase + parent * size, pbase + child * size, size);
else
return;
}
}
/*
* heapify: given an array, shift elements around to satisfy the heap condition
* NOTE: it's possible to do this with sift_up or sift_down. According to wikipedia (and I think
* I understand) sift_down gives O(n) time and sift_up gives O(nlogn) time.
*/
void heapify(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *))
{
/*
size_t bottom;
for (bottom = 1; bottom < nmemb; bottom++)
sift_up(base, nmemb, size, compar, 0, bottom);
*/
int top;
for (top = (nmemb - 2) / 2; top >= 0; top--)
sift_down(base, nmemb, size, compar, top, nmemb - 1);
}
/*
* heap sort: heapify the array, then repeatedly swap the max element (array[0] due to the heap)
* into the correct place at the end of the unsorted array, and restore the heap condition by
* sifting down the element now in array[0]
*/
void heap_sort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *))
{
char *pbase = (char *)base;
int bottom;
heapify(base, nmemb, size, compar);
for (bottom = nmemb - 1; bottom > 0; sift_down(base, nmemb, size, compar, 0, --bottom))
memswap(pbase, pbase + bottom * size, size);
}
/*
* merge: two sorted lists, both stored in 'base', starting at indices 'left' and 'right, will be
* merged in sorted order and placed into 'merged' starting at index 'left'
*/
void merge(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *), size_t left, size_t right, size_t end, void *merged)
{
char *pbase = (char *)base;
size_t m, i = left, j = right; // index into merged, left, and right respectively
for (m = left; m < end; m++)
if (i < right && (j >= end || compar((void*)(pbase + i * size), (void*)(pbase + j * size)) <= 0))
memcpy(merged + m * size, pbase + i++ * size, size);
else
memcpy(merged + m * size, pbase + j++ * size, size);
}
/*
* merge sort: starting with n lists of size 1, lists are merged in pairs, halving the number of
* lists and doubling the size. A bottom up approach to merge sort that avoids recursion.
* NOTE: A buffer of the same size as the array being sorted must be supplied. This is used to merge
* into each time.
* Interesting tidbit, this merge_sort uses the exact same number of compares as glibc's qsort
*/
void merge_sort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *), void *buf)
{
char *pbase = (char *)base, *pbuf = (char *)buf;
size_t width, i, nswaps = 0;
for (width = 1; width < nmemb; width *= 2) {
for (i = 0; i < nmemb; i += 2 * width)
merge(pbase, nmemb, size, compar, i, MIN(i + width, nmemb), MIN(i + 2 * width, nmemb), pbuf);
memswap((char*)&pbase, (char*)&pbuf, sizeof(pbase));
nswaps = !nswaps;
}
if (nswaps) // final list is in buf, copy it to base
memcpy(base, buf, nmemb * size);
}
/*
* partition: partitions an array for use with quicksort, using the last element as the pivot.
* all elements less than and greater than the pivot come before and after the pivot respectively
* return a pointer to the pivot
*/
char *partition(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *), char *low, char *high)
{
char *p;
for (p = low; p < high; p += size) {
if (compar((void*)p, (void*)high) < 0) {
memswap(p, low, size);
low += size;
}
}
memswap(low, high, size);
return low;
}
/*
* these macros are taken from glibc's qsort.c
* they implement a fast and simple stack for use with quicksort in order to avoid recursion
* as long as the smaller of the two partitions is sorted first, the stack will never grow larger
* than log(n). for 32 bit machines this is 32 entries (64 on 64 bit machines). instead of calculating
* just use that size, comes out to 256 bytes on 32 bit machines and 1024 on 64 bit
* NOTE: these aren't pretty, and aren't very safe, don't use them outside of quick_sort please
*/
#define STACK_SIZE (CHAR_BIT * sizeof(size_t))
#define PUSH(lo, hi) ((void) ((top->low = (lo)), (top->high = (hi)), top++))
#define POP(lo, hi) ((void) (top--, ((lo) = top->low), ((hi) = top->high)))
#define STACK_NOT_EMPTY (stack < top)
struct stack_node {
char *low, *high;
};
/*
* quick sort: parition the array, push the larger partition, push the smaller partition, repeat
*/
void quick_sort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *))
{
struct stack_node stack[STACK_SIZE];
struct stack_node *top = stack;
char *low, *mid, *high, *pbase = (char *)base;
PUSH(pbase, pbase + (nmemb - 1) * size);
while(STACK_NOT_EMPTY) {
POP(low, high);
mid = partition(base, nmemb, size, compar, low, high);
if (mid - low > high - mid) {
if (mid - size > low) PUSH(low, mid - size);
if (mid + size < high) PUSH(mid + size, high);
} else {
if (mid + size < high) PUSH(mid + size, high);
if (mid - size > low) PUSH(low, mid - size);
}
}
}
/*
* easily change the data type I'm testing with
*/
void no_print(const void *a) {}
#define TYPE unsigned long long
#define CMP ull_cmp
#define PRINT no_print
/*
* test all the sorting algorithms. on data sets large enough to see the difference between the fast algorithms
* the slow ones just take way too long.
*
* TODO: test with big structures, something multiple words in length, and compare different swap techniques
*/
int main()
{
int i, len = 1024 * 1024 * 8;
TYPE *a, *b; // b is used as a buffer for merge sort
if ((a = malloc(len * sizeof(TYPE))) == NULL) { printf("failed to malloc\n"); return 1; }
if ((b = malloc(len * sizeof(TYPE))) == NULL) { printf("failed to malloc\n"); return 1; }
/*
// test unaligned pointers with same offset
a = (TYPE *)((char *)a + 1);
b = (TYPE *)((char *)b + 1);
len--;
*/
/*
// test unaligned pointers with different offset
a = (TYPE *)((char *)a + 1);
b = (TYPE *)((char *)b + 2);
len--;
*/
// fill array, with some duplicates
for (i = 0; i < len; i++)
a[i] = (random() % 2) ? i : i + 1;
printf("qsort\n");
shuffle ((void*)a, len, sizeof(*a)); print_array((void*)a, len, sizeof(*a), PRINT); printf("\n");
qsort ((void*)a, len, sizeof(*a), CMP); print_array((void*)a, len, sizeof(*a), PRINT); printf("\n");
printf("%s\n\n", is_sorted((void*)a, len, sizeof(*a), CMP) ? "worked" : "failed");
printf("merge sort\n");
shuffle ((void*)a, len, sizeof(*a)); print_array((void*)a, len, sizeof(*a), PRINT); printf("\n");
merge_sort ((void*)a, len, sizeof(*a), CMP, (void*)b); print_array((void*)a, len, sizeof(*a), PRINT); printf("\n");
printf("%s\n\n", is_sorted((void*)a, len, sizeof(*a), CMP) ? "worked" : "failed");
printf("quick sort\n");
shuffle ((void*)a, len, sizeof(*a)); print_array((void*)a, len, sizeof(*a), PRINT); printf("\n");
quick_sort ((void*)a, len, sizeof(*a), CMP); print_array((void*)a, len, sizeof(*a), PRINT); printf("\n");
printf("%s\n\n", is_sorted((void*)a, len, sizeof(*a), CMP) ? "worked" : "failed");
printf("heapify\n");
shuffle ((void*)a, len, sizeof(*a)); print_array((void*)a, len, sizeof(*a), PRINT); printf("\n");
heapify ((void*)a, len, sizeof(*a), CMP); print_array((void*)a, len, sizeof(*a), PRINT); printf("\n");
printf("%s\n\n", is_heap ((void*)a, len, sizeof(*a), CMP) ? "worked" : "failed");
printf("heap sort\n");
shuffle ((void*)a, len, sizeof(*a)); print_array((void*)a, len, sizeof(*a), PRINT); printf("\n");
heap_sort ((void*)a, len, sizeof(*a), CMP); print_array((void*)a, len, sizeof(*a), PRINT); printf("\n");
printf("%s\n\n", is_sorted((void*)a, len, sizeof(*a), CMP) ? "worked" : "failed");
printf("select sort\n");
shuffle ((void*)a, len, sizeof(*a)); print_array((void*)a, len, sizeof(*a), PRINT); printf("\n");
select_sort((void*)a, len, sizeof(*a), CMP); print_array((void*)a, len, sizeof(*a), PRINT); printf("\n");
printf("%s\n\n", is_sorted((void*)a, len, sizeof(*a), CMP) ? "worked" : "failed");
printf("insert sort\n");
shuffle ((void*)a, len, sizeof(*a)); print_array((void*)a, len, sizeof(*a), PRINT); printf("\n");
insert_sort((void*)a, len, sizeof(*a), CMP); print_array((void*)a, len, sizeof(*a), PRINT); printf("\n");
printf("%s\n\n", is_sorted((void*)a, len, sizeof(*a), CMP) ? "worked" : "failed");
printf("bubble sort\n");
shuffle ((void*)a, len, sizeof(*a)); print_array((void*)a, len, sizeof(*a), PRINT); printf("\n");
bubble_sort((void*)a, len, sizeof(*a), CMP); print_array((void*)a, len, sizeof(*a), PRINT); printf("\n");
printf("%s\n\n", is_sorted((void*)a, len, sizeof(*a), CMP) ? "worked" : "failed");
printf("bogo sort\n");
shuffle ((void*)a, len, sizeof(*a)); print_array((void*)a, len, sizeof(*a), PRINT); printf("\n");
bogo_sort ((void*)a, len, sizeof(*a), CMP); print_array((void*)a, len, sizeof(*a), PRINT); printf("\n");
printf("%s\n\n", is_sorted((void*)a, len, sizeof(*a), CMP) ? "worked" : "failed");
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.