c++arrays

Rearrange negative values to the left and positive values to the right in an array


I am going along with an online C++ video tutorial. At one point, I tried to write code for the problem described on this question title. Later, the instructor shows his approach and I could not decide which code is better since both give the same result.

#include <iostream>
using namespace std;
// Array construction

struct Array {
    int A[10];
    int size;
    int length;
};

void Swap(int *des, int *source) {
    int temp = *des;
    *des = *source;
    *source = temp;
}

Instructor's implementation:

void Rearrange(Array* arr)
{
    int i = 0;
    int j = arr->length - 1;
    while (i < j) {
        while (arr->A[i] < 0)
            i++;
        while (arr->A[i] >= 0)
            j--;
        if (i < j)
            Swap(&arr->A[i], &arr->A[j]);
    }
}

My implementation:

void ArrangeNegativeOnLeft(Array *arr) {
    int i = 0;
    int j = arr->length - 1;
    while (i < j) {
        if (arr->A[i] < 0)
            i++;
        if (arr->A[j] >= 0)
            j--;
        if (i < j) {
            Swap(&arr->A[i], &arr->A[j]);
        }
    }
}

Main

int main(){
    Array r = { {2,-15, 3,-10,5,6,-44, 55}, 10, 8 };
    //Rearrange(&r);
    ArrangeNegativeOnLeft(&r);

    // Display

    cout << "\n Elements are:\n";
    for (int i = 0; i < arr.length; i++) 
        cout << arr.A[i] << " ";
    cout << endl;
}

Solution

  • Notes:

    Don't like passing pointers around, but lets assume references are a later class.

    Don't like custom Swap() and custom Array types. Assume you are learning from the bottom and have not got to the standard libraries yet.

    Looking at the instructors code:

    void Rearrange(Array* arr)
    {
        int i = 0;
        int j = arr->length - 1;
        while (i < j) {
            while (arr->A[i] < 0)
                i++;
            while (arr->A[i] >= 0) // I will assume this is a typo from your and that index is j
                j--;
            if (i < j)
                Swap(&arr->A[i], &arr->A[j]);
        }
    }`
    

    Issues I have:

    while (arr->A[i] < 0)      // If the array does not contain any positive numbers this
                               // will not terminate correctly. So you do need an additional
                               // check to make sure it works:
    
    
    // Solved by this test.
    while (i < j && arr->A[i] < 0)
    

    Advantages of using while in instructors code over if in your code.

    Using the if rather than a while does not work the way you think it does. Because you only skip one value at a time and always do a swap at the end of the loop, you can swap values into the wrong place. Using your code the following happens:

    Start:

     -1 -2 -3 3 2 1                // Skip one place -1, 1 are in correct place.
    

    First Iteration:

     -1 2 -3 3 -2 1                // swap the -2 and 2
    

    Second iteration:

    -1 -2 -3 3 2 1                 // Swap them back
    

    Third Iteration:

    -1 -2 3 -3 2 1                 // Now we move on and swap the 3
    

    Fourth Iteration:

    -1 -2 -3 3 2 1                 // Swap them back
    

    Using the Instructors code:

    Start: -1 -2 -3 3 2 1

    Exit.