YoU CanT MaKE BuBBleSorT FaSTER With ASseMbLY

14/01/2020

In one of the classes I teach, we end up writing assembly language programs. And while I explain the (sometimes very relative) benefits of writing assembly language, I use bubble sort as an example where even carefully crafted assembly language doesn’t mean much: it’s a bad algorithm to start with.

YoU CanT MaKE BuBBleSorT FaSTER With ASseMbLY

Except that it’s not quite true.

Read the rest of this entry »


Medians (Part IV)

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 »


Choosing Random Files

14/02/2017

This week, something short. To run tests, I needed a selection of WAV files. Fortunately for me, I’ve got literally thousands of FLAC files lying around on my computer—yes, I listen to music when I code. So I wrote a simple script that randomly chooses a number of file from a directory tree (and not a single directory) and transcode them from FLAC to WAV. Also very fortunately for me, Bash and the various GNU/Linux utilities make writing a script for this rather easy.

dice

Read the rest of this entry »


Checking a LaTeX Index

31/03/2015

This week again, LaTeX. This time, the index. At the end of a document, you will usually find an index so that, if you don’t have a magical ctrl-f, you can find something fast in the book.

maths-discretes-index

In LaTeX, creating an index is really easy. You include the package makeindex, and plant \index{topic!subtopic} tags in the text (preferably just besides the word you want to index, the \index command doesn’t understand paragraphs). You add \printindex somewhere else in your document and you run pdflatex (or just latex) to get the index generated. That’s all fine except that it doesn’t provide checks. It adds to the index whatever you typed, and doesn’t give warnings if you have an entry “compression” and an entry “compresion” (because, you know, typos happen). Let’s see how we can somewhat fix that.

Read the rest of this entry »


Foiled!

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.

QuickSort Animation (Source: Wikipedia)

Indeed, there are occasions where QuickSort leaves its expected O(n \lg n) run-time to reach O(n^2) run-time, its worst case. But what does it take to push QuickSort into its worst behaviour?

Read the rest of this entry »