How to count comparisons and swaps in insertion sort? (JAVA)

Question

public class Sorting
{
   public static int numOfComps = 0,
                     numOfSwaps = 0;

   public static void insertionSort(int[] array)
   {
      int unsortedValue;  // The first unsorted value
      int scan;           // Used to scan the array

      // The outer loop steps the index variable through 
      // each subscript in the array, starting at 1. The portion of
      // the array containing element 0  by itself is already sorted.
      for (int index = 1; index < array.length; index++)
      {
         // The first element outside the sorted portion is
         // array[index]. Store the value of this element
         // in unsortedValue.
         unsortedValue = array[index];

         // Start scan at the subscript of the first element
         // outside the sorted part.
         scan = index;

         // Move the first element in the still unsorted part
         // into its proper position within the sorted part.
         while (scan > 0 && array[scan-1] > unsortedValue)
         {
            array[scan] = array[scan - 1];
            scan--;

                // Counts the number of values swaps
                numOfSwaps ++;
         }

         // Insert the unsorted value in its proper position
         // within the sorted subset.
         array[scan] = unsortedValue;

         // Counts the number of values comparisons
        numOfComps ++;
      }
        System.out.println("\n\nNumber of comps = " + numOfComps);
       System.out.println("Number of swaps = " + numOfSwaps);       
   }
}

Newbie here again. How do I code this insertion sort program in Java to count the number of comparisons and the number of swaps? I have inserted comparison and swap codes into the program but not sure they're in the correct place. I have posted the program. Thanks for any help.

@ikegami Sorry that I provided a poor implementation of insertion sort, but it's the only insertion sort program provided in my textbook. How do I fix the program to get the correct number of comparisons and swaps? I'm very new at this with less than a year at learning it. — Jeremy
– Jeremy, Commented Mar 18, 2015 at 16:47

ikegami · Accepted Answer · 2015-03-18 16:51:11Z

3

The number of comparisons is the number of times array[scan-1] > unsortedValue is executed. That's not what you are counting.

Tips:

while (EXPRESSION) { STATEMENTS } can be rewritten as while (true) { if (!(EXPRESSION)) { break; } STATEMENTS }
!(EXPRESSION1 && EXPRESSION2) can be rewritten as !(EXPRESSION1) || !(EXPRESSION2).
if (EXPRESSION1 || EXPRESSION2) { break; } can be rewritten as if (EXPRESSION1) { break; } if (EXPRESSION2) { break; }.

The algorithm doesn't swap the value of pairs of variables. However, there is a form of multi-variable swap that occurs (A⇒B, B⇒C, C⇒D, D⇒A). The number of times this occurs is the number of times array[scan] = unsortedValue is executed when scan is different than index. That's not what you are counting.

Notes:

Your code is buggy. scan can be -1 when you reach array[scan] = unsortedValue;. This will happen when sorting 2, 1.
Note that this is a poor implementation of insertion sort. A binary search should be used instead of a linear search. This will reduce the maximum number of comparisons from N * N to N * log N.

answered Mar 18, 2015 at 16:51

ikegami

391k17 gold badges291 silver badges555 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Jeremy Over a year ago

I really appreciate your help.

Jeremy Over a year ago

I keyed in the following code after the 'while statement' and now I'm getting the same number of swaps as the program in the textbook with the same unsorted array in the textbook: if (index != scan) { numOfSwaps ++; }. Now to work on the number of comparisons code (numOfComps++;). Thanks a million, ikegami!

Collectives™ on Stack Overflow

How to count comparisons and swaps in insertion sort? (JAVA)

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related