Shell sort

[AlekseiKonov]

Good afternoon. Help me to make some things. In the output should be the time that the sorting took and the complexity of sorting( how many operations the program made). Thanks!

#include  <iostream> 
using namespace std;

int shellSort(int arr[], int n)
{
    for (int gap = n / 2; gap > 0; gap /= 2)
    {

        for (int i = gap; i < n; i += 1)
        {
            int temp = arr[i];
            int j;
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
                arr[j] = arr[j - gap];
            arr[j] = temp;
        }
    }
    return 0;
}

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

int main()
{
    int N;

    cout << "Enter the number of elements: ";
    cin >> N;

    int* arr = new int[N];
    for (int i = 0; i < N; i++)
    {
        arr[i] = rand() % 70;
    }
    cout << "Your array: "<<  endl;
    printArray(arr, N);

    shellSort(arr, N);

    cout << "\nSorted array:" << endl;
    printArray(arr, N);

    delete[] arr;

    return 0;

}

[salem c]

Sure, but if you want actual help, you need to make the first move.

Otherwise, you're just another zero effort drive-by looking to cheat on their homework.

We're your guide, not your mule.

[AlekseiKonov]

Yes, you`re right, sorry for this

[salem c]

Please edit for readability.
https://www.cplusplus.com/articles/jEywvCM9/

[AlekseiKonov]

Thank you

[salem c]

Well for timing, you might use this idea, specifically with high_resolution_clock
https://en.cppreference.com/w/cpp/chrono

For complexity, perhaps

int shellSort(int arr[], int n, int &nswaps)
{
    for (int gap = n / 2; gap > 0; gap /= 2)
    {

        for (int i = gap; i < n; i += 1)
        {
            int temp = arr[i];
            int j;
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                nswaps++;
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
        }
    }
    return 0;
}

int main()
{
...
    int nswaps = 0;
    shellSort(arr, N, nswaps);
...
   // some computation of N and nswaps 

[jonnin]

just put the gap in an array and get one of the good ones from the wiki. The one you used is poor and will make the algorithm look poor.

the better sequences have the form O(N)^(x+1/x) eg O(N)^7/6
however the sequence you use for gap changes the run time analysis dramatically. It can be anything from n*n (gap is just 1, no sequence used) to very close to logbased and a variety in between.
a computer < 5 years old should manage 3-5 million subsecond.