19/09/2017
I’ve visited the median problem a couple of times already. The median is the value in the middle of a sorted list of values. If the list is already sorted, that’s not much of a problem. If it isn’t, then we must use some efficient way to do it.
Read the rest of this entry »
Leave a Comment » | algorithms, C-plus-plus | Tagged: heuristics, median, QuickSort, selection, sort | Permalink
Posted by Steven Pigeon
29/12/2015
While preparing my lecture notes on sorting, I rediscovered the Dutch flag problem proposed by Edsger W. Dijkstra quite a while ago. This problem is relevant in the context of sorting, especially for variants of Quicksort, where you want to create not two but three partitions.
Like many problems, the Dutch flag problem has a very simple statement. Say you have an array with three types of value, how can you arrange them so that all the items of the first type is at the beginning of the array, the items of the third at the end (and, of course, leaving the second type between the two)?
Read the rest of this entry »
Leave a Comment » | algorithms, data structures, programming | Tagged: Dijkstra, Dutch Flag, Dutch Flag Problem, Partition, QuickSort, sorting | Permalink
Posted by Steven Pigeon
27/12/2011
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.
Read the rest of this entry »
4 Comments | algorithms, C, C-plus-plus, data structures, programming, theoretical computer science | Tagged: Lomuto, median, QuickSort, selection, Wirth | Permalink
Posted by Steven Pigeon
01/03/2011
The game is different whether we consider external data structures—that live partially or totally on disk or over the network—or internal data structures residing entirely in local memory. For one thing, none of the courses I had on data structures I had really prepared me to deal adequately with (large) external data structures; it was always assumed that the computer’s memory was somehow spacious enough to hold whatever data you needed.
However, when you’re dealing with files, you can’t really assume that you can access random locations to read, write, or exchange data at low cost, and you have to rethink your algorithms (or change plans altogether) to take the cost of slow external media into account. Sometimes an algorithm that doesn’t look all that useful in main memory suddenly makes more sense in external memory because of the way it scans its data. One of these algorithms is the Shellsort.
Read the rest of this entry »
18 Comments | algorithms, C-plus-plus, data structures, Mathematics, programming | Tagged: C, Combinatorial Analysis, External Data Structures, Hoare, QuickSort, shell, Shellsort, sorting | Permalink
Posted by Steven Pigeon
16/03/2010
QuickSort, due to Hoare, is one of the best comparison-based sorting algorithms around. There are a number of variations, but the vanilla QuickSort does a great job… most of the times.
Indeed, there are occasions where QuickSort leaves its expected run-time to reach run-time, its worst case. But what does it take to push QuickSort into its worst behaviour?
Read the rest of this entry »
4 Comments | algorithms, hacks, Mathematics, programming, rants, theoretical computer science, wtf | Tagged: bubble sort, C, comparison sort, computational complexity, evil, Hoare, malicious data, QuickSort, sort, sorts, Worst Case, Worst Case Behavior | Permalink
Posted by Steven Pigeon
23/06/2009
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.
Read the rest of this entry »
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
16/06/2009
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.
Read the rest of this entry »
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
23/12/2008
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.
Read the rest of this entry »
19 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