CODEWITHSUNDEEP
c++sortingshellsort
mortal21
mortal21

Reputation: 19

implementing of Shell sort

my teacher said that line for (int j = i - step; j >= 0; j = j - step) spoils the whole essence of sorting. he said that I need to use the inset sorting function and insert it into the shell sorting. How can I do this?

template < typename T >
void swap(T* arr, int j, int step)
{
    T value = arr[j];
    arr[j] = arr[j + step];
    arr[j + step] = value;
}

template < typename T >
void shell_sort(T* arr, int length)
{
    for (int step = length / 2; step > 0; step = step / 2)  
    {
        for (int i = step; i < length; i++)                 
        {
            for (int j = i - step; j >= 0; j = j - step)    
            {
                if (arr[j] > arr[j + step])                 
                {
                    swap(arr, j, step);                     
                }
            }
        }
    }
}

Upvotes: 0

Views: 665

Answers (1)

ObliteratedJillo
ObliteratedJillo

Reputation: 5166

You can go for recursive shell sort like this:

template < typename T >
 int shell_sort(T* arr,  int length)
 {
    if (length <= 1)    return length;
    length = shell_sort(arr,length - 1);
    T value = arr[length];
    T i = length - 1;
    while ((i >= 0) && (arr[i] > value)) {
        arr[i + 1] = arr[i];
        i--;
    }
    arr[i + 1] = value;
    return length + 1;
}

Upvotes: 1

Related Questions