How would this shell-sort algorithm be coded in recursive?

Question

I understand that any iterative function can be written recursively, but I still don't quite understand how to write it as a recursive function.

This function receives an array (elements) and a int (number of elements), and sorts them from lower to higher, but I don't get how to make it recursive, any help would be appreciated!

void ShellSort(int *arr, int num){
    for (int i = num / 2; i > 0; i = i / 2)
    {
        for (int j = i; j < num; j++)
        {
            for(int k = j - i; k >= 0; k = k - i)
            {
                if (arr[k+i] >= arr[k])
                {
                    break;
                }
                else
                {
                    arr[k]=arr[k] + arr[k+i];
                    arr[k+i]=arr[k] - arr[k+i];
                    arr[k]=arr[k] - arr[k+i];
                }
            }
        }
    }
    return ;
}

Recursion is where a method calls itself from within its definition.. Your method as you have pasted it does not call itself. Nowhere in the body of your method does it say again ShellSort() — Kevon
– Kevon, Commented Nov 9, 2022 at 18:41

Nicat Abdullayev · Accepted Answer · 2023-09-20 04:12:55Z

Here is the shell sort with recursion:

namespace Algorithm.ShellSort { internal class Program { static void Main(string[] args) { int[] ints = { 11, 2, 3, 1, 6, -1, 4, 2, -2 };

        int[] sorted = ShellSort(ints);

        foreach (int i in sorted)
        {
            Console.WriteLine(i);
        }

        Console.ReadKey();
    }

    public static int[] ShellSort(int[] arr)
    {          
        int gap = 1;

        while (gap < arr.Length / 3)
            gap = 3 * gap + 1;

        while (gap >=1)
        {
            for (int i = 0; i < arr.Length; i++)
            {
                int left = i;
                int right = i + gap;

                Recursion(arr, left, right, gap);
            }

            gap /= 2;
        }

        return arr;
    }

    private static void Recursion(int[] arr, int left, int right, int gap)
    {
        if (left < 0)
            return;

        if (right >= arr.Length)
            return;

        if (arr[left] > arr[right])
        {
            Swap(arr, left, right);

            Recursion(arr, left - gap, right - gap, gap);
        }

        return;
    }

    private static void Swap(int[] arr, int i, int j)
    {
        if (i != j)
        {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
}

}

Collectives™ on Stack Overflow

How would this shell-sort algorithm be coded in recursive?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related