8000 feat: add treesort algorithm (#217) · TheAlgorithms/TypeScript@e0ae744 · GitHub
[go: up one dir, main page]
Skip to content

Commit e0ae744

Browse files
tamaf96tamaf96appgurueu
authored
feat: add treesort algorithm (#217)
* feat: add treesort algorithm * use existing data structure * make generic and add tests for string and date * fix typo * Fix typo --------- Co-authored-by: tamaf96 <tamaf96@mi.fu-berlin.de> Co-authored-by: Lars Müller <34514239+appgurueu@users.noreply.github.com>
1 parent 7433103 commit e0ae744

File tree

3 files changed

+52
-0
lines changed

3 files changed

+52
-0
lines changed

‎DIRECTORY.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -166,3 +166,4 @@
166166
* [Selection Sort](https://github.com/TheAlgorithms/TypeScript/blob/HEAD/sorts/selection_sort.ts)
167167
* [Shell Sort](https://github.com/TheAlgorithms/TypeScript/blob/HEAD/sorts/shell_sort.ts)
168168
* [Swap Sort](https://github.com/TheAlgorithms/TypeScript/blob/HEAD/sorts/swap_sort.ts)
169+
* [Tree Sort](https://github.com/TheAlgorithms/TypeScript/blob/HEAD/sorts/tree_sort.ts)

‎sorts/test/tree_sort.test.ts

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
import { treeSort } from "../tree_sort";
2+
3+
describe('TreeSort (numbers)', () => {
4+
it.each([
5+
{ input: [], expected: [] },
6+
{ input: [1, 18, 3, 4, -5, 6], expected: [-5, 1, 3, 4, 6, 18] },
7+
{ input: [7, 6, 2, 5.2, 11, 0], expected: [0, 2, 5.2, 6, 7, 11] },
8+
{ input: [3, 3, -2, 1, 0], expected: [-2, 0, 1, 3, 3] },
9+
{ input: [3, 0, -2.4, 1, 9, 8, -7, 6], expected: [-7, -2.4, 0, 1, 3, 6, 8, 9] },
10+
{ input: [1, 0, -14, 0, 8.6, 6, 8], expected: [-14, 0, 0, 1, 6, 8, 8.6] },
11+
])('should work for given input', ({ input, expected }) => {
12+
expect(treeSort(input)).toEqual(expected);
13+
});
14+
});
15+
16+
describe('TreeSort (strings)', () => {
17+
it.each([
18+
{ input: ["e","egr","sse","aas", "as","abs"], expected: ["aas","abs","as","e","egr","sse"] },
19+
])('should work for given input', ({ input, expected }) => {
20+
expect(treeSort(input)).toEqual(expected);
21+
});
22+
});
23+
24+
describe('TreeSort (dates)', () => {
25+
it.each([
26+
{ input: [new Date("2019-01-16"),new Date("2019-01-01"),new Date("2022-05-20")], expected: [new Date("2019-01-01"),new Date("2019-01-16"),new Date("2022-05-20")] },
27+
])('should work for given input', ({ input, expected }) => {
28+
expect(treeSort(input)).toEqual(expected);
29+
});
30+
});
31+
32+
33+

‎sorts/tree_sort.ts

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
/**
2+
* @author : tamaf96<https://github.com/tamaf96>
3+
* @description
4+
* Tree Sort sorts a list by building a binary search tree and traversing it.
5+
* @param {T[]} arr - Array of comparable items
6+
* @return {T[]} - The sorted Array.
7+
* @see <https://en.wikipedia.org/wiki/Tree_sort>
8+
*/
9+
10+
import { BinarySearchTree } from "../data_structures/tree/binary_search_tree";
11+
12+
export const treeSort = <T>(arr: T[]): T[] => {
13+
const searchTree = new BinarySearchTree<T>();
14+
for (const item of arr) {
15+
searchTree.insert(item);
16+
}
17+
return searchTree.inOrderTraversal();
18+
};

0 commit comments

Comments
 (0)
0