2
\$\begingroup\$

If given two arrays

arrayOne = [3,6,-1,11,15,-1,32,34,-1,42,-1]
arrayTwo = [1,10,17,56]

Both the array's are sorted but array1 consists -1 in between the sorted numbers.

Now to problem is to merge numbers present in array2 into array1 so that array1 should be sorted and should not contain -1.

i.e.

arrayOne =  [ 1, 3, 6, 10, 11, 15, 17, 32, 34, 42, 56 ]

For the above problem I created one algorithm it is as follows,

step1 : iterate through array2, compare with number present in array1, if number in array2 is less and number in array1, than swap the numbers.

step2 : continue iterating through array1 till -1 occures, now swap.

step3 : got to step1.

so the working of above algorithm is as follows,

step1,

array1 = [3,6,-1,11,15,-1,32,34,-1,42,-1]
array2 = [1,10,17,56]

step2(swaped):

array1 = [1,6,-1,11,15,-1,32,34,-1,42,-1]
array2 = [3,10,17,56]

step3(swaped)

array1 = [1,3,-1,11,15,-1,32,34,-1,42,-1]
array2 = [6,10,17,56]

step4(swaped)

array1 = [1,3,6,11,15,-1,32,34,-1,42,-1]
array2 = [-1,10,17,56]

step5(swaped)

array1 = [1,3,6,10,15,-1,32,34,-1,42,-1]
array2 = [-1,11,17,56]

Continue as above,

The code for above problem is

puzzle02([3,6,-1,11,15,-1,32,34,-1,42,-1],[1,10,17,56]);

function puzzle02(arrayOne,arrayTwo){   
    var array1Counter = 0,
        array2Counter = 0,       
        hasMinusOneOccurred = false;

    console.log(" array-1 ",arrayOne);
    console.log(" array-2 ",arrayTwo);  


    while(array2Counter < arrayTwo.length){ // iterate through array2

        do{
            if(arrayOne[array1Counter] === -1){ // if -1 occurred in array1
                hasMinusOneOccurred = true;

                // swaping numbers at current position of array1
                // with current position of array2 
                swap(arrayOne,arrayTwo,array1Counter,array2Counter);

                // recheck if the current value is greater than other values
                // of array1
                if(recheckAndSort(arrayOne,array1Counter) === true){
                    array1Counter = -1;// recheck array1 from start
                }else{
                    // recheck the current array1 counter, for doing so go 1 count back
                    // so that even if the counter is incremented it points to current
                    // number itself 
                    array1Counter--; 
                }

            }else if(arrayOne[array1Counter] > arrayTwo[array2Counter]){
                swap(arrayOne,arrayTwo,array1Counter,array2Counter);
            }else{
                array1Counter++;
                continue;   
            }

            array1Counter++;            
        }while(hasMinusOneOccurred === false); // end of do-while

        array2Counter++;
        hasMinusOneOccurred = false;

    }//end of while

    console.log(" Sorted array ",arrayOne);

    function swap(arr1,arr2,arr1Index,arr2Index){
        var temp = arr2[arr2Index];
        arr2[arr2Index] = arr1[arr1Index];
        arr1[arr1Index] = temp;
    }// end of swap 

    // this method is call if -1 occures in array1
    function recheckAndSort(arrayOne,array1Counter){
        var isGreaterVal = true,
            prevCounter = 0,
            nextCounter = 0,
            temp = 0,
            recheckFromStart = false;


        if(array1Counter === 0){ // if -1 occurred at first position of array1.

            // flag to check if -1 occurrec at first position
            // if yes, iterate array1 from start
            recheckFromStart = true; 

            // iterate forward to check wether any numbers are less than current position,
            // if yes than move forward
            for(var j = 0; isGreaterVal; j++){
                nextCounter = j + 1;

                if(arrayOne[nextCounter] === -1){
                    // swaping numbers of array1 between next to current                    
                    swap(arrayOne,arrayOne,nextCounter,j);
                    isGreaterVal = true; 

                }else if(arrayOne[nextCounter] < arrayOne[j]){
                    // swaping numbers of array1 between next to current
                    swap(arrayOne,arrayOne,nextCounter,j);
                    isGreaterVal = true;

                }else{
                    isGreaterVal = false;
                }

            }//end of for

        }else{// if -1 occurred in the middle position of array1 and is been swaped then
            // iterate backwards to check if any number less then current position exists,
            // if yes than shift backwards.
            for(var i = array1Counter; isGreaterVal; i--){
                prevCounter = i - 1;

                if(arrayOne[prevCounter] > arrayOne[i]){

                    // swaping numbers of array1 between previous to current                    
                    swap(arrayOne,arrayOne,prevCounter,i);
                    isGreaterVal = true; 
                }else{
                    isGreaterVal = false;
                }

            }// end of for  
        }

        return recheckFromStart;        
    }// end of recheckAndSort
} // end of puzzle02

The output of above code is

array-1  [ 3, 6, -1, 11, 15, -1, 32, 34, -1, 42, -1 ]
array-2  [ 1, 10, 17, 56 ]
Sorted array  [ 1, 3, 6, 10, 11, 15, 17, 32, 34, 42, 56 ]

Please review my code, and give your valuable feedback.

Can my logic as explained above can be improved further or is there a better solution of the above problem

Please suggest me.

\$\endgroup\$
1
\$\begingroup\$

I have a couple of thoughts I wanted to share after taking some time to work through this problem.

  1. Your code has a potential bug: If I add any elements to "array-2", the while loop becomes an infinite loop.
  2. If you want to extend some functionality to your code, add a 3rd array as an argument. This array will contain all the values you want to filter out. Then write up a subroutine to filter out those values.
  3. Another way to extend the code would be to add a "checking" function that can ensure that all the arrays entered are in numerical order before running through the merge sort algorithm. I didn't add this to mine, but it could add some a level of robustness that doesn't exist now.

I took a shot at writing up a version of this code, you can check it out if you want to compare notes.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.