Keep track number of moves of element in array in Shell Sort C++

Question

I am having this assignment regarding implementation of Shell Sort in C++. I already manage to get the number of comparison between elements in the array in Shell Sort. However, I can't figure out how to identify the number of moves of the elements after comparison occur. Here is my code for Shell Sort (I get this code from Internet)

int shellSort(int arr[], int n) {
int compr = 0;      //indicate num of comparison
cout << endl << "Sorting using Shell Sort..." << endl << endl;
// Start with a big gap, then reduce the gap
for (int gap = n/2; gap > 0; gap /= 2) {
    compr++;        //the gap>0 comparison
    for (int i = gap; i < n; i += 1) {
        compr++;    // the i<size comparison
        // add a[i] to the elements that have been gap sorted
        // save a[i] in temp and make a hole at position i
        int temp = arr[i];
        // shift earlier gap-sorted elements up until the correct 
        // location for a[i] is found
        int j;            
        for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
            arr[j] = arr[j - gap];
            compr++;    // the j>=gap comparison
            compr++;    // the temp<arr[j-gap] comparison
        }            
        //  put temp (the original a[i]) in its correct location
        arr[j] = temp;
    }
}
cout << "Number of Comparison in Array of " << n << " Elements : " << compr << endl;}

Hopefully somebody can help me figure it out. Thanks in advance.

Answer 1

Check below code, where new variable moves indicates the number of moves of elements made during sorting:

int shellSort(int arr[], int n) {
    int compr = 0;      //indicate num of comparison
    int moves = 0;
    cout << endl << "Sorting using Shell Sort..." << endl << endl;

    // Start with a big gap, then reduce the gap
    for (int gap = n/2; gap > 0; gap /= 2) {
        compr++;        //the gap>0 comparison

        for (int i = gap; i < n; i += 1) {
            compr++;    // the i<size comparison
            // add a[i] to the elements that have been gap sorted
            // save a[i] in temp and make a hole at position i
            int temp = arr[i];
            // shift earlier gap-sorted elements up until the correct
            // location for a[i] is found
            int j;

            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
                compr++;    // the j>=gap comparison
                compr++;    // the temp<arr[j-gap] comparison
                moves+=2;     // elements are swapped / moved
            }

            //  put temp (the original a[i]) in its correct location
            arr[j] = temp;
        }
    }
    cout << "Number of Comparison in Array of " << n << " Elements : " << compr << endl;
    cout << "Number of Moves in Array of " << n << " Elements : " << moves << endl;
    return 0;
}

Swapping two elements to each other position is assumed to be 2 moves.