Can't get the correct number of insertion sort key comparison

Question

I'm struggling with the number of insertion sort key comparison and swap count..

I have this method that counts and prints out the key comparison at the end

public static void insertionSort(int[] array) {

    int n = array.length;
    int cm = 0;
    int sw = 0;


    for (int pass = 0; pass < array.length; pass++) {
        // figure out what should go into a[pass]
        int min = pass;
        for (int j = pass + 1; j < array.length; j++) {
            if (smaller(array, j, min)) {
                cm++;
                min = j;
            }
        }
        swap(array, pass, min);
        sw++;
    }

    System.out.print("Insertion sort: ");
    for (int c = 0; c < n; c++) {
        System.out.print(array[c] + " ");


    }

    System.out.println("- " + cm + " comparisons, " + sw + " swaps");
}

private static void swap(int[] a, int i, int j) {
    if (i != j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

private static boolean smaller(int[] a, int i, int j) {
    //another suggestion came up to call a count variable here because a false comparison could still count as a comparison
    count++;
    if (a[i] < a[j]) {
        return true;
    }
    return false;
}

With this test array

int[] test = {13, 12, 5, 6, 11};

I should get 7 comparisons and 4 swaps, but I'm getting 5 comparisons and 5 swaps. With another array from 0 to 31 consequently (testing for the best case), I get 0 comparison and 32 swaps.

What is `smaller`? I'm guessing you actually perform comparisons **there**. And if it is just a `<` then you only count comparisons that yield less than... — Elliott Frisch, Oct 19 '17 at 00:24
@ElliottFrisch ooh ooops forgot to post that part. private static boolean smaller(int[] a, int i, int j) { if (a[i] < a[j]) { return true; } return false; } — am1212, Oct 19 '17 at 00:24
tried putting a static int counter right before return true in smaller function, still counts 5.. — am1212, Oct 19 '17 at 00:25
Assuming call to `smaller()` is considered a "comparison", you need to increment `cm` whenever you call `smaller()`. Your code is only incrementing `cm` when `smaller()` returns `true`. Isn't a comparison that returns `false` still a comparison? — Andreas, Oct 19 '17 at 00:32
Please read "[How to create a Minimal, Complete, and Verifiable example](https://stackoverflow.com/help/mcve)". You haven't included the `swap` method. And don't post code in a comment. **Edit** the question to add missing code. — Andreas, Oct 19 '17 at 00:36
@Andreas that gives me 10 comparisons and I believe the it should be 7 comparisons. — am1212, Oct 19 '17 at 00:36
Then either you algorithm or your belief is wrong. Debug the code to figure it out. [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/q/25385173/5221149) — Andreas, Oct 19 '17 at 00:38
@Andreas my algorithm IS wrong and I have debugged for awhile.. that's why I'm asking for help from other keen engineers. — am1212, Oct 19 '17 at 00:41
See Wikipedia article on [Insertion sort](https://en.wikipedia.org/wiki/Insertion_sort#Algorithm_for_insertion_sort). The pseudocode shows `swap` being called in the *inner* loop. Your code calls `swap` in the *outer* loop. Entirely different algorithm. — Andreas, Oct 19 '17 at 00:54
the **sw** will be increased within the outer for loop for every array element, and the **cm** will be increased only when the smaller() return true , you should debugger to inspect the variable and you will figure out why — Jswq, Oct 19 '17 at 00:58
(`if (condition) { return true; } return false;` can and should be `return condition;`.) — greybeard, Oct 21 '17 at 20:11

am1212 · Answer 1 · 2017-10-19T03:53:22.857

Updating for an answer. This works for the comparison count but still working on the swap count.

private static int COMPCOUNT = 0;
public static void main(String[] args) {
    //best case for insertion sort is increasing order
    int[] bestCase = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31};
    //the worst case for insertion sort is decreasing order;
    int[] worstCase = {31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0};

    int[] randomArray = new int[32];
    for (int i = 0; i < randomArray.length; i++) {
        randomArray[i] = genarateRandom(32);
    }
}

public static int genarateRandom(int bound) {
    Random random = new Random();
    int rand = random.nextInt(bound);
    return rand;
}

private static boolean smaller(int[] a, int i, int j) {
    if (a[i] < a[j]) {
        COMPCOUNT++;
        return true;
    }
    return false;
}


public static void insertionSort(int[] arr)
{
    COMPCOUNT=0;
    int temp;
    for (int i = 1; i < arr.length; i++) {
        for(int j = i ; j > 0 ; j--){
            //use boolean function to check A[i] < A[j]
            if(smaller(arr, j, j-1)){
                //swap
                temp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = temp;
            }
        }
    }

    //print out the array
    System.out.print("Insertion sort: ");
    for (int c = 0; c < arr.length; c++) {
        System.out.print(arr[c] + " ");

    }

    //print out the number of comparison
    System.out.println("- " + COMPCOUNT + " comparisons");
}

(Don't write, *never* present uncommented code.) `This works for the comparison count` I can't *quite* see *how*: Doesn't `smaller(arr, a, b); smaller(arr, b, a); ` count as *two* comparisons? `still working on the swap count` I can't see a this code count or compute swaps. Does your code fail to count correctly, or is the number of "swaps" different from what you expect? — greybeard, Oct 19 '17 at 03:46
@greybeard I'm working on the swap count part still so it's not in here but it's in the above code. Isn't fail to count correctly and different from what I expect are the same thing..? I guess it could be different if my assumption is wrong. But as I stated in the original question, for the test array, it fails to count correctly AND different from what I expect. Count works well though. — am1212, Oct 19 '17 at 03:51
@greybeard I don't understand how smaller(arr, a, b); smaller(arr, b, a); count as two comparisons. If A[a] < A[b], and A[b] < A[a], then yes, it will increment the COMPCOUNT twice but the code isn't written that way. — am1212, Oct 19 '17 at 03:55

Can't get the correct number of insertion sort key comparison

1 Answers1