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.
