Phimuemue, in a recent post (at the time of writing, anyway) present his variation on sorting floating point values using radix sort. His implementation wasn’t dealing with the pesky sign bit so I offered a slight modification to his algorithm as a comment on his blog. But for some reason, he did not allow to post it.
So I’ll present my solution here.
5 Comments | 
algorithms, C, C99, hacks, Portable Code, programming | Tagged: endian, endianness, endians, floating point numbers, IEEE 754, Radix Sort, stddint.h | 
Permalink
Posted by Steven Pigeon
Last week I showed you the radix sort on simple linked lists. This week, I will present a version of QuickSort modified to sort simply linked lists.
2 Comments | algorithms, bit twiddling, C, C99, data structures, hacks, Mathematics, programming, theoretical computer science, Uncategorized | Tagged: address transformation, box plot, box-and-whiskers, boxplot, comparison sort, gettimeofday, graphs, median, microsecond, quartile, quartiles, Quick Sort, QuickSort, radix, Radix Sort, tests, timer, trials | Permalink
Posted by Steven Pigeon
The sorting algorithms we were taught in class were typically simplified versions of the algorithms that assumed that the data remained in memory and in contiguous memory locations, also known as an array. What we often have, however, are linked lists. Generalizing algorithms like the QuickSort to lists is not very hard in fact if we use a modification of the basic algorithm.
For lists with numerical keys (or values), there might be a simpler algorithm that scans the list in only one direction, so that simply linked lists are a perfectly cromulent data structure, that is, the radix sort.
2 Comments | algorithms, C99, data structures, database, Mathematics | Tagged: aces, card deck, cromulent, data mining, data set, deuces, external sorting, French suits, kings, large data set, linked lists, lists, playing cards, QuickSort, radix, Radix Sort, sorting cards | Permalink
Posted by Steven Pigeon
In Tunnels of Doom!, I wrote that the disjoint sets algorithm is one of the very few algorithms every programmer should know. That got me thinking. Should? What about must? If everyone must know about disjoint sets, what other algorithms must every programmer know about?
I made a “top ten” list of algorithms and data structures every programmer must know about.
9 Comments | algorithms, data compression, database, embedded programming, programming, Uncategorized | Tagged: array, Artificial Intelligence, Binary Search Tree, Binary Tree, Chess, disjoint set, Dynamic Programming, genetic algorithms, graph, graph algorithms, hash function, hash table, hashing, list, lookup table, memoization, one way function, QuickSort, Radix Sort, search, sorting, state space, state space search | Permalink
Posted by Steven Pigeon
