« Back to all algorithms and all initial conditions

Random Initial Order

Problem Size:  20 · 30 · 40 · 50     Magnification:  1x · 2x · 3x
Initial Condition:  Random · Nearly Sorted · Reversed · Few Unique
Insertion
Selection
Bubble
Shell
Merge
Heap
Quick
Quick3

Discussion

A random initial order is often used to evaluate sorting algorithms in order to elucidate the "typical" case and to facilitate mathematical analysis. For some applications, however, this does not represent the typical case, so conclusions drawn here do not generalize.

Here we see the vast difference in speed between the O(n2) elementary sorting algorithms (insert, selection, bubble) and the more advanced algorithms.

Directions

  • Click on above to restart the animations in a row, a column, or the entire table.
  • Click directly on an animation image to start or restart it.
  • Click on a problem size number to reset all animations.

Key

  • Black values are sorted.
  • Gray values are unsorted.
  • A red triangle marks the algorithm position.
  • Dark gray values denote the current interval (shell, merge, quick).
  • A pair of red triangles marks the left and right pointers (quick).

References

Algorithms in Java, Parts 1-4, 3rd edition by Robert Sedgewick. Addison Wesley, 2003.

Programming Pearls by Jon Bentley. Addison Wesley, 1986.

Quicksort is Optimal by Robert Sedgewick and Jon Bentley, Knuthfest, Stanford University, January, 2002.

Bubble-sort with Hungarian ("Csángó") folk dance YouTube video, created at Sapientia University, Tirgu Mures (Marosvásárhely), Romania.

Select-sort with Gypsy folk dance YouTube video, created at Sapientia University, Tirgu Mures (Marosvásárhely), Romania.

The Beauty of Sorting YouTube video, Dynamic Graphics Project, Computer Systems Research Group, University of Toronto.