These three sorting algorithms are categorized as quadratic sorts because the number of steps increases as a quadratic function of the size of the list.

It will be very helpful to study algorithms based on the number of steps they require to solve a problem. We will add code to the sorting template program and count the number of steps for each algorithm.

This will require the use of an instance variable - we'll call it steps. The steps variable will be maintained within the sorting class and be accessed through appropriate accessor and modifier methods. You will need to initialize steps to 0 at the appropriate spot in the main menu method.

For our purposes, we will only count comparisons of items in the list, and gets or sets within the list. These operations are typically the most expensive (time-wise) operations in a sort.

As you type in the sorting algorithms, add increment statements for the instance variable steps. For example, here is a revised version of the bubbleSort method:

public void bubbleSort( ArrayList<Comparable> list )
{
  steps = 0;
  for ( int outer = 0; outer < list.size() - 1; outer++ )
  {
    for ( int inner = 0; inner < list.size()-outer-1; inner++ )
    {
        steps += 3;  //count one compare and 2 gets
        if ( list.get(inner).compareTo(list.get(inner + 1)) > 0 )
        {
           steps += 4;  //count 2 gets and 2 sets
           Comparable temp = list.get(inner);
           list.set(inner,list.get(inner + 1));
           list.set(inner + 1,temp);
        }
    }
  }
}

It is helpful to remember that a for statement is simply a compressed while statement. Each for loop has three parts: initialization, boundary check, and incrementation.

As you count the number of steps, an interesting result will show up in your data. As the size of the data set doubles, the number of steps executed increases by approximately four times, a “quadratic” rate.

Bubble Sort is an example of a quadratic algorithm in which the number of steps required increases at a quadratic rate as the size of the data set increases.