在 Shell 排序 C++ 中跟踪数组中元素的移动次数

Question

我正在接受关于在 C++ 中实现 Shell 排序的作业。我已经设法在 Shell 排序中获得数组中元素之间的比较次数。但是，我无法弄清楚如何在比较发生后识别元素的移动次数。这是我的 Shell 排序代码（我从互联网上得到这个代码）

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;}

希望有人能帮我弄清楚。提前致谢。

Answer 1

检查下面的代码，其中新变量 moves 表示排序期间元素移动的次数：

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;
}

假设将两个元素交换到彼此的位置是 2 步。

在 Shell 排序 C++ 中跟踪数组中元素的移动次数

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

c++

arrays

sorting

shellsort