Insertion Sort Question

[mysiarobin1987]

Hi! I am trying to count the number of comparisons and assignments using insertion sort ONLY but the program I am using is telling me that the count is wrong. Can someone tell me what I am doing wrong? Thanks! I also put in the code for main.cpp if you need it.

inline void insertionSort(int list3[], int listLength, int& comp, int& assign)
{
    // write a function using insertion sort to sort the provided array

    // assign "comp" to the number of comparisons required

    // assign "assign" to the number of item assignments
    
    //local declarations of variables

int i, j, temp;

for (i = 1; i < listLength + 1; i++)
    {
        comp++;
            if (list3[i] < list3[i-1])
                {
                    comp++;
                    temp = list3[i];
                    j = i;
                    assign = assign+2;
                }
        do
            {
                list3[j] = list3[j-1];
                assign++;
                j--;
            } 


while(j > 0 && list3[j -1] > temp);
        {
            list3[j] = temp;
            assign++;
        }
    }
}

//main.cpp
#include <iostream>
#include <cstdlib>
#include <ctime>
#include "functions.cpp"

using namespace std; 

int main()
{
    int list1[5000]; 
    int list2[5000];
    int list3[5000];

    int compBubbleSort = 0, compSelectionSort = 0, compInsertionSort = 0;
    int assignBubbleSort = 0, assignSelectionSort = 0, assignInsertionSort = 0;

    fillArray(list1, 5000);
    copyArray(list1, list2, 5000);
    copyArray(list1, list3, 5000);

    bubbleSort(list1, 5000, compBubbleSort, assignBubbleSort);  
    selectionSort(list2, 5000, compSelectionSort, assignSelectionSort);  
    insertionSort(list3, 5000, compInsertionSort, assignInsertionSort);
    
    cout << "Number of comparisons---" << endl;
    cout << "  Bubble sort: " << compBubbleSort << endl;
    cout << "  Selection sort: " << compSelectionSort << endl;
    cout << "  Insertion sort: " << compInsertionSort << endl << endl;

    cout << "Number of item assignments---" << endl;
    cout << "  Bubble sort: " << assignBubbleSort << endl;
    cout << "  Selection sort: " << assignSelectionSort << endl;
    cout << "  Insertion sort: " << assignInsertionSort << endl << endl;


    return 0;   
}

[jonnin]

what are you counting?

for (i = 1; i < listLength + 1; i++)
{
comp++; //counts the loop iterations. This seems wrong unless you consider the loop variable check to be a comparison.

if (list3[i] < list3[i-1])
{
comp++; //counts actual data comparisons.

but you don't count the compares done in your while loop to shuffle the data.
(By the way, that is the BIG ONE, that while loop data move is where all your time is spent, and the bigger the data type being copied, the worse this becomes, eg if copying strings or classes here... at some point you swap to pointers and its the same as integers though).

[mysiarobin1987]

Oh ok I see now but when I take that out and run it the program still fails either way if it's there or not

[jonnin]

more info. does your sort actually work and sort the list? Counting the work is pointless if not :)

[mysiarobin1987]

jonnin, yes it does sort it.