Last active
July 9, 2021 09:59
-
-
Save storyn26383/4230b82c9962c4a857fcacca5ccc5ccc to your computer and use it in GitHub Desktop.
Algorithms for Functional Programming
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
type PermutationTable = Array<number> | |
type SBox = Array<Array<number>> | |
type CanCastToBigInt = number | bigint | string | BigNumber | |
const CHAR_BITS = 16 | |
const DES_BITS_LIMIT = 64 | |
const BITS_ROTATION_TABLE: Array<number> = [ | |
1, 1, 2, 2, 2, 2, 2, 2, | |
1, 2, 2, 2, 2, 2, 2, 1, | |
] | |
const PERMUTED_CHOICE_1_TABLE: PermutationTable = [ | |
57, 49, 41, 33, 25, 17, 9, | |
1, 58, 50, 42, 34, 26, 18, | |
10, 2, 59, 51, 43, 35, 27, | |
19, 11, 3, 60, 52, 44, 36, | |
63, 55, 47, 39, 31, 23, 15, | |
7, 62, 54, 46, 38, 30, 22, | |
14, 6, 61, 53, 45, 37, 29, | |
21, 13, 5, 28, 20, 12, 4, | |
] | |
const PERMUTED_CHOICE_2_TABLE: PermutationTable = [ | |
14, 17, 11, 24, 1, 5, | |
3, 28, 15, 6, 21, 10, | |
23, 19, 12, 4, 26, 8, | |
16, 7, 27, 20, 13, 2, | |
41, 52, 31, 37, 47, 55, | |
30, 40, 51, 45, 33, 48, | |
44, 49, 39, 56, 34, 53, | |
46, 42, 50, 36, 29, 32, | |
] | |
const INITIAL_PERMUTATION_TABLE: PermutationTable = [ | |
58, 50, 42, 34, 26, 18, 10, 2, | |
60, 52, 44, 36, 28, 20, 12, 4, | |
62, 54, 46, 38, 30, 22, 14, 6, | |
64, 56, 48, 40, 32, 24, 16, 8, | |
57, 49, 41, 33, 25, 17, 9, 1, | |
59, 51, 43, 35, 27, 19, 11, 3, | |
61, 53, 45, 37, 29, 21, 13, 5, | |
63, 55, 47, 39, 31, 23, 15, 7, | |
] | |
const FINAL_PERMUTATION_TABLE: PermutationTable = [ | |
40, 8, 48, 16, 56, 24, 64, 32, | |
39, 7, 47, 15, 55, 23, 63, 31, | |
38, 6, 46, 14, 54, 22, 62, 30, | |
37, 5, 45, 13, 53, 21, 61, 29, | |
36, 4, 44, 12, 52, 20, 60, 28, | |
35, 3, 43, 11, 51, 19, 59, 27, | |
34, 2, 42, 10, 50, 18, 58, 26, | |
33, 1, 41, 9, 49, 17, 57, 25, | |
] | |
const EXPANSION_TABLE: PermutationTable = [ | |
32, 1, 2, 3, 4, 5, | |
4, 5, 6, 7, 8, 9, | |
8, 9, 10, 11, 12, 13, | |
12, 13, 14, 15, 16, 17, | |
16, 17, 18, 19, 20, 21, | |
20, 21, 22, 23, 24, 25, | |
24, 25, 26, 27, 28, 29, | |
28, 29, 30, 31, 32, 1, | |
] | |
const S_BOXES: Array<SBox> = [ | |
[ | |
[14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7], | |
[ 0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8], | |
[ 4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0], | |
[15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13], | |
], | |
[ | |
[15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2, 13, 12, 0, 5, 10], | |
[ 3, 13, 4, 7, 15, 2, 8, 14, 12, 0, 1, 10, 6, 9, 11, 5], | |
[ 0, 14, 7, 11, 10, 4, 13, 1, 5, 8, 12, 6, 9, 3, 2, 15], | |
[13, 8, 10, 1, 3, 15, 4, 2, 11, 6, 7, 12, 0, 5, 14, 9], | |
], | |
[ | |
[10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12, 7, 11, 4, 2, 8], | |
[13, 7, 0, 9, 3, 4, 6, 10, 2, 8, 5, 14, 12, 11, 15, 1], | |
[13, 6, 4, 9, 8, 15, 3, 0, 11, 1, 2, 12, 5, 10, 14, 7], | |
[ 1, 10, 13, 0, 6, 9, 8, 7, 4, 15, 14, 3, 11, 5, 2, 12], | |
], | |
[ | |
[ 7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 4, 15], | |
[13, 8, 11, 5, 6, 15, 0, 3, 4, 7, 2, 12, 1, 10, 14, 9], | |
[10, 6, 9, 0, 12, 11, 7, 13, 15, 1, 3, 14, 5, 2, 8, 4], | |
[ 3, 15, 0, 6, 10, 1, 13, 8, 9, 4, 5, 11, 12, 7, 2, 14], | |
], | |
[ | |
[ 2, 12, 4, 1, 7, 10, 11, 6, 8, 5, 3, 15, 13, 0, 14, 9], | |
[14, 11, 2, 12, 4, 7, 13, 1, 5, 0, 15, 10, 3, 9, 8, 6], | |
[ 4, 2, 1, 11, 10, 13, 7, 8, 15, 9, 12, 5, 6, 3, 0, 14], | |
[11, 8, 12, 7, 1, 14, 2, 13, 6, 15, 0, 9, 10, 4, 5, 3], | |
], | |
[ | |
[12, 1, 10, 15, 9, 2, 6, 8, 0, 13, 3, 4, 14, 7, 5, 11], | |
[10, 15, 4, 2, 7, 12, 9, 5, 6, 1, 13, 14, 0, 11, 3, 8], | |
[ 9, 14, 15, 5, 2, 8, 12, 3, 7, 0, 4, 10, 1, 13, 11, 6], | |
[ 4, 3, 2, 12, 9, 5, 15, 10, 11, 14, 1, 7, 6, 0, 8, 13], | |
], | |
[ | |
[ 4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1], | |
[13, 0, 11, 7, 4, 9, 1, 10, 14, 3, 5, 12, 2, 15, 8, 6], | |
[ 1, 4, 11, 13, 12, 3, 7, 14, 10, 15, 6, 8, 0, 5, 9, 2], | |
[ 6, 11, 13, 8, 1, 4, 10, 7, 9, 5, 0, 15, 14, 2, 3, 12], | |
], | |
[ | |
[13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7], | |
[ 1, 15, 13, 8, 10, 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2], | |
[ 7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13, 15, 3, 5, 8], | |
[ 2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11], | |
] | |
] | |
const PERMUTATION_TABLE: PermutationTable = [ | |
16, 7, 20, 21, 29, 12, 28, 17, | |
1, 15, 23, 26, 5, 18, 31, 10, | |
2, 8, 24, 14, 32, 27, 3, 9, | |
19, 13, 30, 6, 22, 11, 4, 25, | |
] | |
class BigNumber { | |
value: bigint | |
constructor(value: CanCastToBigInt) { | |
this.value = this.normalizeValue(value) | |
} | |
add(right: CanCastToBigInt): BigNumber { | |
return new BigNumber(this.value + this.normalizeValue(right)) | |
} | |
sub(right: CanCastToBigInt): BigNumber { | |
return new BigNumber(this.value - this.normalizeValue(right)) | |
} | |
and(right: CanCastToBigInt): BigNumber { | |
return new BigNumber(this.value & this.normalizeValue(right)) | |
} | |
or(right: CanCastToBigInt): BigNumber { | |
return new BigNumber(this.value | this.normalizeValue(right)) | |
} | |
xor(right: CanCastToBigInt): BigNumber { | |
return new BigNumber(this.value ^ this.normalizeValue(right)) | |
} | |
shiftLeft(right: CanCastToBigInt): BigNumber { | |
return new BigNumber(this.value << this.normalizeValue(right)) | |
} | |
shiftRight(right: CanCastToBigInt): BigNumber { | |
return new BigNumber(this.value >> this.normalizeValue(right)) | |
} | |
toBigInt(): bigint { | |
return this.value | |
} | |
toString(radix?: number): string { | |
return this.value.toString(radix) | |
} | |
private normalizeValue(value: CanCastToBigInt): bigint { | |
if (value instanceof BigNumber) { | |
return value.toBigInt() | |
} | |
if (typeof value === 'bigint') { | |
return value | |
} | |
return BigInt(value) | |
} | |
} | |
class Code { | |
value: BigNumber | |
bits: number | |
constructor(value: CanCastToBigInt, bits?: number) { | |
this.value = new BigNumber(value) | |
this.bits = this.normalizeBits(bits) | |
} | |
slice(start: number, bits?: number): Code { | |
if (!bits) { | |
bits = this.bits - start + 1 | |
} | |
return new Code( | |
this.value.shiftRight(this.bits - start - bits + 1).and(new BigNumber(1).shiftLeft(bits).sub(1)), | |
bits | |
) | |
} | |
split(quantity: number = 2): Array<Code> { | |
const size = this.bits / quantity | |
const groups = [] | |
for (let i = 0; i < quantity; i++) { | |
groups.push(this.slice(size * i + 1, size)) | |
} | |
return groups | |
} | |
rotateLeft(offset: number): Code { | |
return new Code( | |
this.value.shiftLeft(offset).and(new BigNumber(1).shiftLeft(this.bits).sub(1)).or(this.slice(1, offset).toBigInt()), | |
this.bits | |
) | |
} | |
combine(right: Code): Code { | |
return new Code( | |
this.value.shiftLeft(right.getBits()).or(right.toBigInt()), | |
this.bits + right.getBits() | |
) | |
} | |
xor(right: Code): Code { | |
return new Code( | |
this.value.xor(right.toBigInt()), | |
this.bits | |
) | |
} | |
padEnd(bits: number): Code { | |
if (this.bits >= bits) { | |
return this | |
} | |
return this.combine(new Code(0, bits - this.bits)) | |
} | |
permute(table: PermutationTable): Code { | |
const permutedBits = table.length | |
const permutedValue = table.reduce((permuted: BigNumber, targetBit: number, currentBit: number): BigNumber => { | |
return permuted.or(this.slice(targetBit, 1).toBigNumber().shiftLeft(permutedBits - currentBit - 1)) | |
}, new BigNumber(0)) | |
return new Code(permutedValue, permutedBits) | |
} | |
getBits(): number { | |
return this.bits | |
} | |
toBigNumber(): BigNumber { | |
return this.value | |
} | |
toBigInt(): bigint { | |
return this.value.toBigInt() | |
} | |
toNumber(): number { | |
return Number(this.toBigInt()) | |
} | |
toString(radix: number = 16): string { | |
return this.value.toString(radix).toUpperCase().padStart(this.bits / radix * 2, '0') | |
} | |
static fromText(text: string): Code { | |
return new Code( | |
text.split('').reduce((result: BigNumber, char: string): BigNumber => { | |
return result.shiftLeft(CHAR_BITS).or(char.charCodeAt(0)) | |
}, new BigNumber(0)), | |
text.length * CHAR_BITS | |
) | |
} | |
toText(): string { | |
const char = String.fromCharCode(this.slice(1, CHAR_BITS).toNumber()) | |
if (this.bits <= CHAR_BITS) { | |
return char | |
} | |
return char + this.slice(CHAR_BITS + 1).toText() | |
} | |
private normalizeBits(bits: number | null | undefined): number { | |
if (bits) { | |
return bits | |
} | |
return this.value.toString(16).length * 4 | |
} | |
} | |
class DES { | |
static encrypt(input: Code, key: Code): Code { | |
const instance = new DES() | |
return instance.des(input, instance.generateSubKeys(key)) | |
} | |
static decrypt(input: Code, key: Code): Code { | |
const instance = new DES() | |
return instance.des(input, instance.generateSubKeys(key).reverse()) | |
} | |
private des(input: Code, subkeys: Array<Code>): Code { | |
const sliced: Code = input.slice(1, DES_BITS_LIMIT).padEnd(DES_BITS_LIMIT) | |
const permuted: Code = sliced.permute(INITIAL_PERMUTATION_TABLE) | |
let [left, right]: [Code, Code] = permuted.split() as [Code, Code] | |
for (const subkey of subkeys) { | |
const originalLeft: Code = left | |
left = right | |
right = this.feistel(right, subkey) | |
right = right.xor(originalLeft) | |
} | |
const crypted = right.combine(left).permute(FINAL_PERMUTATION_TABLE) | |
if (input.getBits() <= DES_BITS_LIMIT) { | |
return crypted | |
} | |
return crypted.combine(this.des(input.slice(DES_BITS_LIMIT + 1), subkeys)) | |
} | |
private feistel(code: Code, subkey: Code): Code { | |
const expended: Code = code.permute(EXPANSION_TABLE) | |
const groups: Array<Code> = expended.xor(subkey).split(8) | |
const substituted: BigNumber = groups.reduce((result: BigNumber, group: Code, index: number): BigNumber => { | |
const x: number = group.slice(1, 1).combine(group.slice(6, 1)).toNumber() | |
const y: number = group.slice(2, 4).toNumber() | |
return result.shiftLeft(4).or(S_BOXES[index][x][y]) | |
}, new BigNumber(0)) | |
return new Code(substituted, 32).permute(PERMUTATION_TABLE) | |
} | |
private generateSubKeys(key: Code): Array<Code> { | |
const sliced: Code = key.slice(1, DES_BITS_LIMIT).padEnd(DES_BITS_LIMIT) | |
const permuted: Code = sliced.permute(PERMUTED_CHOICE_1_TABLE) | |
const subkeys: Array<Code> = [] | |
let [left, right]: [Code, Code] = permuted.split() as [Code, Code] | |
for (const offset of BITS_ROTATION_TABLE) { | |
left = left.rotateLeft(offset) | |
right = right.rotateLeft(offset) | |
subkeys.push(left.combine(right).permute(PERMUTED_CHOICE_2_TABLE)) | |
} | |
return subkeys | |
} | |
} | |
const key = new Code('0x01234567890ABCDEF') | |
console.log( | |
DES.decrypt( | |
DES.encrypt( | |
Code.fromText('abc中文def中文ghi中文jkl中文mno'), | |
key | |
), | |
key | |
).toText() | |
) |
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
class Graph { | |
nodes = {} | |
adjacencyMatrix = {} | |
addNode(node) { | |
this.nodes[node] = node | |
this.adjacencyMatrix[node] = {} | |
} | |
addEdge(a, b, distance = 1) { | |
this.adjacencyMatrix[a][b] = distance | |
this.adjacencyMatrix[b][a] = distance | |
} | |
findAdjacencies(node) { | |
const adjacencies = [] | |
for (const address in this.adjacencyMatrix[node]) { | |
if (this.adjacencyMatrix[node][address]) { | |
adjacencies.push(this.nodes[address]) | |
} | |
} | |
return adjacencies | |
} | |
buildRoute(predecessor, target) { | |
if (!(predecessor[target] instanceof Node)) { | |
return [target.value] | |
} | |
return [...this.buildRoute(predecessor, predecessor[target]), target.value] | |
} | |
bfs(from, to) { | |
const queue = [] | |
const predecessor = {} | |
queue.push(from) | |
predecessor[from] = -1 | |
while (queue.length) { | |
const current = queue.shift() | |
if (current === to) { | |
break | |
} | |
this.findAdjacencies(current).forEach((adjacency) => { | |
if (predecessor[adjacency]) { | |
return | |
} | |
predecessor[adjacency] = current | |
queue.push(adjacency) | |
}) | |
} | |
return this.buildRoute(predecessor, to) | |
} | |
dfs(from, to) { | |
const predecessor = {} | |
const visit = (node) => { | |
if (node === to) { | |
return | |
} | |
this.findAdjacencies(node).forEach((adjacency) => { | |
if (predecessor[adjacency]) { | |
return | |
} | |
predecessor[adjacency] = node | |
visit(adjacency) | |
}) | |
} | |
predecessor[from] = -1 | |
visit(from) | |
return this.buildRoute(predecessor, to) | |
} | |
bellmanFord(from, to) { | |
const distance = {} | |
const predecessor = {} | |
for (const address in this.nodes) { | |
distance[address] = Infinity | |
} | |
distance[from] = 0 | |
predecessor[from] = -1 | |
const relax = (node) => { | |
let updated = false | |
this.findAdjacencies(node).forEach((adjacency) => { | |
const testDistance = distance[node] + this.adjacencyMatrix[node][adjacency] | |
if (distance[adjacency] <= testDistance) { | |
return | |
} | |
updated = true | |
distance[adjacency] = testDistance | |
predecessor[adjacency] = node | |
relax(adjacency) | |
}) | |
return updated | |
} | |
while (!relax(from)) { | |
// | |
} | |
return this.buildRoute(predecessor, to) | |
} | |
dijkstras(from, to) { | |
const distance = {} | |
const predecessor = {} | |
const options = {} | |
for (const address in this.nodes) { | |
distance[address] = Infinity | |
} | |
distance[from] = 0 | |
predecessor[from] = -1 | |
options[from] = 0 | |
while (this._isNotEmpty(options)) { | |
const node = this.nodes[this._min(options)] | |
delete options[node] | |
this.findAdjacencies(node).forEach((adjacency) => { | |
const testDistance = distance[node] + this.adjacencyMatrix[node][adjacency] | |
if (distance[adjacency] <= testDistance) { | |
return | |
} | |
distance[adjacency] = testDistance | |
predecessor[adjacency] = node | |
options[adjacency] = testDistance | |
}) | |
} | |
return this.buildRoute(predecessor, to) | |
} | |
aStar(from, to) { | |
const estimatedDistance = {} | |
const distance = {} | |
const predecessor = {} | |
const options = {} | |
for (const address in this.nodes) { | |
estimatedDistance[address] = graph.bfs(to, this.nodes[address]).length - 1 | |
distance[address] = Infinity | |
} | |
estimatedDistance[from] = 0 | |
distance[from] = 0 | |
predecessor[from] = -1 | |
options[from] = 0 | |
while (this._isNotEmpty(options)) { | |
const node = this.nodes[this._min(options)] | |
delete options[node] | |
this.findAdjacencies(node).forEach((adjacency) => { | |
const testDistance = | |
distance[node] | |
- estimatedDistance[node] | |
+ estimatedDistance[adjacency] | |
+ this.adjacencyMatrix[node][adjacency] | |
if (distance[adjacency] <= testDistance) { | |
return | |
} | |
distance[adjacency] = testDistance | |
predecessor[adjacency] = node | |
options[adjacency] = testDistance | |
}) | |
} | |
return this.buildRoute(predecessor, to) | |
} | |
_min(nodes) { | |
let minNodeAddress = Object.keys(nodes)[0] | |
let minValue = nodes[minNodeAddress] | |
for (const address in nodes) { | |
if (nodes[address] < minValue) { | |
minNodeAddress = address | |
minValue = nodes[address] | |
} | |
} | |
return minNodeAddress | |
} | |
_isNotEmpty(nodes) { | |
return Object.keys(nodes).length | |
} | |
} | |
class Node { | |
value = null | |
address = null | |
constructor(value) { | |
this.value = value | |
this.address = this.generateFakeMemoryAddress() | |
} | |
generateFakeMemoryAddress() { | |
return `0x${Math.random().toString(16).slice(2, 14)}` | |
} | |
toString() { | |
return `${this.address}` | |
} | |
} | |
const graph = new Graph() | |
const nodeA = new Node('A') | |
const nodeB = new Node('B') | |
const nodeC = new Node('C') | |
const nodeD = new Node('D') | |
const nodeE = new Node('E') | |
const nodeF = new Node('F') | |
const nodeG = new Node('G') | |
graph.addNode(nodeA) | |
graph.addNode(nodeB) | |
graph.addNode(nodeC) | |
graph.addNode(nodeD) | |
graph.addNode(nodeE) | |
graph.addNode(nodeF) | |
graph.addNode(nodeG) | |
graph.addEdge(nodeA, nodeB, 9) | |
graph.addEdge(nodeA, nodeC, 2) | |
graph.addEdge(nodeB, nodeC, 6) | |
graph.addEdge(nodeB, nodeD, 3) | |
graph.addEdge(nodeB, nodeE, 1) | |
graph.addEdge(nodeC, nodeD, 2) | |
graph.addEdge(nodeC, nodeF, 9) | |
graph.addEdge(nodeD, nodeE, 5) | |
graph.addEdge(nodeD, nodeF, 6) | |
graph.addEdge(nodeE, nodeF, 3) | |
graph.addEdge(nodeE, nodeG, 7) | |
graph.addEdge(nodeF, nodeG, 4) | |
/* | |
* B - 1 - E | |
* /|\ /|\ | |
* 9 | 3 5 | 7 | |
* / | \ / | \ | |
* A 6 D 3 G | |
* \ | / \ | / | |
* 2 | 2 6 | 4 | |
* \|/ \|/ | |
* C - 9 - F | |
*/ | |
console.log('bfs:', graph.bfs(nodeA, nodeG).join(' -> ')) | |
console.log('dfs:', graph.dfs(nodeA, nodeG).join(' -> ')) | |
console.log('bellman ford:', graph.bellmanFord(nodeA, nodeG).join(' -> ')) | |
console.log('dijkstras:', graph.dijkstras(nodeA, nodeG).join(' -> ')) | |
console.log('a star:', graph.aStar(nodeA, nodeG).join(' -> ')) |
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 binarySearch = (needle, haystack, basis = 0) => { | |
if (haystack.length === 0) return -1 | |
const center = Math.ceil((haystack.length - 1) / 2) | |
if (haystack[center] === needle) return basis + center | |
if (haystack[center] > needle) return binarySearch(needle, haystack.slice(0, center), basis) | |
return binarySearch(needle, haystack.slice(center + 1), basis + center + 1) | |
} | |
console.log(binarySearch(18, [1, 3, 5, 7, 9, 12, 14, 16, 18, 20])) |
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 last = (list) => list.slice(-1)[0] | |
const bubble = ([first, second, ...rest]) => { | |
if (second === undefined) return [first] | |
if (first > second) return [second, ...bubble([first, ...rest])] | |
return [first, ...bubble([second, ...rest])] | |
} | |
const bubbleSort = (list) => { | |
if (list.length === 0) return [] | |
if (list.length === 1) return list | |
const sorted = bubble(list) | |
return [...bubbleSort(sorted.slice(0, -1)), last(sorted)] | |
} | |
console.log('Bubble Sort:', bubbleSort([5, 4, 3, 2, 1, 6, 7, 8, 9, 0])) | |
const select = ([first, second, ...rest]) => { | |
if (second === undefined) return [first] | |
if (first > second) return [first, ...select([second, ...rest])] | |
return [second, ...select([first, ...rest])] | |
} | |
const selectionSort = (list) => { | |
if (list.length < 2) return list | |
const sorted = select(list) | |
return [last(sorted), ...selectionSort(sorted.slice(0, -1))] | |
} | |
console.log('Selection Sort:', selectionSort([5, 4, 3, 2, 1, 6, 7, 8, 9, 0])) | |
const insert = (target, [first, second, ...rest]) => { | |
if (first === undefined) return [target] | |
if (second === undefined) return first <= target ? [first, target] : [target, first] | |
if (first <= target && target <= second) return [first, target, second, ...rest] | |
return [first, ...insert(target, [second, ...rest])] | |
} | |
const insertionSort = ([first, ...rest]) => { | |
if (rest.length === 0) return [first] | |
return insert(first, insertionSort(rest)) | |
} | |
console.log('Insertion Sort:', insertionSort([5, 4, 3, 2, 1, 6, 7, 8, 9, 0])) | |
const split = (list) => { | |
const center = Math.ceil(list.length / 2) | |
return [list.slice(0, center), list.slice(center)] | |
} | |
const merge = (left, right) => { | |
if (left.length === 0) return right | |
if (right.length === 0) return left | |
if (left[0] < right[0]) return [left[0], ...merge(left.slice(1), right)] | |
return [right[0], ...merge(left, right.slice(1))] | |
} | |
const mergeSort = (list) => { | |
if (list.length < 2) return list | |
let [left, right] = split(list) | |
return merge(mergeSort(left), mergeSort(right)) | |
} | |
console.log('Merge Sort:', mergeSort([5, 4, 3, 2, 1, 6, 7, 8, 9, 0])) | |
const swap = (list, a, b) => { | |
[list[a], list[b]] = [list[b], list[a]] | |
} | |
const heapify = (list, target = 0) => { | |
const left = 2 * target + 1 | |
const right = left + 1 | |
if (list[left] !== undefined) heapify(list, left) | |
if (list[right] !== undefined) heapify(list, right) | |
if (list[right] === undefined && list[target] > list[left]) { | |
swap(list, target, left) | |
return list | |
} | |
if (list[target] > list[right] && list[right] > list[left]) { | |
swap(list, target, left) | |
heapify(list, left) | |
return list | |
} | |
if (list[target] > list[left] && list[left] > list[right]) { | |
swap(list, target, right) | |
heapify(list, right) | |
return list | |
} | |
return list | |
} | |
const heapSort = (list) => { | |
if (list.length === 0) return [] | |
const [first, ...rest] = heapify(list) | |
return [first, ...heapSort(rest)] | |
} | |
console.log('Heap Sort:', heapSort([5, 4, 3, 2, 1, 6, 7, 8, 9, 0])) | |
const filter = ([first, ...rest], condition) => { | |
if (first === undefined) return [] | |
if (condition(first)) return [first, ...filter(rest, condition)] | |
return filter(rest, condition) | |
} | |
const quickSort = ([first, ...rest]) => { | |
if (first === undefined) return [] | |
return [ | |
...quickSort(filter(rest, n => n < first)), | |
first, | |
...quickSort(filter(rest, n => n >= first)) | |
] | |
} | |
console.log('Quick Sort:', quickSort([5, 4, 3, 2, 1, 6, 7, 8, 9, 0])) | |
const prepareBuckets = () => { | |
return [[], [], [], [], [], [], [], [], [], []] | |
} | |
const putToBuckets = ([first, ...rest], digit, buckets) => { | |
if (first === undefined) return buckets | |
const radix = Math.floor(first / 10 ** (digit - 1)) % 10 | |
return putToBuckets(rest, digit, [ | |
...buckets.slice(0, radix), | |
[...buckets[radix], first], | |
...buckets.slice(radix + 1), | |
]) | |
} | |
const sortInbuckets = ([first, ...rest], digit) => { | |
if (first === undefined) return [] | |
if (first.length === 0) return sortInbuckets(rest, digit) | |
return [bucketSort(first, digit - 1), ...sortInbuckets(rest, digit)] | |
} | |
const flatten = ([first, ...rest]) => { | |
if (first === undefined) return [] | |
return [...first, ...flatten(rest)] | |
} | |
const bucketSort = (list, digit) => { | |
if (digit === 0) return list | |
if (digit === undefined) digit = Math.ceil(Math.log10(Math.max(...list))) | |
return flatten(sortInbuckets(putToBuckets(list, digit, prepareBuckets()), digit)) | |
} | |
console.log('Bucket Sort:', bucketSort([15, 34, 33, 42, 41, 46, 27, 28, 9, 0])) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment