Skip to content

Instantly share code, notes, and snippets.

@2manoj1
Last active April 27, 2020 14:28
Show Gist options
  • Save 2manoj1/75ad3a671061c50e6d237bf66741fba7 to your computer and use it in GitHub Desktop.
Save 2manoj1/75ad3a671061c50e6d237bf66741fba7 to your computer and use it in GitHub Desktop.
All zero at tail of array
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)
@2manoj1
Copy link
Author

2manoj1 commented Apr 27, 2020

output -->

Before Sort -> 2,0,3,4,5,4,0,0,0,3,0,2,8,9,0,0,1,1,0
after Sort ->  9,8,5,4,4,3,3,2,2,1,1,0,0,0,0,0,0,0,0 

Before Sort -> 0,0,0,0,0,2,2,2,2,2,0,-1
after Sort ->  2,2,2,2,2,-1,0,0,0,0,0,0 

Before Sort -> 0,0,0,2,2,2,2,2,2,2
after Sort ->  2,2,2,2,2,2,2,0,0,0

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment