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.
As you type in the sorting algorithms, add increment statements for the variable steps
. For example here are the revised version of the bubbleSort
method:
void bubbleSort (int[] list)
{
steps++; // initialization of outer
for (int outer = 0; outer < list.length - 1; outer++)
{
steps += 3;
// 1 - boundary check of outer loop;
// 2 - increment, outer++
// 3 - initialization of inner loop
for (int inner = 0; inner < list.length - outer - 1; inner++)
{
steps += 3;
// 1 - boundary check of inner loop
// 2 - increment, inner++
// 3 - if comparison
if (list[inner] > list[inner+1])
{
int temp = list[inner]
list[inner] = list[inner + 1]);
list[inner + 1] = temp;
steps += 3; // swap of list[inner] & list[inner + 1]
}
}
}
}
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.
A quadratic equation in algebra is one with a squared term, like x2. In our sorting example, as the size of the array increases by a factor of N, the number of steps required for any of the quadratic sorts increases by a factor of N2.