The Applet

Written in 1997 by William Braynen [source]
Enhanced by Rex Posadas

Description

This applet illustrates the operation of a number of sorting algorithms and the concept of invariants. As it sorts a list of integers, it uses a different color to plot the part of the list affected by the invariant. An invariant is a condition that does not change during a program segment's execution.

• The visual invariant for selection sort: the items plotted in red are in their final place as they should be were the whole list sorted.
• The visual invariant for bubble sort: the items plotted in red are in their final place as they should be were the whole list sorted.
• The visual invariant for insertion sort: the items plotted in green form a sorted sub-list, but are not in their final place as they should be were the whole list sorted.
  
  
  

The Graph

On the x-axis: the position of the item in the list (or the array index i )
On the y-axis: the value of the item in the list (or the array value A[i])

Instructions

To start sorting, press the "Sort" button. The sorting routine can then be paused by pressing the "Pause" button (which the "Sort" button becomes once a sorting routine starts). The sorting routine can be stopped by pressing the "New" button.

To choose a particular sorting algorithm, use the radio buttons underneath the "Sort" button.

To create a new list of 200 random numbers (0 < value < 200), select the "Random" radio button and then press the "New" button.
To create a new randomly shuffled list of 200 numbers, none of which repeat (0 < value < 200), select the "Shuffled" radio button and then press the "New" button.

To change the speed of the sorting routine, use the pull-down menu.

To see the sorted list in the background, click the "Sorted List" checkbox in the right bottom corner of the applet.

Source Code

• InvariantsApplet.java
  • ArrayI.java
  • Graph.java
  • ThreadObject1.java
  • ThreadObject2.java
  • ThreadObject3.java
  • ThreadObject4.java