CODEWITHSUNDEEP
c#recursion
Yoeri Wysselinck
Yoeri Wysselinck

Reputation: 13

a part of a recursive method may not be performed in the recursion

I've made a small project to learn the different sorting algoritms. Each algoritm uses for base the same unsorted array. So that means I need to copy that array everytime for each algoritm. With most of the algoritms that works perfectly fine but with 2 of them (Merge Sort and Quick Sort) it doesn't work because I wrote them recursively. I've tried it like this:

public int[] MergeSort(int[] unsorted, bool copy, int right, int left = 0)
{
    if (copy == true)
    {
        int[] toSort = new int[unsorted.Length];
        Array.Copy(unsorted, toSort, unsorted.Length);
    }

    if (left < right)
    {
        int middle = (left + right) / 2;

        MergeSort(toSort, false, middle, left);
        MergeSort(toSort, false, right, middle + 1);

        int[] leftArray = new int[middle - left + 1];
        int[] rightArray = new int[right - middle];

        Array.Copy(toSort, left, leftArray, 0, middle - left + 1);
        Array.Copy(toSort, middle + 1, rightArray, 0, right - middle);

        int i = 0;
        int j = 0;
        for (int k = left; k < right + 1; k++)
        {
            if (i == leftArray.Length)
            {
                toSort[k] = rightArray[j];
                j++;
            }
            else if (j == rightArray.Length)
            {
                toSort[k] = leftArray[i];
                i++;
            }
            else if (leftArray[i] <= rightArray[j])
            {
                toSort[k] = leftArray[i];
                i++;
                                        }
            else
            {
                toSort[k] = rightArray[j];
                j++;
            }
        }
    }
    return toSort;
}

Ofcourse: I get the following error:

The name 'ToSort does not exist in the current context.

I've been looking at this for too long and I don't see it anymore.

The algoritm does work if I leave the whole copy thing out.

Upvotes: 1

Views: 58

Answers (4)

Guy
Guy

Reputation: 1512

as proposed above, to avoid the out of scope you need to delare the variable outside.

but to make your logic easier, and debugging simpler, I would stop the copy altogether. Since you do need to copy, you can do it in a preceding method (and keep the recursive method doing just the sorting).

here is how i see it:

                public int[] PreMergeSort(int[] unsorted, bool copy, int right, int left = 0)
    {
        int[] toSort = new int[unsorted.Length];
        if (copy == true)
        {
            Array.Copy(unsorted, toSort, unsorted.Length);
            return MergeSort(toSort, right, left = 0);
        }
        else
            return MergeSort(unsorted, right, left = 0);
    }
    public int[] MergeSort(int[] unSorted,  int right, int left = 0)
    {
        if (left < right)
        {
            int middle = (left + right) / 2;

            MergeSort(unSorted,  middle, left);
            MergeSort(unSorted,  right, middle + 1);

            int[] leftArray = new int[middle - left + 1];
            int[] rightArray = new int[right - middle];

            Array.Copy(unSorted, left, leftArray, 0, middle - left + 1);
            Array.Copy(unSorted, middle + 1, rightArray, 0, right - middle);

            int i = 0;
            int j = 0;
            for (int k = left; k < right + 1; k++)
            {
                if (i == leftArray.Length)
                {
                    unSorted[k] = rightArray[j];
                    j++;
                }
                else if (j == rightArray.Length)
                {
                    unSorted[k] = leftArray[i];
                    i++;
                }
                else if (leftArray[i] <= rightArray[j])
                {
                    unSorted[k] = leftArray[i];
                    i++;
                }
                else
                {
                    unSorted[k] = rightArray[j];
                    j++;
                }
            }
        }
        return unSorted;
    }

Upvotes: 0

Grant Winney
Grant Winney

Reputation: 66469

You only want to create a new int[] under a certain condition, so set toSort to reference the unsorted parameter initially, then create a new instance if copy == true.

int[] toSort = unsorted;

if (copy)
{
    toSort = new int[unsorted.Length];
    Array.Copy(unsorted, toSort, unsorted.Length);
}

Upvotes: 1

Kevin Le - Khnle
Kevin Le - Khnle

Reputation: 10857

I don't know about correctness of your algorithm, but to get past your compiling error, bring the definition of toSort outside of the if statement

int[] toSort = new int[unsorted.Length];
if (copy == true)
{        
    Array.Copy(unsorted, toSort, unsorted.Length);
}

Upvotes: 0

Jite
Jite

Reputation: 5847

You are creating a local variable toSort inside the if-scope: 

if (copy == true)
{
    int[] toSort = new int[unsorted.Length];
    Array.Copy(unsorted, toSort, unsorted.Length);
}

As soon as it runs out of scope (at the }) the toSort variable will cease to exist.
You will have to define it outside of the scope to be able to use it outside of it.

Upvotes: 2

Related Questions