Anonymous avatar Anonymous committed 3cc2ecc

new stuff

Comments (0)

Files changed (6)

anagrams/anagrams.awk

+{
+	a[$2] = a[$2] (a[$2]?" ":"") $1
+}
+END {
+	for (k in a)
+		if (index(a[k]," "))
+			print a[k]
+}

anagrams/sortwords.c

+/*
+ * sortwords.c
+ *
+ * taking into account current LC_CTYPE and LC_COLLATE:
+ * read in word ([:space:] separated),
+ * print word followed by space
+ * sort characters
+ * print sorted word followed by newline
+ *
+ * use with anagrams.awk to get anagram classes
+ */
+
+#include <limits.h>
+#include <locale.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <unistd.h>
+#include <wchar.h>
+#include <wctype.h>
+
+int wcscoll_cmp(const void *a, const void *b) {
+	return wcscoll((const wchar_t *)a, (const wchar_t *)b);
+}
+
+int main(void)
+{
+	wint_t  wc;
+	wchar_t line[sysconf(_SC_LINE_MAX) / sizeof(wchar_t) * 2], *p = line;
+
+	setlocale(LC_ALL, "");
+	while ((wc = fgetwc(stdin)) != WEOF) {
+		if (iswspace(wc)) {
+			for (wchar_t *q = line; q < p; q += 2)
+				fputwc(*q, stdout);
+			fputwc(L' ', stdout);
+			qsort(line, (p - line) / 2, sizeof(wchar_t) * 2, wcscoll_cmp);
+			for (wchar_t *q = line; q < p; q += 2)
+				fputwc(*q, stdout);
+			fputwc(L'\n', stdout);
+			p = line;
+		} else {
+			*p++ = (wchar_t) wc;
+			*p++ = L'\0';
+		}
+	}
+	return 0;
+}

sorting.bash

-print_array()
-{
-	declare -n _arr=$1
-	printf "["
-	printf "%s," "${_arr[@]:0:${#_arr[@]}-1}"
-	printf "%s]\n" "${_arr[@]: -1}"
-}
-
-swap_in_array()
-{
-	declare -n _arr=$1
-	declare -i _a=$2 _b=$3
-	declare _t
-
-	_t=${_arr[$_a]}
-	_arr[$_a]=${_arr[$_b]}
-	_arr[$_b]=$_t
-}
-
-shuffle_array()
-{
-	declare -n _arr=$1
-
-	declare -i _i
-
-	for ((_i = ${#_arr[@]} - 1; _i > 0; _i--)); do
-		swap_in_array "$1" $((_i)) $((RANDOM % (_i + 1)))
-	done
-}
-
-str_cmp()
-{
-	declare -i a b
-	[[ $1 > $2 ]] && a=1
-	[[ $2 > $1 ]] && b=1
-	printf "%d" $((a - b))
-}
-
-int_cmp()
-{
-	printf "%d" $((($1 > $2) - ($2 > $1)))
-}
-
-compar()
-{
-	if declare -f "$cmp_func" >/dev/null 2>&1; then
-		"$cmp_func" "$@"
-	else
-		str_cmp "$@"
-	fi
-}
-
-is_sorted()
-{
-	declare -n _arr=$1
-
-	for ((i = 0; i < ${#_arr[@]} - 1; i++)); do
-		(("$(compar "${_arr[$i]}" "${_arr[$((i + 1))]}")" <= 0)) || return 1
-	done
-
-	return 0
-}
-
-is_heap()
-{
-	declare -n _arr=$1
-
-	for ((i = 1; i < ${#_arr[@]}; i++)); do
-		(("$(compar "${_arr[i]}" "${_arr[$(((i - 1) / 2))]}")" <= 0)) || return 1
-	done
-
-	return 0
-}
-
-bogo_sort()
-{
-	while ! is_sorted "$1"; do
-		shuffle_array "$1"
-	done
-}
-
-bubble_sort()
-{
-	declare -n _arr=$1
-
-	declare -i _left _right
-
-	for ((_right = ${#_arr[@]} - 1; _right > 0; _right--)); do
-		for ((_left = 0; _left < _right; _left++)); do
-			if (("$(compar "${_arr[$_left]}" "${_arr[$_right]}")" > 0)); then
-				swap_in_array "$1" $((_left)) $((_right))
-			fi
-		done
-	done
-}
-
-select_sort()
-{
-	declare -n _arr=$1
-
-	declare -i _left _right _min
-
-	for ((_left = 0; _left < ${#_arr[@]}; _left++)); do
-		for ((_min = _right = _left; _right < ${#_arr[@]}; _right++)); do
-			if (("$(compar "${_arr[$_right]}" "${_arr[$_min]}")" < 0)); then
-				((_min = _right))
-			fi
-		done
-		swap_in_array "$1" $((_min)) $((_left))
-	done
-}
-
-sift_down()
-{
-	declare -n _arr=$1
-	declare -i _beg=$2 _end=$3
-
-	declare -i _child _swap
-
-	for ((; _beg * 2 + 1 <= _end; _beg = _child)); do
-		((_child = _beg * 2 + 1))
-		if ((_child + 1 <= _end && "$(compar "${_arr[$_child]}" "${_arr[$((_child + 1))]}")" < 0)); then
-			((_child++))
-		fi
-		if (("$(compar "${_arr[$_child]}" "${_arr[$_beg]}")" < 0)); then
-			return
-		fi
-		swap_in_array "$1" $((_child)) $((_beg))
-	done
-}
-
-sift_up()
-{
-	declare -n _arr=$1
-	declare -i _beg=$2 _end=$3
-
-	declare -i _child _parent
-
-	for ((_child = _end; _child > _beg; _child = _parent)); do
-		((_parent = (_child - 1) / 2))
-		if (("$(compar "${_arr[$_parent]}" "${_arr[$_child]}")" < 0)); then
-			swap_in_array "$1" $((_parent)) $((_child))
-		else
-			break
-		fi
-	done
-}
-
-heapify()
-{
-	declare -n _arr=$1
-
-	declare -i _count=${#_arr[@]} _beg
-
-	for ((_beg = (_count - 2) / 2; _beg >= 0; _beg--)); do
-		sift_down "$1" $_beg $((_count - 1))
-	done
-}
-
-heap_sort()
-{
-	declare -n _arr=$1
-
-	declare -i _count=${#_arr[@]} _end
-
-	heapify "$1"
-
-	for ((_end = _count - 1; _end > 0;)); do
-		swap_in_array "$1" $((_end)) $((0))
-		sift_down "$1" $((0)) $((--_end))
-	done
-}
-
-partition()
-{
-	declare -n _arr=$1
-	declare -i _left=$2 _right=$3
-
-	declare -i _i
-
-	for ((_i = _left; _i < _right; _i++)); do
-		if (("$(compar "${_arr[$_i]}" "${_arr[$_right]}")" < 0)); then
-			swap_in_array "$1" $((_i)) $((_left++))
-		fi
-	done
-	swap_in_array "$1" $((_left)) $((_right))
-	((_piv = _left))
-}
-
-quick_sort()
-{
-	declare -n _arr=$1
-	declare -i _left _right
-
-	if (($# == 1)); then
-		((_left = 0, _right = ${#_arr[@]} - 1))
-	else
-		((_left = $1, _right = $2))
-	fi
-
-	if ((_right - _left < 2)); then
-		return
-	fi
-
-	declare -i _piv # set in partition()
-
-	partition "$1" $((_left)) $((_right))
-
-	qsort "$1" $((_left)) $((_piv - 1))
-	qsort "$1" $((_piv + 1)) $((_right))
-}

sorting.c

-/*
- * 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 placed
- */
-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 * 2;
-	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;
-}

sorting/sorting.bash

+print_array()
+{
+	declare -n _arr=$1
+	printf "["
+	printf "%s," "${_arr[@]:0:${#_arr[@]}-1}"
+	printf "%s]\n" "${_arr[@]: -1}"
+}
+
+swap_in_array()
+{
+	declare -n _arr=$1
+	declare -i _a=$2 _b=$3
+	declare _t
+
+	_t=${_arr[$_a]}
+	_arr[$_a]=${_arr[$_b]}
+	_arr[$_b]=$_t
+}
+
+shuffle_array()
+{
+	declare -n _arr=$1
+
+	declare -i _i
+
+	for ((_i = ${#_arr[@]} - 1; _i > 0; _i--)); do
+		swap_in_array "$1" $((_i)) $((RANDOM % (_i + 1)))
+	done
+}
+
+str_cmp()
+{
+	declare -i a b
+	[[ $1 > $2 ]] && a=1
+	[[ $2 > $1 ]] && b=1
+	printf "%d" $((a - b))
+}
+
+int_cmp()
+{
+	printf "%d" $((($1 > $2) - ($2 > $1)))
+}
+
+compar()
+{
+	if declare -f "$cmp_func" >/dev/null 2>&1; then
+		"$cmp_func" "$@"
+	else
+		str_cmp "$@"
+	fi
+}
+
+is_sorted()
+{
+	declare -n _arr=$1
+
+	for ((i = 0; i < ${#_arr[@]} - 1; i++)); do
+		(("$(compar "${_arr[$i]}" "${_arr[$((i + 1))]}")" <= 0)) || return 1
+	done
+
+	return 0
+}
+
+is_heap()
+{
+	declare -n _arr=$1
+
+	for ((i = 1; i < ${#_arr[@]}; i++)); do
+		(("$(compar "${_arr[i]}" "${_arr[$(((i - 1) / 2))]}")" <= 0)) || return 1
+	done
+
+	return 0
+}
+
+bogo_sort()
+{
+	while ! is_sorted "$1"; do
+		shuffle_array "$1"
+	done
+}
+
+bubble_sort()
+{
+	declare -n _arr=$1
+
+	declare -i _left _right
+
+	for ((_right = ${#_arr[@]} - 1; _right > 0; _right--)); do
+		for ((_left = 0; _left < _right; _left++)); do
+			if (("$(compar "${_arr[$_left]}" "${_arr[$_right]}")" > 0)); then
+				swap_in_array "$1" $((_left)) $((_right))
+			fi
+		done
+	done
+}
+
+select_sort()
+{
+	declare -n _arr=$1
+
+	declare -i _left _right _min
+
+	for ((_left = 0; _left < ${#_arr[@]}; _left++)); do
+		for ((_min = _right = _left; _right < ${#_arr[@]}; _right++)); do
+			if (("$(compar "${_arr[$_right]}" "${_arr[$_min]}")" < 0)); then
+				((_min = _right))
+			fi
+		done
+		swap_in_array "$1" $((_min)) $((_left))
+	done
+}
+
+sift_down()
+{
+	declare -n _arr=$1
+	declare -i _beg=$2 _end=$3
+
+	declare -i _child _swap
+
+	for ((; _beg * 2 + 1 <= _end; _beg = _child)); do
+		((_child = _beg * 2 + 1))
+		if ((_child + 1 <= _end && "$(compar "${_arr[$_child]}" "${_arr[$((_child + 1))]}")" < 0)); then
+			((_child++))
+		fi
+		if (("$(compar "${_arr[$_child]}" "${_arr[$_beg]}")" < 0)); then
+			return
+		fi
+		swap_in_array "$1" $((_child)) $((_beg))
+	done
+}
+
+sift_up()
+{
+	declare -n _arr=$1
+	declare -i _beg=$2 _end=$3
+
+	declare -i _child _parent
+
+	for ((_child = _end; _child > _beg; _child = _parent)); do
+		((_parent = (_child - 1) / 2))
+		if (("$(compar "${_arr[$_parent]}" "${_arr[$_child]}")" < 0)); then
+			swap_in_array "$1" $((_parent)) $((_child))
+		else
+			break
+		fi
+	done
+}
+
+heapify()
+{
+	declare -n _arr=$1
+
+	declare -i _count=${#_arr[@]} _beg
+
+	for ((_beg = (_count - 2) / 2; _beg >= 0; _beg--)); do
+		sift_down "$1" $_beg $((_count - 1))
+	done
+}
+
+heap_sort()
+{
+	declare -n _arr=$1
+
+	declare -i _count=${#_arr[@]} _end
+
+	heapify "$1"
+
+	for ((_end = _count - 1; _end > 0;)); do
+		swap_in_array "$1" $((_end)) $((0))
+		sift_down "$1" $((0)) $((--_end))
+	done
+}
+
+partition()
+{
+	declare -n _arr=$1
+	declare -i _left=$2 _right=$3
+
+	declare -i _i
+
+	for ((_i = _left; _i < _right; _i++)); do
+		if (("$(compar "${_arr[$_i]}" "${_arr[$_right]}")" < 0)); then
+			swap_in_array "$1" $((_i)) $((_left++))
+		fi
+	done
+	swap_in_array "$1" $((_left)) $((_right))
+	((_piv = _left))
+}
+
+quick_sort()
+{
+	declare -n _arr=$1
+	declare -i _left _right
+
+	if (($# == 1)); then
+		((_left = 0, _right = ${#_arr[@]} - 1))
+	else
+		((_left = $1, _right = $2))
+	fi
+
+	if ((_right - _left < 2)); then
+		return
+	fi
+
+	declare -i _piv # set in partition()
+
+	partition "$1" $((_left)) $((_right))
+
+	qsort "$1" $((_left)) $((_piv - 1))
+	qsort "$1" $((_piv + 1)) $((_right))
+}

sorting/sorting.c

+/*
+ * 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 placed
+ */
+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 * 2;
+	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;
+}
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.