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 »


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 »