c++arrayssortingshellsort

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


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.


Solution

  • 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.