Array sorting...

[soranz]

I have 2 arrays with the exact same elements but a few extra zeros in the wrong places. The relative order of the numbers is always the same.

Array 1 = {1, 3, 0, 55, 33, 0, 5, 99}
Array 2 = {1, 3, 55, 33, 5, 99, 0, 0}

What's a good way to sort array 2 so that it matches up with array 1?

My attempts have led to some ugly loops....

[Disch]

If you know the arrays have the same elements, why do you need to sort? Can't you just copy?

std::copy( array1, array1 + arraysize, array2 );

[soranz]

err oops i worded that wrong. I should have added that Array 2 is being used as an index to determine how to sort an Array 3. So, i do need to know how many spots each element of Array 2 is being shifted to lineup with Array 1.

[HiteshVaghani1]

You are not still clear about your question to others..

[Gaminic]

I'm not sure I follow. How do array 1 and array 2 relate to array 3? Are those values indeces or priorities/weights?

If indeces: How do you use one array with 8 elements to sort an array with at least 100 elements?

If priorities: You're not sorting, because the priorities in array 1 aren't sorted. There is no logical way to get the sequence in Array 1.


Using your last sentence ("being shifted"), I'd say something likes this:

int index1 = 0, index2 = 0;    // Start at beginning of both arrays

while (array2[index2] != 0) {    // Loop through non-zero elements of ar1
    int shifts = 0;
    while (array1[index1] != array2[index2]) {   // Count zeroes
        shifts++;
        index2++;
    }
    cout << "Element " << index1 << " is shifted " << shifts << " times.\n";
    index1++;    // Go to next element of ar1
}

Replace the cout with whatever purpose.

[soranz]

OK I'll try again. I have 2 arrays. Namely,

Array 1 = {1, 3, 0, 55, 33, 0, 5, 99}
Array 2 = {1, 3, 55, 33, 5, 99, 0, 0}

I want Array 2 shifted such that it is equal to Array 1.

Array 1 = {1, 3, 0, 55, 33, 0, 5, 99}
Array 2 = {1, 3, 0, 55, 33, 0, 5, 99}

Somewhere through this shift, I want to know how each element from Array 2 moved.

So in the example, Array 2's elements moved as follows:

[0]: 0
[1]: 0
[2]: +1 (element 2 (ie: 55) moved to element 3 and element 2 is set to 0)
[3]: +1 (element 3 (ie: 33) moved to element 4)
[4]: +2 (element 4 (ie: 5) moved to element 6 and element 5 is set to 0)
[5]: +2 (element 5 (ie: 99) moved to element 7)
[6]: -4 (element 6 (ie: 0) moved to element 2)
[7]; -2 (element 7 (ie: 0) moved to element 5)

To make it easier, element [0] has always the same value for both arrays...
Thanks again

[HiteshVaghani1]

i almost succeed but occurrence of '0' is more than one time causes the problem.

[HiteshVaghani1]

int main()
{
    int a[8] = {1, 3, 0, 55, 33, 0, 5, 99};
    int b[8] = {1, 3, 55, 33, 5, 99, 0, 0};
    int shift[8];
    int index = 0,track = 0;
    int morethanone = 0;

    for (int i=0; i<8/*Number of array element*/; i++)
    {
        if(a[i] != b[i])
        {
            for(int j=0;j<8;j++)
            {
                if(b[i] == a[j])
                {
                    shift[index++] = j - i;
                    morethanone++;
                    if(morethanone > 1)
                        track++;
                    if(track > 1)
                        shift[index - morethanone] = j - i;
                }
            }
            if(morethanone > 1)
            {
                index = index - morethanone + 1;
            }
            morethanone = 0;
        }
        else
            shift[index++] = 0;
    }

    
    for(int i=0;i<8;i++)
    {
        cout << i << "  "<<shift[i]<<endl;
    }
    getchar();
    return 0;
}

[ne555]

For every element in the array, you find the position in the reference.
However, that gives issues with repeated elements. You could just kill it when you found it.

[soranz]

Hey

HiteshVaghani1

I'm getting a corruption of stack error for shift[] that occurs after the return and it doesn't seem to work for 'n' zeros ?

***UPDATE***
I was able to sort array2 for all cases that the zeros of array2 are relatively deeper than array1. I think I should be able to add another 'if clause' and do a sort in the opposite direction for the cases where array2 has a zero earlier than array1 by rotating the subarray in the opposite direction... Getting the 'shift' should be trivial now too.

int AOne[9] = {1, 33, 0, 0, 55, 22, 0, 66, 99}
int Atwo[9] = {1, 33, 55, 22, 0, 66, 0, 99, 0}
bool bShiftZero = false;

//THIS aligns all elements from Atwo with Aone ONLY if all zeros in A2 are relatively deeper than those in A1
for(int k=2; k<=8; k++)	//start with element 1 since element 0 is aligned
{
       //THIS find the first zero in the target array 
	if(Aone[k] == 0)
	{	
		//THIS finds the first 0 element from the top
		for(int w=k; w<=8; w++)	
		{	
			if(bShiftZero == true)
			{
				bShiftZero = false;
				break;	//only shift down the zero ONCE
			}
			if(Atwo[w] == 0)
			{
				//THIS shifts all elements of the sub array UP by 1 based on the first ~
                               //    ~ zero encountered in direction towards max element
				for(int z=w; z>=k; z--)
				{								
                                     Atwo[z] = Atwo[z-1];  									
				}
				bShiftZero = true; //only shift for 1 zero at a time
				Atwo[k] = 0;	//set the target element to 0 AFTER the loop
			}
		}
	}
       if(Atwo[k] == 0)
       {
                 //.........do sorting of sub arrays in opposite direction
        }
}

[HiteshVaghani1]

of course it won't work for n '0'.
What if repeated number is other than ''0'. will it work for that or it won't be the case ?

[soranz]

no, only the existence of the number of '0's is guaranteed and element[0] of each array are the same. Also, the sequence of nonzero numbers is assumed to be in the same ordering (as shown below).The other nonzero elements from [1] to [n<20] may or may not exist in both arrays but they have to be sorted with the assumption that they are the same based on the positions of the zeros in Array one and the fact that element[0] is shared in each array.

That is, removing all zeros and shifting all elements to the right should yield the same array:

int AOne[9] = {1, 33, 0, 0, 55, 22, 0, 66, 99};
int Atwo[9] = {1, 33, 55, 22, 0, 66, 0, 99, 0};

AOne[9] = {1, 33, 55, 22, 66, 99};
Atwo[9] = {1, 33, 55, 22, 66, 99};

So, this would fail and it's ok if it fails:

AOne[9] = {1, 33, 0, 0, 55, 22, 0, 66, 99};
Athree[9] = {1, 33, 0, 22, 0, 55, 0, 66, 99};