Sort algorithm walkthroughs

Using D3 to animate sort algorithms

Here are visualizations of common sorting algorithms. Use the comparisons counter and number of items to observe the performance of each randomized case.

All source data is shuffled using the Fisher-Yates algorithm.

There's a fun clip about the sounds of sorting here.

Quick sort discussion

Implementation

• Select a pivot element anywhere in the list
• Uses "left" and "right" markers that approach each other from opposite ends of the list
• Left marker halts if its current value is greater than pivot
• Right marker halts if its current value is less than pivot
• Swap after both markers are halted, then continue moving inwards
• Once markers pass eachother, recurse for sublists on each side of pivot

Notes

• "Conquer and divide" algorithm
• Performance depends heavily on pivot selection
• O(n) time possible with partitioning

Merge sort discussion

Implementation

• Recursively split array until only single element slices remain.
• Consider two slices. Compare their heads and unshift minimum into a result array.
• Continue comparing heads and unshifting until the two slices are empty.
• Build result arrays from all the slices.
• Recurse the comparison process on the result arrays.

Notes

• Top down variant: Recursively split into halves, sort halves depth first, ending with original two halves. Tree-like. Implemented here.
• Bottom up variant: Split fixed intervals, sort each interval, join into full array, split larger interval, repeat.
• Natural variant: Bottom up, but with adaptive interval selection over existing ordering.
• Discussion of variants

Selection sort discussion

Implementation

• Consider [0]. Compare it to the rest of the elements to find the minimum value.
• Swap [0] with the index of the minimum. [0] is now finished.
• Proceed to [1]. Repeat.

Notes

• To remember: selection sort selects the minimum.
• Be aware of the unstable version, where a swap is greedy.
• No other sorting algorithm has less data movement (Rosetta Code)
• Good for cases where writes are expensive.

Insertion sort discussion

Implementation

• Compare [1] and [0]. Swap if [0] > [1].
• Compare [2] and [1]. Swap if needed. Continue swapping downward one by one until no swap is needed.
• Repeat with [3], [4], etc. until end of the array.

Notes

• Simplicity can make insertion sort a good choice for small arrays.
• Similar to selection sort, but uses bubbling rather than minimums.

Shellsort discussion

Implementation

• Decide on a gap width. 3 is used here.
• Start at [3]. Compare to [0]. Swap if [0] > [3].
• Move to [4]. Compare to [1]. Swap if necessary.
• Move to [5]. Compare to [2]. Swap if necessary.
• Continue the pattern and bubble downstream, exactly like insertion sort but with a gap of 3, not 1.
• After the end of the list is reached, it is weakly sorted. Perform a final insertion sort.
• Note: Insertion sort is a shell sort with a gap of 1.

Notes

• Weakly sorts elements to prepare for final pass using different sort algorithm
• Average performance depends on gap selection, but...
• Dependence on input data makes gap selection highly subjective

Bubble sort discussion

Implementation

• Order [1] and [0].
• Order [2] and [1].
• Continue to the end. Note that there is at most one swap per index.
• Repeat the process until fully ordered. Keep a boolean that shows if swaps have been made.
• Once there is a pass without swaps, all elements have bubbled down to their proper positions.

Notes

• If even one number is out of place means a new pass must be done.
• "Turtles" are small values that crawl slowly toward their position near the front.
• "Rabbits" are large values that hop quickly to their position near the end.
• Variations on bubble sort (cocktail sort, comb sort) try to address the turtle problem.