Counting Steps

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.

In order to compare algorithms to see this for yourself, we will come up with a way to count the steps each algorithm takes to solve a problem. Then we can see how the steps increase when the number of items to process increases. For example, if it took 100 steps to process 10 items, but it took 400 steps to process 20 items, clearly the number of steps is not increasing linearly with the number of items. We will add code to the sorting template program and count the number of steps for each algorithm so we can collect this data.

In Lab 17.4 QuadSort, we will use an instance variable called steps to keep track of the number of steps executed. The steps variable will be maintained within the Sorts class. The starter code for the SortStep class already resets the steps count to 0 before a sort is run, so the code in the Sorts class can assume steps will be zero when a sorting method is called.

Which Steps To Count

While it is possible to use a variety of rules for what to count, the simplest rule is to just count everything: assignments, comparisons, math operations, method calls, increments, decrements...etc.

The increment and decrement operators will each count as a single step because they are optimized to be more efficient than a separate assignment and addition. Thus x++ counts as one step even though x = x + 1 would count as 2 steps (= and +).

We will treat referencing a value in an array the same as accessing the value in a variable since it is not a method call so just accessing the value will be free. We will count calls to the get(int) method of ArrayList as one step because it is a method call and therefore comes with the overhead of adding the method call to the stack and doing a range check, so it is slower than directly accessing an index in an array. In both cases, any calculations done to determine the index will of course count as steps because they are math operations and any operations such as assignment or comparison will still count as steps.

Similarly, the array property length is not a method, so arr.length will be treated the same as accessing the value of a variable and won't count as a step, but the ArrayList method size() is a method call, so list.size() would count as one step.

In the example below, the method is swapping the values on each side of index i.

public void swapNeighbors(int[] arr, int i) {
  int left = arr[i - 1];
  arr[i - 1] = arr[i + 1];
  arr[i + 1] = left;
}

Now, lets count the steps.

• +2 steps for int left = arr[i - 1] ( +1 for assignment = and +1 for math op i - 1)
• +3 steps for arr[i - 1] = arr[i + 1] (+1 for i - 1, +1 for =, and +1 for i + 1)
• +2 steps for arr[i + 1] = left (+1 for i + 1 and +1 for =)

That is 7 steps. We could write the step counting like this:

public void swapNeighbors(int[] arr, int i) {
  steps += 2; // =, -
  int left = arr[i - 1];
  steps += 3; // -, =, +
  arr[i - 1] = arr[i + 1];
  steps += 2; // +, =
  arr[i + 1] = left;
}

It is good practice to include a comment noting what was counted, so it is easy to confirm the counting was done correctly.

Since all the operations in swapNeighbors will be executed each time the method is called, we can combine them into a single statement that counts all those steps.

public void swapNeighbors(int[] arr, int i) {
  steps += 7; // =, -, -, =, +, +, =
  int left = arr[i - 1];
  arr[i - 1] = arr[i + 1];
  arr[i + 1] = left;
}

Step Counting With Conditional Statements

Sometimes there are conditional statements that control when code runs, so not all lines of code will be guaranteed to run each time. For example, the swapNeighbors method as written above would throw an IndexOutOfBoundsExeption in certain cases, so a better implementation would include boundary checks to prevent that from happening. To do that, we need to decide how it will handle the edges. Let's say we add a rule that says the method will do nothing if the index passed in is the first or last index in the array. We could then modify the method like this:

public void swapNeighbors(int[] arr, int i) {
  if (i > 0 && i < arr.length - 1) {
    int left = arr[i - 1];
    arr[i - 1] = arr[i + 1];
    arr[i + 1] = left;
  }
}

Since there is now some code that only runs in certain conditions, we need to make sure that steps are only counted when they are guaranteed to be executed.

The comparison in the first condition of the if statement (i > 0) is guaranteed to be executed regardless of whether it evaluates to true or not, so we can count that step just before the if statement like this:

public void swapNeighbors(int[] arr, int i) {
  steps++; // i > 0 comparison
  if (i > 0 && i < arr.length - 1) {
    int left = arr[i - 1];
    arr[i - 1] = arr[i + 1];
    arr[i + 1] = left;
  }
}

The if statement has an && in the condition, which means that due to boolean short circuiting, the second condition will only be checked if the first one is true. To handle that, you can simply add conditional logic to your step counting that only counts the steps in the second condition if the first one is true.

public void swapNeighbors(int[] arr, int i) {
  steps++; // i > 0 comparison
  if (i > 0) steps + = 2 // i < arr.length - 1 is two operations: < and -
  if (i > 0 && i < arr.length - 1) {
    int left = arr[i - 1];
    arr[i - 1] = arr[i + 1];
    arr[i + 1] = left;
  }
}

Now that we are ready to count the steps inside the if statement. To be sure the steps are only counted when the if condition is true, we simply put the step counting code for those operations inside the if statement. We already went over those steps earlier and figured out there are 7 steps, so we can just write the previous step counting code inside the body of the if statement:

public void swapNeighbors(int[] arr, int i) {
  steps++; // i > 0 comparison
  if (i > 0) steps + = 2 // i < arr.length - 1 is two operations: < and -
  if (i > 0 && i < arr.length - 1) {
    steps += 7; // =, -, -, =, +, +, =
    int left = arr[i - 1];
    arr[i - 1] = arr[i + 1];
    arr[i + 1] = left;
  }
}

Step Counting With Loops

A while loop is like an if statement that repeats, so you should count the steps for the condition before the while loop, just like you would for an if statement; however, you should also count the steps for the condition at the end of the body of the loop because when the body of the loop is completed, the condition will be checked again.

Lets say we had the following code segment. Assume x, n and list have already been declared and initialized.

while (x < n) {
  x++;
  n--;
  list.add(n);
}

We would add step counting code like this:

steps++; // x < n comparison
while (x < n) {
  steps += 3; // x++, n--, add()
  x++;
  n--;
  list.add(n);
  steps++; // x < n comparison
}

A for loop is similar to a while loop, except that there are more parts to it. The parts of a for loop are:

for (initialization; condition; change) {
  body
}

When a for loop is encountered:

• The initialization is executed exactly once in all cases.
• The condition will execute after the initialization regardless of whether the condition is true.
• The body will only execute after the condition is checked only if the condition is true.
• The change will always execute after the body.
• The condition will always execute after the change.

Lets take a specific example. Assume list has already been declared and initialized:

for (int i = 0; i < list.size() - 1; i++) {
  if (list.get(i).compareTo(list.get(i + 1)) > 0) {
    Comparable temp = list.get(i);
    list.set(i, list.get(i + 1));
    list.set(i + 1, temp)
  }
}

According to the rules above, we can start by counting the initialization and condition before the loop like this:

steps += 4; // =, <, size(), - (initialization and comparison)
for (int i = 0; i < list.size() - 1; i++) {
  if (list.get(i).compareTo(list.get(i + 1)) > 0) {
    Comparable temp = list.get(i);
    list.set(i, list.get(i + 1));
    list.set(i + 1, temp)
  }
}

Inside the body of the for loop, there is an if statement. We can count the steps in the condition before the if statement as we discussed earlier:

steps += 4; // =, <, size(), - (initialization and comparison)
for (int i = 0; i < list.size() - 1; i++) {
  steps += 5; // get(), compareTo(), get(), +, >
  if (list.get(i).compareTo(list.get(i + 1)) > 0) {
    Comparable temp = list.get(i);
    list.set(i, list.get(i + 1));
    list.set(i + 1, temp)
  }
}

Then we can count the steps inside the body of the if statement:

steps += 4; // =, <, size(), - (initialization and comparison)
for (int i = 0; i < list.size() - 1; i++) {
  steps += 5; // get(), compareTo(), get(), +, >
  if (list.get(i).compareTo(list.get(i + 1)) > 0) {
    steps += 7; // =, get(), set(), get(), +, set(), +
    Comparable temp = list.get(i);
    list.set(i, list.get(i + 1));
    list.set(i + 1, temp)
  }
}

Finally, at the end of the body, after the if statement, we can count the steps in the change and the condition which will decide whether another iteration occurs.

steps += 4; // =, <, size(), -  (initialization and comparison)
for (int i = 0; i < list.size() - 1; i++) {
  steps += 5; // get(), compareTo(), get(), +, > (the if condition)
  if (list.get(i).compareTo(list.get(i + 1)) > 0) {
    steps += 7; // =, get(), set(), get(), +, set(), + (the if body)
    Comparable temp = list.get(i);
    list.set(i, list.get(i + 1));
    list.set(i + 1, temp)
  }
  steps += 4; // i++, <, size(), - (change and comparison)
}

Bubble Sort Example

Here is an example of adding step counting to a bubbleSort method:

public void bubbleSort(ArrayList <Comparable> list){
  steps += 4; // =, <, size(), - (outer loop inititalization and condition)
  for (int outer = 0; outer < list.size() - 1; outer++){
    steps += 5; // =, <, size(), -, - (inner loop initialization and condition)
    for (int inner = 0; inner < list.size()-outer-1; inner++){
      steps += 5; // get(), compareTo(), get(), +, > (if condition)
      if (list.get(inner).compareTo(list.get(inner + 1)) > 0){
        steps += 7; // =, get(), set(), get(), +, set(), + (if body)
        Comparable temp = list.get(inner);
        list.set(inner,list.get(inner + 1));
        list.set(inner + 1,temp);
      }
      steps += 5; // inner++, <, size(), -, - (inner loop change and condition)
    }
    steps += 4; // outer++, <, size(), - (outer loop change and condition)
  }
}

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 x². In our sorting example, as the size of the array increases to N, the number of steps required for any of the quadratic sorts increases as a function of N².

Warning About Calling Methods

The method calls we counted in the examples above are all simple methods like get() and set() that perform essentially one operation, so it makes sense to count them as one step, but you should always consider what a method does when counting steps. For example, calling list.remove(0) will not just remove the first item, it will also shift all the other items in the list to the left. If there were 100 items in the list, that is equivalent to 99 calls of set on top of any math ops, so it would be a huge mistake to count that as a single step. If you are calling your own helper method, such as a swap method, simply add step counting to the helper method as we did for swapNeighbors, otherwise you will need to figure out a fair estimate of the number of steps the method will execute based on what it does.

When doing Lab 17.4 QuadSort, you should only use the methods get() and set(), so you should not run in to this complication.