Implementations of common sorting algorithms

sorting_algos.js

/**
 * Naive sort - Quadratic time, nested  loops
 * Divide & Comquer - O(nlogn)
 */

module.exports = {

	bubbleSort () {

	},

	bubbleSortForNumbers (list, reversed=false) {
		for (let i = 0; i < list.length; i++) {
			for (let j = i+1; j < list.length; j++) {
				console.log(`${list} ==> comparing indices: ${i} and ${j}`)
				condition = reversed
				? list[i] < list[j]
				: list[i] > list[j]

				if (condition) {
					// swap
					this.swap(list, i, j)
					console.log(`${list} swapping list ==> ${i} and ${j}`)
				}
			}
		}
		return list
	},

	bubbleSortBasic (array) {
		for (let i = 0; i < array.length; i++) {
			for (let j = 1; j < array.length; j++) {
				if (array[j-1] > array[j]) {
					this.swap(array, j-1, j)
				}
			}
		}
		return array
	},

	buubleSortOptimized (list) {
		let swapped;
		do { swapped = false;
			for (let i = 0; i < list.length; i++) {
				if (list[i] && list[i+1] && list [i] > list[i+1]) {
					this.swap(list, i, i+1)
					swapped = true
					// console.log(`swapping list ==> ${i} and ${i+1}`)
				}
			}
		} while (swapped)
		console.log(list)
		return list
	},

	swap (array, i, j) {
		[array[i], array[j]] = [array[j], array[i]]
		// temp = array[i]
		// array[i] = array[j]
		// array[j] = temp
	},

	insertionSort () {

	},

	heapSort () {

	},

	selectionSort () {

	},

	// initialize empty array
	// compare the first index of L to first index of R
	// push the lower value to empty array
	// shift the main original array (remove the first one)
	// repeat until both L and R arrays are empty 
	// 
	// pseudo code
	// mergeSort(list)
	// base case: if list.length < 2, return
	// break the list into halves L and R
	// Lsorted = mergeSort(L)
	// Rsorted = mergeSort(R)
	// return merge(Lsorted, Rsorted)
	mergeSort (list) {
		if (list.length < 2) {
			return list
		} else {
			// break it in two halves
			let mid = Math.floor(list.length / 2)
			let l = list.slice(0, mid)
			let r = list.slice(mid)

			let lSorted = this.mergeSort(l)
			let rSorted = this.mergeSort(r)
			return this.merge(lSorted, rSorted)
		}
	},

	merge (l, r) {
		// checkout: https://hackernoon.com/programming-with-js-merge-sort-deb677b777c0
		const final = [] 
		while (l.length > 0 || r.length > 0) {
			if (l.length > 0 && r.length > 0) {
				let smallest = l[0] < r[0] ? l.shift() : r.shift()
				final.push(smallest)
			} else {
				if (l.length === 0) {
					final.push(r.shift())
				} else if (r.length === 0) {
					final.push(l.shift())
				}
			}
		}
		return final
	},

	quickSort (list) {
		let len = list.length
		if (len <= 1) {
			return list;
		} else {
			let prev = list[0];
			let right = []
			let left = []

			for (var i = 1; i < list.length; i++) {
				if (list[i] < prev) {
					left.push(list[i])
				} else {
					right.push(list[i])
				}
			}
			return this.quickSort(left).concat([prev]).concat(this.quickSort(right))
		}
	}
}