##
Suffix Arrays

A suffix array is an array formed by taking a string, and storing pointers to all the suffixes in the array. As an example, if the...

Posted by
Beetle B.
on
Mon 24 November 2014

##
Radix Sorts

Least Significant Digit Suppose we have \(N\) strings of length \(W\). The idea behind the LSD sort is to first sort the last “digit”...

Posted by
Beetle B.
on
Sun 23 November 2014

##
Counting Sort

Counting Sort Suppose we have \(N\) elements, but we know the elements are drawn from a fixed, finite list (called the alphabet in this...

Posted by
Beetle B.
on
Sat 22 November 2014

##
Heap Sort

One way to sort a list is to use the heap data structure. Given an array of \(N\) unsorted elements, build a max heap in place. Start...

Posted by
Beetle B.
on
Tue 19 August 2014

##
Quick Sort

A quick sort works recursively: Shuffle the list. This protects against a carefully crafted input that will make the algorithm...

Posted by
Beetle B.
on
Wed 13 August 2014

##
Convex Hull Problem

Say you have \(N\) points on a Euclidean plane. You want to find the polygon with the smallest area that can be formed connecting a...

Posted by
Beetle B.
on
Sun 10 August 2014

##
Sorting Complexity Analysis

Any comparison based sorting algorithm must use at least \(\lg(N!)\sim N\lg N\) comparisons for the worst case. This is absent any...

Posted by
Beetle B.
on
Sun 10 August 2014

##
Merge Sort

A merge sort works recursively: Split the list into two roughly equal halves. Sort each half using mergesort. Merge the two...

Posted by
Beetle B.
on
Thu 07 August 2014

##
Shell Sort

A shell sort works somewhat recursively. It first sorts every \(k\) elements (i.e. the sublist formed by elements 0, \(k\), \(2k\),...

Posted by
Beetle B.
on
Tue 05 August 2014

##
Insertion Sort

An insertion sort starts from the first element in the list, and then for each element will check with the previous one to see if it is...

Posted by
Beetle B.
on
Tue 05 August 2014

##
Inversions & Partial Sortedness

An inversion in a list of elements is a pair of elements where the 2nd element is smaller than the first (i.e. the 2nd element would be...

Posted by
Beetle B.
on
Tue 05 August 2014

##
Selection Sort

A selection sort starts out by traversing the whole list, finding the minimal element, and swapping it with the first element. It then...

Posted by
Beetle B.
on
Tue 29 July 2014