Count comparisons and assignments in three sorting algorithms

[Mike Stein]

Hello everyone,

I have three sorting algorithms in which I must count the number of swaps/copies and comparisons. I am meant to only count the swaps and comparisons that involve anything other than indexes as they are too fast to really matter (according to the professor). Could anyone please look over my work and let me know if my counters are in the right position. I keep coming up with swaps/comparisons that don't necessarily match the formulas I'm finding for best/worst case. Makes me think that my counters are somehow out of place or that I don't have enough of them.

Insertion Sort:

public class InsertionSort {

    public static void insertionSorter(int[] array) {
        
        int firstValue;                // first value in  array
        int scan;                    // scan array through the array
        int moves = 0;            //  number of moves 
        int compares = 0;      //  number of comparisons
        int total;                // total number of operations 
        
        for (int index = 1; index < array.length; index++) {
            
            firstValue = array[index];
            
            moves++;// count as a move
           
            scan = index;

            while (scan> 0 && array[scan - 1] > firstValue) {
                
                array[scan] = array[scan - 1];
                
                compares++; // count as a compare
                moves++;     // count as a move     
                scan--; 
            } compares++; // count as a comparison
            
            array[scan] = firstValue;  
            moves++;       // count as a move
    }

        total = compares + moves;
        
        // Display the number of assignments
        System.out.println("# of comparisons: " 
                + compares);
        System.out.println("# of moves: " + moves);
        System.out.println("Total number of operations: " +  total);
              
    }
}
      

Selection Sort:

public class SelectionSort {
    
       public static void selectionSorter(int[] array) {
        
        int start;              //  starting point of array
        int index;              // index of an array element
        int minIndex;              // element with smallest value
        int minValue;                //  smallest value in array
        int swaps = 0;             // swaps 
        int comparisons = 0;       //  comparisons
        int total;                  // The total number of operations
        
        for (start = 0; start < (array.length - 1); start++) {
            
            minIndex = start;
            minValue = array[start];
            swaps++; // count swap

            for (index = start + 1; index < array.length; index++){

                if (array[index] < minValue) {
                    
                   comparisons++; // count comparison
                    minValue = array[index];
                    swaps++; // count the swap
                    minIndex = index; // not sure if this should be counted as it is dealing with an index
                } 
            } comparisons++; // count comparison [b](not sure if this should be here)[/b]

            array[minIndex] = array[start];  
            swaps++; // count the swap
            array[start] = minValue;
            swaps++; // count the swap
        }

        total = comparisons + swaps;
        
        // Display the number of assignments
        System.out.println("# of comparisons: " 
                + comparisons);
        System.out.println("# of swaps: " + swaps);
        System.out.println("Total number of operations: " +  total);
    }
}

Quick sort:

public class QuickSort {
    
    private int compares = 0, swaps = 0, total;
   
    public void quickSorter(int array[]) {
  
        doQuickSort(array, 0, array.length - 1);

        total = swaps + compares;
        
         // Display the number of assignments
        System.out.println("# of comparisons: " 
                + compares);
        System.out.println("# of swaps: " + swaps);
        System.out.println("Total number of operations: " + total); 
    }
    
    private void doQuickSort(int[] array, int left, int right) {
        
        int pivot;     // The pivot point    
        
        if (left < right) {
            
           compares++; // count this as a comparison (not sure if this is right)
            pivot = findPivot(array, left, right);
            doQuickSort(array, left, pivot - 1);
            doQuickSort(array, pivot + 1, right);
        }   
    }

    private int findPivot(int array[], int left, int right) {
        
        int pivotValue;
        int leftMostEnd;
        int middlePoint;
        
        middlePoint = (left + right) / 2;
        
        swap(array, left, midddlePoint);
        
        pivotValue = array[left];
        swaps++; // count as a swap
     
        leftMostEnd = left;
        swaps++; // not sure if this should be counted as a swap
        
        for (int scan = left + 1; scan <= right; scan++) {

            if (array[scan] < pivotValue) {
                
                compares++; // count as comparison
                leftMostEnd++;
                swap(array, leftMostEnd, scan); 
            }
        } compares++; // Count as comparison
        
        swap(array, left, leftMostEnd);
 
            return leftMostEnd;
    }

    private void swap(int[] array, int a, int b) {

        int temp;
       
      //count all three swaps 

        temp = array[a];
        swaps++;
        array[a] = array[b];
        swaps++;
        array[b] = temp;
        swaps++;
    }
}

[Liutauras Vilda]

Hello Mike,

Had a change to have a look only at the quick sort at the moment.

Lines:

temp = array[a];
swaps++;
array[a] = array[b];
swaps++;
array[b] = temp;
swaps++;

You have to clarify, what do you call a swap. Actually over here, is just a one "visible" swap. Technically, I do agree that we could state swaps count as you did. In fact, I still think your professor expects as a 1 swap over here.
Please clarify.

[Mike Stein]

Liutauras Vilda,

In the swap method I should have labeled the swaps++ as moves++ because that is a more accurate description of what is going on.

[Liutauras Vilda]

Mike Stein wrote:In the swap method I should have labeled the swaps++ as moves++ because that is a more accurate description of what is going on.

temp = array[a];
swaps++;
array[a] = array[b];
swaps++;
array[b] = temp;
swaps++;

I'll ask differently.
Assume you have an array:

int[] array = {2, 1, 3, 4};

In order to get sorted array, you need to swap elements with a content 2 and 1.
How many swaps you considering you need to make?

It is important to make it clear, so someone could answer your main question correctly.

[Mike Stein]

Just one swap would be needed.

[Liutauras Vilda]

Mike Stein wrote:Just one swap would be needed.

Good.

temp = array[a];
swaps++;
array[a] = array[b];
swaps++;
array[b] = temp;
swaps++;

Those code lines from your quick sort algorithm does 1 swap. Changing places of numbers 2 and 1.
But you are counting as 3 swaps. So you have to fix it.

[Mike Stein]

Those code lines from your quick sort algorithm does 1 swap. Changing places of numbers 2 and 1.
But you are counting as 3 swaps. So you have to fix it.

Liutauras, I understand completely that this should be considered one swap. However, for my particular project I have to count every assignment (e.g. temp = array[index]) and every single comparison (array[index] < value or something like that). The only assignments and comparisons that I don't count involve indexes. I should only be counting the statements on array elements or elements of the same type such as tmp = array[i]. Trouble is, I'm not quite sure that I spotted or counted all of these operations in my sorting classes.

[Liutauras Vilda]

Mike Stein wrote:for my particular project I have to count every assignment (e.g. temp = array[index]) and every single comparison (array[index] < value or something like that).

Mike Stein wrote:

int moves = 0;
int compares = 0;
...
firstValue = array[index];
             
moves++;
            
scan = index;

Then you should be very carefully when you choose variable names. As it is hell confusing (moves, swaps, compares, comparisons)

Beside that, there are misplaced positions.

for (index = start + 1; index < array.length; index++){
 
                if (array[index] < minValue) {
                     
                   comparisons++;
                    minValue = array[index];
                    swaps++;
                    minIndex = index;
                } 
} comparisons++;

Line 10 wrong, should be after curly bracket on line 9. More better, on a separate line for better readability.

1. I would suggest you choose more precise variable names for counting (the same in all three programs).
2. Make bigger gaps between separate tasks, so you could better understand where one task finish, where other starts.

[Mike Stein]

Thank you for the suggestion. I see how it is a confusing mess. I have a specific question about the quicksort comparison count. I see that all the operations are occurring in the method that creates the partition. I'm having a hard time deciding where to put the comparison counter for the if statement. Specifically, I have counter for when the condition is true, but I don't know where to put the comparison counter when the condition is false. I tried placing it right outside the if statement, but that causes the comparison to be counted twice. I then tried putting it outside the for loop but that causes the comparison to be counted regardless of the conditions Boolean value.

private int findPivot(int array[], int left, int right) {
         
        int pivotValue;
        int leftMostEnd;
        int middlePoint;
         
        middlePoint = (left + right) / 2;
         
        swap(array, left, midddlePoint);
         
        pivotValue = array[left];
        swaps++; // count as a swap
      
        leftMostEnd = left;
        swaps++; // not sure if this should be counted as a swap
         
        for (int scan = left + 1; scan <= right; scan++) {
 
            if (array[scan] < pivotValue) {
                 
                compares++; // count as comparison

                leftMostEnd++;

                swap(array, leftMostEnd, scan); 

            } compares++; // Putting counter here counts the compares twice if condition is true
        
        } compares++; // Putting it here counts the comparison regardless of the condition (true or false)         
      
           swap(array, left, leftMostEnd);
  
            return leftMostEnd;
    }

I can't get how to count the comparisons when the condition is false. Any pointers?

[Liutauras Vilda]

Probably we over complicating this problem. Or we don't understand this problem at all (please paste the exact requirements over here, so we could exactly understand what they are).
As for me still lots of ambiguities in this problem.

Beside that, how about this idea?

1. for loop number of iterations/compares (scan <= right) is exactly "scan + 1". At the end you could add it to total.
2. instead "compares++" at line 21, move it to line 18. So you could check before, in case when false occurs.

To simplify you could count "for" and "if" compares as "total = scan * 2 + 1"

[Mike Stein]

Liutauras,

Thank you very much for all of your insight. Can't tell you how awful it is not to have someone to beat ideas back and forth with. So, I talked to the professor and was given a huge hint. I need to have two comparison counts (one for false and one for when the condition is true). Before reading your post, I thought well I can just add the comparison counter right before the if statement! So, you read my mind a bit :-). What I have now is a counter for when true and a counter in the event that what ever is outlined in the if statement is false. Does this make sense?

  private int getPivot(int numArr[], int left, int right) {
        
        int pValue;
        int leftEnd;
        int midPoint;
        
        midPoint = (left + right) / 2;
        
        swap(numArr, left, midPoint);
        
        pValue = numArr[left];
        moves++;
     
        leftEnd = left;
       
        for (int search = left + 1; search <= right; search++) {
            
            comparisons++; //fires off when the condition is false

            if (numArr[search] < pValue) {
                
                comparisons++; // fires when true
                leftEnd++;
                swap(numArr, leftEnd, search); 
            } 
        } 
        
        swap(numArr, left, leftEnd);
        
        
            
            return leftEnd;  
    }

[Liutauras Vilda]

Remove line 22 "comparisons++". It is a duplicate from line 18 (increments in both situations true or false).

You have to understand, that such a task requires a bit creativity.
For loop iterations is equal to if condition checks. So you don't need to separate variables for that.

[Mike Stein]

Okay, okay, I see. Since I need it to count when both true and false it is redundant to have the counter in the if statement! Thanks!

[Liutauras Vilda]

I still strongly advise you to post exact requirements over here, as the problem is not clear enough.
Of course you will have to solve it yourself, but at least we could point you to a right direction.

I could be wrong about many points, because for me still lots of ambiguities left about requirements.

[Paul Clapham]

Mike Stein wrote:Since I need it to count when both true and false it is redundant to have the counter in the if statement!

No, I don't think that's the right way to think of it. You don't need to increment the number of comparisons when something is true or false. You need to increment the number of comparisons when a comparison takes place.

[Mike Stein]

You don't need to increment the number of comparisons when something is true or false. You need to increment the number of comparisons when a comparison takes place.

Paul Clapham,

I see. This counting project is so seemingly simple (just count the comparisons and the assignments when they occur). Yet, I am having such a terrible time with it! You are right; my thinking on this is wrong. I am only concerned when a comparison is taking place. That being said, this is what I have come up with for the quicksort:

private int findPivot(int array[], int left, int right) {
         
        int pivotValue;
        int leftMostEnd;
        int middlePoint;
         
        middlePoint = (left + right) / 2;
         
        swap(array, left, midddlePoint);
         
        pivotValue = array[left];
        swaps++; // count as a swap
      
        leftMostEnd = left;
        swaps++; // not sure if this should be counted as a swap
         
        for (int scan = left + 1; scan <= right; scan++) {

           compares++;  // Adding my counter here will count the comparisons when they happen (in the event of true OR false)
 
            if (array[scan] < pivotValue) {
 

                leftMostEnd++;

                swap(array, leftMostEnd, scan); 

            }

        }          
        swap(array, left, leftMostEnd);
  
            return leftMostEnd;
    }

In all likelihood what I've come up with is most likely wrong, but my inferior logic is telling me that it works! ;-) :-(

[Paul Clapham]

Yes, that looks like the right way to count the number of comparisons to me.

[Liutauras Vilda]

If you follow that logic, then you need counter within the "if" statement.