Array #DataStructureAlgorithms

merge-sort-array.js

// Merge two arrays
function merge(arr1, arr2) {
	var res = []
	while (arr1.length > 0 && arr2.length > 0) {
		if (arr1[0] < arr2[0]) {
			res.push(arr1.shift())
		} else {
			res.push(arr2.shift())
		}
	}
	return [...res, ...arr1, ...arr2]
}

// Recurssive Merge Sort
function mergeSort1(arr) {
	var len = arr.length
	if (len < 2) return arr
	var mid = Math.floor(len/2)
	var left = arr.slice(0, mid)
	var right = arr.slice(mid)
	return merge(mergeSort1(left), mergeSort1(right))
}

// Iterative Merge Sort
function mergeSort2(arr) {

	var result = arr.map(item => [item])
	
	while (result.length > 1) {
		var temp = []
		var isOddNumber = (result.length % 2 !== 0)
		for (var i = 0; i < result.length; i += 2) {
			var a = result[i]
			var b = result[i + 1]
			if (isOddNumber && i === result.length - 3) {
				b = merge(result[i + 1], result[i + 2])
				i++
			}
			temp.push(merge(a,b))
		}
		result = temp
	}
	return result[0]
}

console.log(mergeSort1([3,2,9,1,4,5]))
console.log(mergeSort2([3,2,9,1,4,5]))

search-element-in-sorted-and-rotated-array.js

// Search an element in a sorted and rotated array

function searchElement(arr, value, left=0, right) {
	if (!right) right = arr.length
	var mid = Math.floor(left + (right - left)/2)
	if (arr[mid] === value) {
		return mid
	}
	if (arr[left] < arr[mid]) {
		if (value >= arr[left] && value <= arr[mid]) {
			return searchElement(arr, value, left, mid - 1)
		}
		return searchElement(arr, value, mid + 1, right)
	} else {
		if (value >= arr[mid] && value <= arr[right]) {
			return searchElement(arr, value, mid + 1, right)
		}
		return searchElement(arr, value, left, mid - 1)
	}
}

console.log(searchElement([5,6,7,8,9,10,1,2,3],2))

search-two-elements-in-array-whose-sum-is-closest-to-zero.js

// Search wo elements in array whose sum is closest to zero

function minAbsSumPair (arr) {

	// Sort array
	arr.sort((a,b) => {
		return a - b
	})

  	// Keep track of min_left and min_right
	var min_left = left = 0
	var min_right = right = arr.length - 1
	var min = Math.abs(arr[min_left] + arr[min_right])

    // Two pointers
	while (left < right) {
		var total = arr[left] + arr[right]
		if (Math.abs(total) < min) {
			min = Math.abs(total)
			min_left = left
			min_right = right
		}
		if (total > 0) right--
		if (total < 0) left++
	}
	
	return [arr[min_left], arr[min_right]]

}

console.log(minAbsSumPair([1,60,-10,70,-80,85,100]))