C++: In 1959, the American computer scientist Donald Shell invented a technique

Question

C++: In 1959, the American computer scientist Donald Shell invented a technique that can be used to speed up many different sorting algorithms. For this project, you will apply Shell’s method to insertion sort. The basis of the technique is to get the items to move in big steps (rather than shifting elements to the next-higher index). These big-step shifts are done early in the algorithm, and they tend to put the array in nearly sorted order. Later in the algorithm, we use smaller steps (all the way down to steps of size one, just like an ordinary insertion sort). But by the time that the small steps are being taken, the array is nearly sorted, and that’s a situation where insertion sort is efficient. The choice of the various step sizes affects the performance of the algorithm, but one sequence that is empirically good starts at n/2, and each subsequent step size is about the previous size divided by 2.2. The overall pseudocode is given here:

ss = n/2;

while (ss > 0) {

Do an insertionsort on the elements data[0], data[ss], data[2*ss].....

Also do an insertionsort on data[1], data[ss+1], data[2*ss+1].....

And on data[0], data[ss], data[2*ss].....

And so on.

The last little insertionsort that you do starts at data[ss-1].

ss = round ss/2.2 to nearest integer;

}

Please test your code in main().

Explanation / Answer

// C++ implementation of Shell Sort
#include <iostream>
using namespace std;

/* function to sort arr using shellSort */
int shellSort(int arr[], int n)
{
// Start with a big gap, then reduce the gap
for (int gap = n/2; gap > 0; gap /= 2)
{
// Do a gapped insertion sort for this gap size.
// The first gap elements a[0..gap-1] are already in gapped order
// keep adding one more element until the entire array is
// gap sorted
for (int i = gap; i < n; i += 1)
{
// 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];

// put temp (the original a[i]) in its correct location
arr[j] = temp;
}
}
return 0;
}

void printArray(int arr[], int n)
{
for (int i=0; i<n; i++)
cout << arr[i] << " ";
}

int main()
{
int arr[] = {12, 34, 54, 2, 3};
int n = sizeof(arr)/sizeof(arr[0]);

cout << "Array before sorting: ";
printArray(arr, n);

shellSort(arr, n);

cout << " Array after sorting: ";
printArray(arr, n);

return 0;
}

/*

Output:

Array before sorting:
12 34 54 2 3
Array after sorting:
2 3 12 34 54

*/

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.