Last active
April 27, 2020 14:28
-
-
Save 2manoj1/75ad3a671061c50e6d237bf66741fba7 to your computer and use it in GitHub Desktop.
All zero at tail of array
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
const a0 = [2, 0, 3, 4, 5, 4, 0, 0, 0, 3, 0, 2, 8, 9, 0, 0, 1, 1, 0]; | |
const a1 = [0, 0, 0, 0, 0, 2, 2, 2, 2, 2, 0, -1]; | |
const a2 = [0, 0, 0, 2, 2, 2, 2, 2, 2, 2]; | |
const merge = (left, right) => { | |
let resArr = [], zeroArr = [], lIndex = 0, rIndex = 0; | |
while (lIndex < left.length && rIndex < right.length) { | |
if (left[lIndex] === 0) { | |
zeroArr.push(0); | |
lIndex++; | |
} | |
else if (right[rIndex] === 0) { | |
zeroArr.push(0); | |
rIndex++; | |
} | |
else if (left[lIndex] !== 0 && right[rIndex] !== 0) { | |
// Sort Descending order if its not zero | |
if (left[lIndex] <= right[rIndex]) { | |
resArr.push(right[rIndex]); | |
rIndex++; // move right pivot | |
} | |
else { | |
resArr.push(left[lIndex]); | |
lIndex++; // move left pivot | |
} | |
} | |
else { | |
// Left and right both zero | |
zeroArr.push(0); | |
lIndex++; // move left pivot | |
rIndex++; // move right pivot | |
} | |
} | |
const leftSliceArray = left.slice(lIndex); | |
const rightSliceArray = right.slice(rIndex); | |
// Merge rest of element and zero at last | |
resArr = [...resArr, ...leftSliceArray, ...rightSliceArray, ...zeroArr] | |
return resArr; | |
} | |
// | |
//-> Not using some or every array function | |
// Is all array elemt zero or not | |
const isArrAllZero = (unsortedArray) => { | |
let index = 0; | |
while (index < unsortedArray.length) { | |
if (unsortedArray[index] !== 0) { | |
return false; | |
} | |
index++; | |
} | |
return true; | |
} | |
// If array size <=1 or all elemnt zero no need to sort | |
const mergeSortZero = (unsortedArray) => { | |
if (unsortedArray.length <= 1 || isArrAllZero(unsortedArray)) { | |
return unsortedArray; | |
} | |
// Middle of Array, [0,0,0,0,0,2,2,2,2,2,0] -> 11/2 = 5.5 => 5 | |
const middle = Math.floor(unsortedArray.length / 2); // Divide | |
// left and right Array divided using slice method | |
const leftArr = unsortedArray.slice(0, middle); // startIndex, length | |
const rightArr = unsortedArray.slice(middle); // From middle to rest element | |
// recusive function to merge and sort | |
return merge( | |
mergeSortZero(leftArr), mergeSortZero(rightArr) | |
); | |
} | |
const res0 = mergeSortZero(a0); | |
const res1 = mergeSortZero(a1); | |
const res2 = mergeSortZero(a2); | |
console.log(`Before Sort -> ${a0} | |
after Sort -> ${res0} \n`); | |
console.log(`Before Sort -> ${a1} | |
after Sort -> ${res1} \n`); | |
console.log(`Before Sort -> ${a2} | |
after Sort -> ${res2} \n`); | |
/* | |
console.log(`Test isArrAllZero function with [0, 0, 0] ${isArrAllZero([0,0,0])}`) | |
console.log(`Test isArrAllZero function with [0, 1, 0] ${isArrAllZero([0,1,0])}`) | |
console.log(`Test isArrAllZero function with [1, 0, 0] ${isArrAllZero([1,0,0])}`) | |
console.log(`Test isArrAllZero function with [0, 0, 1] ${isArrAllZero([0,0,1])}`) | |
*/ | |
//Time Coplexcity merge sort -> O(nLogn) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
output -->