Java Insertion Sort: Counting Data Comparisons

Question

I am trying to place a counter for number of data comparisons and number of data swaps of this insertion sort algorithm using Java. While I believe counter swapsNo is correctly placed, compsNo is not giving me the expected output (both initialized at zero). I originally placed it where it is currently to count in cases where compElem is compared to list item, but clearly this simply Ups the counter for each item in the list. I am wondering if the counter should perhaps occur twice in the algorithm or somewhere else completely.

public void insertionSort(T[] list, int length)
{
 for (int firstOutOfOrder = 1; firstOutOfOrder < length;
                               firstOutOfOrder ++)
 {
     Comparable<T> compElem =
               (Comparable<T>) list[firstOutOfOrder];
     compsNo++;

     if (compElem.compareTo(list[firstOutOfOrder - 1]) < 0)
     {
         Comparable<T> temp =
                     (Comparable<T>) list[firstOutOfOrder];
         //or perhaps compsNo++; should go here??
         int location = firstOutOfOrder;

         do
         {
             list[location] = list[location - 1];
             location--;
             swapsNo++;

         }
         while (location > 0 &&
                temp.compareTo(list[location - 1]) < 0);

         list[location] = (T) temp;

     }
   }
 }

Update: I've added an incrementation for compsNo++ within a while loop (previously doWhile) and incrementation for swapsNo++ within if statement. This is approaching the expected output, but I'm not yet confident in my edits.

public void insertionSort(T[] list, int length)
{
 for (int firstOutOfOrder = 1; firstOutOfOrder < length;
                               firstOutOfOrder ++)

 {
     Comparable<T> compElem =
               (Comparable<T>) list[firstOutOfOrder];
     compsNo++;
     if (compElem.compareTo(list[firstOutOfOrder - 1]) < 0)
     {
         Comparable<T> temp =
                     (Comparable<T>) list[firstOutOfOrder];

         int location = firstOutOfOrder;



         while (location > 0 && temp.compareTo(list[location - 1]) < 0)
         {
             compsNo++;

             list[location] = list[location - 1];
             location--;
             swapsNo++;
         }




         list[location] = (T) temp;
         swapsNo++;
     }
  }
}

My advice would be to create a counting Comparator, and keep count in that class. — Elliott Frisch
– Elliott Frisch, Commented May 5, 2014 at 18:06
@ElliotFrisch I originally tried something in line with ideas presented in this thread: stackoverflow.com/questions/8292615/…, but as a beginner to Java I wasn't sure how to adapt it to my situation. — user25976
– user25976, Commented May 5, 2014 at 20:06

Andres · Accepted Answer · 2014-05-05 18:06:11Z

3

If you want to count the comparations, you should increment compsNo just after or before every line that contains an invocation to compareTo.

In your code, you have two invocations to compareTo, and only one compsNo++.

answered May 5, 2014 at 18:06

Andres

10.7k4 gold badges50 silver badges65 bronze badges

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

9 Comments

user25976 Over a year ago

Okay, I've edited my code to reflect an increment of compsNo in the do while loop. Is this what you meant?

Andres Over a year ago

No, the doWhile will always execute at least once, and that could produce no comparations in case location==0. But the counter is going to be incremented anyway.

user25976 Over a year ago

Also, I put the first compsNo++ before the if statement, because I figured it would be compared no matter what for each item in list. Is this correct, or should it be counted only if the comparesTo < 0?

Andres Over a year ago

The first compsNo++ is ok. The second is wrong, for the reason I wrote before.

user25976 Over a year ago

I see what you're saying, but I'm wondering why the doWhile still would increment if location==0 if the while condition is 'while (location > 0 && temp.compareTo(list[location - 1]) < 0);'

|

Collectives™ on Stack Overflow

Java Insertion Sort: Counting Data Comparisons

1 Answer 1

9 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

9 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related