So in the two previous parts of this series, we have looked at the selection algorithm and at sorting networks for determining efficiently the (sample) median of a series of values.
In this last installment of the series, I consider an efficient (but approximate) algorithm based on heaps to compute the median.
6 Comments | 
algorithms, C, C-plus-plus, data structures, hacks, programming | Tagged: heap, max-heap, med-heap, median, min-heap, selection | 
Permalink
Posted by Steven Pigeon
In the previous post of this series, we left off where we were asking ourselves if there was a better way than the selection algorithm of finding the median.
Computing the median of three numbers is a simple as sorting the three numbers (an operation that can be done in constant time, after all, if comparing and swapping are constant time) and picking the middle. However, if the objects compared are “heavy”, comparing and (especially) moving them around may be expensive.
3 Comments | algorithms, C, C-plus-plus, data structures, programming | Tagged: ADL, cmpxchg, median, Sorting Networks | Permalink
Posted by Steven Pigeon
In a previous installment, about filtering noise, we discussed how to use a moving average to even out irregularities in a sequence. Averaging over a window is tricky. First, the window size must make sense in terms of the speed at which the signal changes (in samples), and the average is (overly) sensitive to outliers.
One way to limit the influence of the outliers for denoising is to use the median. However, computing the median is usually more tricky than computing the average, or mean, and this first post (in a series of three, in the next few weeks), discusses how to compute the median efficiently using the selection algorithm.
2 Comments | algorithms, C, C-plus-plus, data structures, programming, theoretical computer science | Tagged: Lomuto, median, QuickSort, selection, Wirth | 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 | Uncategorized, algorithms, C, programming, bit twiddling, hacks, C99, Mathematics, data structures, theoretical computer science | Tagged: QuickSort, Radix Sort, radix, boxplot, box plot, box-and-whiskers, Quick Sort, tests, trials, graphs, gettimeofday, microsecond, timer, comparison sort, address transformation, median, quartile, quartiles | Permalink
Posted by Steven Pigeon
Yestermorning I presented an ad hoc compression method known as RLE, or run-length encoding and I got quite more reactions than I thought I would. Many suggested doing plenty of other stuff despite the fact that the post was about RLE, not about <insert your favorite compression method>. But something very nice happened: people got interested and many suggestions came forth.
I decided to implement the median-based prediction method as suggested by Dark Shikari here. Let us see the results!
11 Comments | algorithms, data compression, embedded programming, hacks | Tagged: Bitmap, Compression Ratio, efficient code, median, Palette, PNM, Pokemon, Pokemons, Predictive Coding, RLE, Run Length Encoding, Sprite | Permalink
Posted by Steven Pigeon
