CODEWITHSUNDEEP
c++arrayspointers
Speerian
Speerian

Reputation: 1208

Copying arrays via pointers in C++

I've never programmed in C++ before and I'm trying to figure out how to recursively pass segments of an array in a C++ method. I am trying to convert the following pseudo code into C++.

SlowSort(A[1...n])
if n = 2
    if A[1] > A[2]
        Swap(A[1], A[2])
else if n > 2
    SlowSort(A[1...(2n/3)])
    SlowSort(A[(n/3+1)... n])
    SlowSort(A[1...(2n/3)])

The recursive calls are the bits I'm having a problem with. I was thinking about creating two new arrays that point to the wanted locations but don't know how to go about that, specifically doing that and defining the length of the array. I've tried googling it and searching this site, but there doesn't seem to be anything, that I understand, on it. Also, in case I fudged up somewhere in my code, here's what I have for the first bit.

int SlowSort(int A[])
{
int length = (sizeof(A)/sizeof(*A));
    if(length ==2)
    {
        if(A[0] > A[1])
        {
            int temp = A[0];
            A[0] = A[1];
            A[1] = temp;
        }
    }

In short, how do In covert the else if statement into C++? Explanation would be nice too.

Thanks

Upvotes: 1

Views: 203

Answers (4)

Yakk - Adam Nevraumont
Yakk - Adam Nevraumont

Reputation: 275966

The modern C++ way to do this would be to pass iterators to the beginning and one-past-the-end of the range. In this case, the iterators are pointers.

void SlowSort(int* begin, int* end)
{
  unsigned length = end-begin;
  if(length == 2)
  {
    if(begin[0] > begin[1])
    {
      std::swap( begin[0], begin[1] );
    }
  } else if(length>2) {
    SlowSort(begin, begin+2*length/3);
    SlowSort(begin+length/3, end);
    SlowSort(begin, begin+2*length/3);
  }
}

then, for the case of working with an entire array:

template<unsigned N>
void SlowSort( int(&Arr)[N] ) {
  return SlowSort( Arr, Arr+N );
}

we dispatch it to the iterator version, relying on decaying of array-to-pointer. This has to be a template function, as we want it to work with multiple different array sizes.

Note that an int Arr[] is not an array. It is a different way to say int* Arr, left over as a legacy from C. In fact, as a parameter to a function, saying void foo( int A[27] ) results in void foo( int* A ): function parameters cannot be arrays.

They can, however, be references-to-arrays, which is what the above template function uses.

Upvotes: 2

BrainStone
BrainStone

Reputation: 3205

This is pretty simple. Since arrays are just consecutive pointers. If you have a method:

Your code would look like this:

void slowSort(int[] array, int length)
{
    if(length == 2)
    {
        if(array[0] > array[1])
        {
            int temp = array[0];
            array[0] = array[1];
            array[1] = temp;
        }
    }
    else
    {
        slowSort(&array[0], (2 * length) / 3 - 1);
        slowSort(&array[length / 3], length - (length / 3 - 1));
        slowSort(&array[0], (2 * length) / 3 - 1);
    }
}

The trick I use here is that I pass the pointer of the element I want to start with and the pass the end point.

This works because when you pass an array in C++ you just pass the pointer of the first element. Here I pass a custom pointer of the array.

Upvotes: 2

Vlad from Moscow
Vlad from Moscow

Reputation: 311146

You simply pass required pointer using the pointer arithmetic. For example the following pseudo code 

SlowSort(A[(n/3+1)... n])

could be written as

SlowSort( A + n/3+1,  n - n/3 - 1 );

So the function could be declared as

void SlowSort( int A[], size_t n );

As for this code snippet

int SlowSort(int A[])
{
int length = (sizeof(A)/sizeof(*A));

then it is invalid because array is implicitly converted to a ponter to its first element when it is passed as an argument to a function seclared such a way. So the value of length will not be equal to the number of elements.

Upvotes: 2

user2033018
user2033018

Reputation:

You will want to pass indices into the array instead, and use those.

void SlowSort(int A[], int left, int right)
{
    if (right - left == 2)
        if (A[left] > A[right])
            Swap(A[left], A[right]);
    else
    {
        int n = right - left + 1;
        SlowSort(A, left, 2 * n / 3);
        SlowSort(A, left + n / 3 + 1, right);
        SlowSort(A, left, left + 2* n / 3);
}

The above code might not be correct regarding what the algorithm is supposed to do, but you get the idea I'm trying to describe. The thing is: you don't make a copy of the array. Instead, pass the same array always and the range (i.e. the indices) you are sorting.

Upvotes: 6

Related Questions