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