Skip to main content
Lesson 23 - Quadratic Sorting Algorithms
Lesson MenuPreviousNext
  
Counting Steps - Quadratic Algorithms page 7 of 10

  1. 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.

  2. 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.

  3. 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.

  4. 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]
          }
        }
      }
    }
    
  5. 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.

  6. 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.

  7. 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.

  8. 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.


Lesson MenuPreviousNext
Contact
 ©ICT 2003, All Rights Reserved.