Skip to content

Instantly share code, notes, and snippets.

@motss

motss/insertion-sort.js

Last active August 29, 2019 06:21
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save motss/0d6a04e76d39ed59c99082b62d700839 to your computer and use it in GitHub Desktop.
Save motss/0d6a04e76d39ed59c99082b62d700839 to your computer and use it in GitHub Desktop.
Download ZIP
Sorting
Raw
insertion-sort.js
// i
// j
// 4 2 1 3 6 0
// i
// j
// 4 2 1 3 6 0
// 2 4 1 3 6 0 # 2 < 4
// i
// j
// 2 4 1 3 6 0
// 2 1 4 3 6 0 # 1 < 4
//
// i
// j
// 2 4 1 3 6 0
// 1 2 4 3 6 0 # 1 < 2
// i
// j
// 1 2 4 3 6 0
// 1 2 3 4 6 0 # 3 < 4
// i
// j
// 1 2 4 3 6 0
// 1 2 3 4 6 0
//
// i
// j
// 1 2 4 3 6 0
// 1 2 3 4 6 0
// i
// j
// 1 2 3 4 6 0
// ... skip
// i
// j
// 1 2 3 4 6 0
// 1 2 3 4 0 6 # 0 < 6
//
// i
// j
// 1 2 3 4 0 6
// 1 2 3 0 4 6 # 0 < 4
//
// i
// j
// 1 2 3 0 4 6
// 1 2 0 3 4 6 # 0 < 3
// ... skip
// 0 1 2 3 4 6 # 0 < 1
// Time complexity: O(n ^ 2) as while traversing n elements, we traverse n - 1 elements to compare every elements.
// Space complexity: O(1) as it is done in-place and only a few variable assignments
function insertionSort(x) {
const len = x.length;
for (let i = 1; i < len; i += 1) {
let j = i; // current element
let k = i - 1; // previous element
while (k >= 0) { // Comparison is done when k is >= 0 as x[k] is undefined when k is -1 when j is 0.
// If current element, x[j] is >= previous element, x[k], bails out.
// It is safe to do so, since at j, anything before j will be sorted.
// So by doing just one comparion with previous element suffice.
if (x[j] >= x[k]) break;
// swap elements
[x[j], x[k]] = [x[k], x[j]]
j -= 1;
k -= 1;
}
}
return x;
}
function isSortedArray(x) {
const len = x.length;
for (let i = 0; i < len; i += 1) {
if (x[i] < x[i - 1]) return false;
}
return true;
}
function main() {
const a = [
[4, 2, 1, 3, 6, 0],
[-7, -3, -9, -5, -8, 2, 3, 9, 1, -1],
[-4, 12, 7, 6, 12, 2, 0, -1, 1, -3],
[3, 6, 8, 17, 7, -3, -4, 9, 9, 6],
[1, -5, 15, 14, 5, 10, 7, 0, 4, 3],
[7, -4, 2, 6, 7, 2, 6, 11, 9, 3],
[1, -4, 7, 4, 1, 13, 8, 1, 2, -1],
[-6, 11, 8, -2, 15, 4, 9, 7, 3, 1],
[10, -3, -1, -4, 0, 2, -1, -2, -4, 9],
[14, 10, 0, 10, -3, 6, 1, 8, -6, 5],
[-3, 10, 3, 9, 5, 4, 9, 8, 3, 0],
];
a.forEach((n) => {
const sorted = insertionSort(n);
console.log(isSortedArray(sorted), sorted);
});
}
console.clear();
main();
Raw
merge-sort.js
// Time complexity: O(n) or O(max(len(x), len(y)) whichever is longer. That's the total number of times we need traverse both the arrays
// Space complexity: O(n) as new sorted array to contain all elements (x + y)
function concatTwoSortedArrays(x, y) {
const xLen = x.length;
const yLen = y.length;
const merged = [];
let xi = 0;
let yi = 0;
while (xi < xLen || yi < yLen) { // xi or yi starts from 0, so loop until both rearch their len
// Either xn or yn is null, we know that the array has nothing needs to be compared,
// we can safely push the rest of the elements in another array into `merged`
let xn = xi < xLen ? x[xi] : null;
let yn = yi < yLen ? y[yi] : null;
if (null != xn && null != yn) {
if (xn < yn) { merged.push(xn); xi += 1 }
if (yn <= xn) { merged.push(yn); yi += 1; } // merging 2 possibilities: yn < xn or yn === xn
} else if (null == xn) {
merged.push(yn);
yi += 1;
} else {
merged.push(xn);
xi += 1;
}
}
return merged;
}
// Time complexity: O(n * log(n)) as based on Master Theorem, T(n) = a * T(n / b) + f(n)
// Given that f(n) is O(n) for `concatTwoSortedArrays`,
// a = 2 as `x` being split in half,
// b = 2 as arrays continue splitting until it has <= 2 elements,
// Hence, T(n) = 2 * T(n / 2) + O(n).
// Recursion takes n ^ log_b^a = n ^ log_2^2 = n ^ 1 = O(n) time.
// Since both recursion and work done outside recursion takes O(n),
// the formula is O(n ^ log_b^a * log(n)). By substituting a = 2, b = 2, into the formula,
// we get O(n * log(n)).
//
// Space complexity: O(n) where n is the number of elements in a new array after merge and sort.
function mergeSort(x) {
const len = x.length;
if (1 === len) return x;
if (2 === len) {
if (x[0] > x[1]) [x[0], x[1]] = [x[1], x[0]];
return x;
}
let l = 0;
let r = len;
const mid = Math.floor((l + (r - l)) / 2);
// `concatTwoSortedArrays` takes O(n) time while recursive `mergeSort` takes O(log(n)) time to split arrays into half
// While recursion is happening here, it basically means that there is a recursive call stack up to log(n) before
// `concatTwoSortedArrays` takes place. So the space complexity, specifically, is O(log(n) + n). But O(n) > O(log(n)).
// The final space complexity will be O(n) for new created array.
return concatTwoSortedArrays(mergeSort(x.slice(l, mid)), mergeSort(x.slice(mid, r)));
}
function isSortedArray(x) {
const len = x.length;
for (let i = 0; i < len; i += 1) {
if (x[i] < x[i - 1]) return false;
}
return true;
}
function main() {
const a = [
[4, 2, 1, 3, 6, 0],
[-7, -3, -9, -5, -8, 2, 3, 9, 1, -1],
[-4, 12, 7, 6, 12, 2, 0, -1, 1, -3],
[3, 6, 8, 17, 7, -3, -4, 9, 9, 6],
[1, -5, 15, 14, 5, 10, 7, 0, 4, 3],
[7, -4, 2, 6, 7, 2, 6, 11, 9, 3],
[1, -4, 7, 4, 1, 13, 8, 1, 2, -1],
[-6, 11, 8, -2, 15, 4, 9, 7, 3, 1],
[10, -3, -1, -4, 0, 2, -1, -2, -4, 9],
[14, 10, 0, 10, -3, 6, 1, 8, -6, 5],
[-3, 10, 3, 9, 5, 4, 9, 8, 3, 0],
];
a.forEach((n) => {
const sorted = mergeSort(n);
console.log(isSortedArray(sorted), sorted);
});
}
console.clear();
main();
Raw
quick-sort.js
// left = l = 0, right = h = 8, mid = floor((0 + 8) / 2) = 4, pivot = x[4] = 8:
// l
// h
// -1 0 1 2 *8 3 7 6 4 # l++;
// 0 1 2 3 4 5 6 7 8
//
// l
// h
// -1 0 1 2 *8 3 7 6 4 # l++;
//
// l
// h
// -1 0 1 2 *8 3 7 6 4 # l++;
//
// l
// h
// -1 0 1 2 *8 3 7 6 4 # l++;
//
// l
// h
// -1 0 1 2 *8 3 7 6 4 # l <= h. swap l, h; l++, h--;
//
// l
// h
// -1 0 1 2 4 3 7 6 *8 # l++;
//
// l
// h
// -1 0 1 2 4 3 7 6 *8 # l++;
//
// l
// h
// -1 0 1 2 4 3 7 6 *8 # l++;
//
// l
// h
// -1 0 1 2 4 3 7 6 *8 # l++; # l = 8; Return l as i.
// 0 1 2 3 4 5 6 7 8
// left = l = 0, right = h = i - 1 = 8 - 1 = 7, mid = floor((0 + 7) / 2) = 3, pivot = x[3] = 2:
//
// l
// h
// -1 0 1 *2 4 3 7 6 8 # l++;
// 0 1 2 3 4 5 6 7 8
//
// l
// h
// -1 0 1 *2 4 3 7 6 8 # l++;
//
// l
// h
// -1 0 1 *2 4 3 7 6 8 # l++;
//
// l
// h
// -1 0 1 *2 4 3 7 6 8 # h--;
//
// l
// h
// -1 0 1 *2 4 3 7 6 8 # h--;
//
// l
// h
// -1 0 1 *2 4 3 7 6 8 # h--;
//
// l
// h
// -1 0 1 *2 4 3 7 6 8 # l >= h. swap l, h; l++, h--;
//
// l
// h
// -1 0 1 *2 4 3 7 6 8 # l = 4; Return l as i.
// 0 1 2 3 4 5 6 7 8
// left = l = 0, right = h = i - 1 = 4 - 1 = 3, mid = floor((0 + 3) / 2) = 1, pivot = x[1] = 0:
// l
// h
// -1 *0 1 2 4 3 7 6 8 # l++;
// 0 1 2 3 4 5 6 7 8
//
// l
// h
// -1 *0 1 2 4 3 7 6 8 # h--;
//
// l
// h
// -1 *0 1 2 4 3 7 6 8 # h--;
//
// l
// h
// -1 *0 1 2 4 3 7 6 8 # l >= h. swap l, h; l++, h--;
//
// l
// h
// -1 *0 1 2 4 3 7 6 8 # l = 2. Return l as i.
// 0 1 2 3 4 5 6 7 8
// left = l = 0, right = h = i - 1 = 2 - 1 = 1, mid = floor((0 + 1) / 2) = 0, pivot = x[1] = -1:
// l
// h
// *-1 0 1 2 4 3 7 6 8 # h++;
// 0 1 2 3 4 5 6 7 8
//
// l
// h
// *-1 0 1 2 4 3 7 6 8 # l >= h. swap l, h; l++, h--;
//
// l
// h
// *-1 0 1 2 4 3 7 6 8 # l = 1. Return l as i.
// -1 0 1 2 3 4 5 6 7 8
// left = l = 0, right = h = i - 1 = 1 - 1 = 0: # left >= right. Return.
// left = l = 0, right = h = 1 = 0: # left >= right. Return.
// left = l = 2, right = h = 3, mid = floor((2 + 3) / 2) = 2, pivot = x[2] = 1:
// l
// h
// -1 0 *1 2 4 3 7 6 8 # h--;
// 0 1 2 3 4 5 6 7 8
//
// l
// h
// -1 0 *1 2 4 3 7 6 8 # l <= h. swap l, h; l++, h--;
//
// l
// h
// -1 0 *1 2 4 3 7 6 8 # l = 3. Return as i.
// 0 1 2 3 4 5 6 7 8
// left = l = 2, right = h = i - 1 = 3 - 1 = 2: left >= right. Return.
// left = l = 3, right = h = 3: left >= right. Return.
// left = l = 4, right = h = 7, mid = floor((4 + 7) / 2) = 5, pivot = x[5] = 3:
//
// l
// h
// -1 0 1 2 4 *3 7 6 8 # h--;
// 0 1 2 3 4 5 6 7 8
//
// l
// h
// -1 0 1 2 4 *3 7 6 8 # h--;
//
// l
// h
// -1 0 1 2 4 *3 7 6 8 # l >= h. swap l, h. l++, h--;
//
// l
// h
// -1 0 1 2 *3 4 7 6 8 # l = 5. Return as i.
// 0 1 2 3 4 5 6 7 8
// left = l = 4, right = h = i - 1 = 5 - 1 = 4: left >= right. Return.
// left = l = 5, right = h = 7, mid = floor((5 + 7) / 2) = 6, pivot = x[6] = 7:
// l
// h
// -1 0 1 2 3 4 *7 6 8 # l--;
// 0 1 2 3 4 5 6 7 8
//
// l
// h
// -1 0 1 2 3 4 *7 6 8 # l <= h. swap l, h. l++, h--;
//
// l
// h
// -1 0 1 2 3 4 6 *7 8 # l <= h. swap l, h. l++, h--;
//
// l
// h
// -1 0 1 2 3 4 6 *7 8 # l = 7. Return as i.
// 0 1 2 3 4 5 6 7 8
// left = l = 5, right = h = i - 1 = 7 - 1 = 6, mid = floor((5 + 6 ) / 2) = 5, pivot = x[5] = 4:
// l
// h
// -1 0 1 2 3 *4 6 7 8 # h--;
// 0 1 2 3 4 5 6 7 8
//
// l
// h
// -1 0 1 2 3 *4 6 7 8 # l <= h. swap l, h. l++, h--;
//
// l
// h
// -1 0 1 2 3 *4 6 7 8 # l = 6. Return as i.
// 0 1 2 3 4 5 6 7 8
// left = l = 5, right = h = i - 1 = 6 - 1 = 5: # left <= right. Return.
// left = l = 6, right = h = 6: # left <= right. Return.
// left = l = 7, right = h = 7: # left <= right. Return.
// left = l = 8, right = h = 8: # left <= right. Return.
// Time complexity: O(n) as 2 ptrs are used to traverse elements from left to right towards the centre.
// The traversal stops when left and right cross each other.
// Space complexity: O(1) as swapping is done in-place.
function partition(arr, left, right, pivot) {
while (left <= right) {
while (arr[left] < pivot) left++;
while (arr[right] > pivot) right--;
if (left <= right) {
[arr[left], arr[right]] = [arr[right], arr[left]];
left++;
right--;
}
}
return left;
}
// Reference: https://bit.ly/2NEtCDw.
// Time complexity: O(n log(n)) as partition takes O(n) time before array can split into half.
// In each half, it recursively calls itself so there could be up to log(n) calls.
// Space complexity: O(log(n)) as there could be log(n) recursive calls everytime each half calls itself.
function quickSort(arr, left = 0, right = arr.length - 1) {
if (left >= right) return;
const pivot = arr[Math.floor((left + right) / 2)];
const index = partition(arr, left, right, pivot);
quickSort(arr, left, index - 1);
quickSort(arr, index, right);
return arr;
}
function isSortedArray(x) {
const len = x.length;
for (let i = 0; i < len; i += 1) {
if (x[i] < x[i - 1]) return false;
}
return true;
}
function main() {
const a = [
[4, 2, 1, 3, 6, 0],
[-7, -3, -9, -5, -8, 2, 3, 9, 1, -1],
[-4, 12, 7, 6, 12, 2, 0, -1, 1, -3],
[3, 6, 8, 17, 7, -3, -4, 9, 9, 6],
[1, -5, 15, 14, 5, 10, 7, 0, 4, 3],
[7, -4, 2, 6, 7, 2, 6, 11, 9, 3],
[1, -4, 7, 4, 1, 13, 8, 1, 2, -1],
[-6, 11, 8, -2, 15, 4, 9, 7, 3, 1],
[10, -3, -1, -4, 0, 2, -1, -2, -4, 9],
[14, 10, 0, 10, -3, 6, 1, 8, -6, 5],
[-3, 10, 3, 9, 5, 4, 9, 8, 3, 0],
];
a.forEach((n) => {
quickSort(n);
console.log(isSortedArray(n), n);
});
}
console.clear();
main();
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment