Отслеживать количество ходов элемента в массиве в Shell Sort Stack Overflow

Question

Отслеживать количество ходов элемента в массиве в Shell Sort Stack Overflow

У меня есть это назначение относительно реализации Shell Sort в C ++. Мне уже удалось получить количество сравнений между элементами в массиве в Shell Sort. Однако я не могу понять, как определить количество ходов элементов после сравнения. Вот мой код для Shell Sort (я получаю этот код из Интернета)

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

Надеюсь, кто-нибудь поможет мне разобраться. Заранее спасибо.

0

arrays c++shellsort sorting

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Проверьте ниже код, где новая переменная перемещается указывает количество ходов элементов, сделанных во время сортировки:

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 хода.

0