Problem converting C++ Program to CSharp Program. C++ Runs while there is exception in CSharp

Question

I am converting a C++ program to CSharp program. While C++ and Csharp are exactly the same, the C++ program runs with no problem for input { 5, 4, 1, 3, 6, 7, 2 } while in Csharp, there is index out of bound exception. I have pasted both the codes below and they are exactly the copy of each other but I cannot understand why there is an exception in CSharp version while C++ runs fine.

C++ Program

#include <iostream>
using namespace std;

#include <stdio.h>
#include<stdlib.h>

void swap (int *x, int *y)
{
  int temp = *x;
  *x = *y;
  *y = temp;
}

int partition (int A[], int l, int h)
{
  int pivot = A[l];
  int i = l, j = h;

  do
    {
      do
    {
      i++;
    } while (A[i] <= pivot);
  do
    {
      j--;
    } while (A[j] > pivot);

  if (i < j)
    swap (&A[i], &A[j]);
}
while (i < j);

  swap (&A[l], &A[j]);
  return j;
    }

void QuickSort (int A[], int l, int h)
{
  int j;

  if (l < h)
    {
      j = partition (A, l, h);
      QuickSort (A, l, j);
      QuickSort (A, j + 1, h);
    }
}

int main ()
{
  int A[] = { 5, 4, 1, 3, 6, 7, 2 }, n = 7, i;

  QuickSort (A, 0, n);

  for (i = 0; i < 7; i++)
    printf ("%d ", A[i]);
  printf ("\n");

  return 0;
}

CSharp Program

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace MyApp
{
    public class QuickSort2
    {
        int partition(int[] A, int l, int h)
        {
            int pivot = A[l];
            int i = l, j = h;

            do
            {
                do
                {
                    i++;
                }
                while (A[i] <= pivot);
                do
                {
                    j--;
                }
                while (A[j] > pivot);

                if (i < j)
                    Swap(ref A[i], ref A[j]);
            }
            while (i < j);

            Swap(ref A[l], ref A[j]);
            return j;
        }

        public void QuickSort(int[] A, int l, int h)
        {
            int j;

            if (l < h)
            {
                j = partition(A, l, h);
                QuickSort(A, l, j);
                QuickSort(A, j + 1, h);
            }
        }

        public void Swap(ref int x, ref int y)
        {

            int tmp = x;
            x = y;
            y = tmp;
        }
    }
}

[Test]
public void TestQuickSort2()
{
    QuickSort2 quick = new QuickSort2();
    int[] list = new int[] { 5, 4, 1, 3, 6, 7, 2};
    quick.QuickSort(list, 0, 7);
    for (int i = 0; i < 7; i++)
    {
        Console.Write(list[i] + " --> ");
    }

}

Edit 2. The problem happens at the following location and iteration

Can you put some try/catch clauses to find where the error is happening and in which iteration? I am suspecting that at some point you are trying to access A[7], which is out of bounds. In your C# program (there is no main, so we do not know), have you tried Quicksort(A, 0, 6)? — Miguel Mateo, Jul 08 '19 at 03:10
Please provide the `Main` method of the C# program. Also, arrays start from index 0 and ends at **n - 1** (`n` being your array length). `n = 7` in your program, and when you write `while (A[j] > pivot)` there is an out bound error because at the beginning `j = 7`. C++ doesn't check for array bound, but C# does. You should probably do `Quicksort(A, 0, 6)`. — ph3rin, Jul 08 '19 at 03:16
@user109260 `while (A[i] <= pivot);` -- Your C++ program does **not** run fine. This is an out-of-bounds access for the C++ program. The difference, as pointed out previously, is that C++ does **not** check array boundary conditions. If you do want C++ to check this, then use `std::vector`, and call `vector::at()` instead of using `[ ]`. Then you would see that your C++ program actually has a problem. — PaulMcKenzie, Jul 08 '19 at 03:38
Side note: C++ is a language with a very powerful Standard library. There is no need to write your own `swap`. No need to write your own sorting algorithms, either, but I have the feeling this is for an assignment. Anyway, writing a `swap` function in code with `using namespace std;` puts you in the fun world of knowing if your `swap` or the library's `std::swap` is going to be called. [This is but one of the many reasons one should not use `using namespace std;`](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) — user4581301, Jul 08 '19 at 05:21
You have an algorithm that is broken in both languages. Note that the do/while where the exception happens does not prevent `i >= h` . — H H, Jul 08 '19 at 07:03
The problem here is C++ does not check for bounds while C# does as suggested by @KaenbyouRin. So, the adding following bound check solved the issue. — user109260, Jul 08 '19 at 12:43

score 0 · Answer 1 · answered Jul 08 '19 at 23:21

The problem is right there, as I originally requested. This statement:

do {
  i++;
} while (A[i] <= pivot);

will go out of boundaries of the array if the last element of the array are lower than the variable pivot that you have calculated. Perhaps this solves the problem:

do {
  i++;
} while ((i <= h) && (A[i] <= pivot));

You need to do the same in the second cycle, so variable j does not go negative.

score -1 · Answer 2 · answered Jul 08 '19 at 12:44

-1

The problem here is C++ does not check for bounds while C# does as suggested by @KaenbyouRin. So, the adding following bound check solved the issue.

    int partition(int[] A, int l, int h)
    {
        int pivot = A[l];
        int i = l, j = h;

        do
        {
            do
            {
                i++;
            }
            while (i < h && A[i] <= pivot);  // i < h condition not needed in C++ as C++ doesnot check for array bounds but C# does
            do
            {
                j--;
            }
            while (j >= l && A[j] > pivot);

            if (i < j)
                Swap(ref A[i], ref A[j]);
        }
        while (i < j);

        Swap(ref A[l], ref A[j]);
        return j;
    }

answered Jul 08 '19 at 12:44

user109260

878
7
22

1

No, even though your c++ program doesn't check for array bound, it **DOESN'T MEAN YOU SHOULD VISIT ELEMENTS OUT OF THE ARRAY BOUND**, because this could lead to unpredictable results (even though it seems safe in your program). Use `Quicksort(A, 0, 6)` because your functions mean to take the range parameters inclusively (i.e including the upper-bound 6) – ph3rin Jul 08 '19 at 13:41
@KaenbyouRin - no, the entire algorithm uses an _exclusive_ upperbound. See `QuickSort(A, l, j);` – H H Jul 08 '19 at 16:46
But of course you are right about boundschecjing in C++ too. – H H Jul 08 '19 at 16:48

Problem converting C++ Program to CSharp Program. C++ Runs while there is exception in CSharp

2 Answers2