A Software Engineering Space

Comb sort: Bubble sort learns from Donald Shell

Computer Sciences better mouse trap In the beginning the large majority of sort implementations were the more commonly known quadratic sorts: selection sort, insertion sort, and the omnipresent bubble sort. Radix sort was in use for the physical sorting of punch cards, and while merge sort was known by the late 1940s, the small main […]

qsort(): The C library function with an unfortunate name

qsort() At a glance most would assume such a function would invoke the quicksort algorithm, and they would be right – most of the time. Indeed MANY different C standard libraries bull ahead and use quicksort with varying amount of optimizations and call it a day. But an interesting note in the annals of history […]

Iterative Quicksort: removing recursion via explicit stack

Quicksort In my previous article on quick sort I covered in detail the recursive implementation of the famous sorting algorithm. A downside of Quick sort is that it has the potential to encounter worst-case quadratic complexity, which means that in the worst case the recursive version can reach a very steep stack depth leading to […]