@santi100/sorting-lib
v0.0.5
Published
Santi's Sorting Library: Many sorting algorithms in one package!
Downloads
40
Readme
Santi's Sorting Library
- 🚀 Lightweight and fast
- 👴 ES3-compliant
- 📘 Comes with built-in TypeScript definitions
- 📑 Split into files (under
cjs/
) to import what's needed - 💻 Portable between the browser and Node.js
What's this?
This is a library of sorting algorithms written in TypeScript. Currently, the library includes the following algorithms:
- Bubble sort
- Insertion sort
- Selection sort
- Merge sort
- Quick sort
- Bogo sort
- Radix sort
- Heap sort
- Counting sort
- Shell sort
Thanks to @codediodeio for the idea, taken from his video about sorting algorithms and its corresponding repo.
Installation
- Via NPM:
npm install @santi100/sorting-lib
- Via Yarn:
yarn add @santi100/sorting-lib
- Via PNPM:
pnpm install @santi100/sorting-lib
API
type SortComparator<T = unknown> = (a: T, b: T) => number;
Comparator function for every sorting algorithm, except forradixSort
. It's fully compatible withArray.prototype.sort
's callback.type SortOrder = 'ascending' | 'descending';
Sorting order string. Must be eitherascending
ordescending
.interface SortOptions<T = unknown>;
Shape of theopts
object passed to every sorting algorithm, except forradixSort
. SeeRadixSortOptions
for the options specific to it.comparator?: SortComparator<T>;
Comparator function for every sorting algorithm, except forradixSort
. It's fully compatible withArray.prototype.sort
's callback. SeeSortComparator
.order?: SortOrder;
Sorting order string. Must be eitherascending
ordescending
. SeeSortOrder
.
interface RadixSortOptions;
Shape of theopts
object exclusive toradixSort
.order?: SortOrder;
Sorting order string. Must be eitherascending
ordescending
. SeeSortOrder
.
type CountingSortOptions = RadixSortOptions;
(since 0.0.3) Shape of theopts
object exclusive tocountingSort
.function bubbleSort<T = unknown>(arr: T[], opts?: SortOptions<T>): T[];
Sortsarr
with bubble-sort and returns a new sorted array (i.e.: doesn't mutatearr
). It takes the array to sort, and optional sorting options, and returns a sorted copy ofarr
.
Time complexity: Quadratic ($O(n ^ 2)$).
function insertionSort<T = unknown>(arr: T[], opts?: SortOptions<T>): T[];
Sortsarr
with insertion-sort and returns a new sorted array (i.e.: doesn't mutatearr
). It takes the array to sort, and optional sorting options, and returns a sorted copy ofarr
.
Time complexity (average and worst-case): Quadratic ($O(n ^ 2)$).
Time complexity (best-case): Linear ($O(n)$).
function selectionSort<T = unknown>(arr: T[], opts?: SortOptions<T>): T[];
Sortsarr
with selection-sort and returns a new sorted array (i.e.: doesn't mutatearr
). It takes the array to sort, and optional sorting options, and returns a sorted copy ofarr
.
Time complexity (average and worst-case): Quadratic ($O(n ^ 2)$).
function mergeSort<T = unknown>(arr: T[], opts?: SortOptions<T>): T[];
Sortsarr
with merge-sort and returns a new sorted array (i.e.: doesn't mutatearr
). It takes the array to sort, and optional sorting options, and returns a sorted copy ofarr
.
Time complexity (average and worst-case): Quasi-linear ($O(n \log{n})$).
function quickSort<T = unknown>(arr: T[], opts?: SortOptions<T>): T[];
Sortsarr
with quick-sort and returns a new sorted array (i.e.: doesn't mutatearr
). It takes the array to sort, and optional sorting options, and returns a sorted copy ofarr
.
Time complexity (best and average): Quasi-linear ($O(n \log{n})$).
Time complexity (worst): Quadratic ($ O(n ^ 2) $).
function bogoSort<T = unknown>(arr: T[], opts?: SortOptions<T>): T[];
Sortsarr
with bogo-sort and returns a new sorted array (i.e.: doesn't mutatearr
). It takes the array to sort, and optional sorting options, and returns a sorted copy ofarr
.
Time complexity (average): Linear-factorial ($O((n!)(n))$).
Worst-case time complexity: Infinity ($O(∞)$).
function radixSort<T = unknown>(arr: T[], opts?: SortOptions<T>): T[];
Sortsarr
with radix-sort and returns a new sorted array (i.e.: doesn't mutatearr
). It takes the array to sort, and optional sorting options, and returns a sorted copy ofarr
.
Time complexity (best, average and worst): $O(n k)$, where $k$ is the number of digits or characters in the largest element.
function heapSort<T = unknown>(arr: T[], opts?: SortOptions<T>): T[];
Sortsarr
with heap-sort and returns a new sorted array (i.e.: doesn't mutatearr
). It takes the array to sort, and optional sorting options, and returns a sorted copy ofarr
.
Time complexity (best, average and worst): Quasi-linear ($O(n \log {n})$).
function shellSort<T = unknown>(arr: T[], opts?: SortOptions<T>): T[];
: Sortsarr
with shell-sort and returns a new sorted array (i.e.: doesn't mutatearr
). It takes the array to sort, and optional sorting options, and returns a sorted copy ofarr
.
Time complexity: Depends on the gap sequence used. Best known is $O(n (log2(n) ^ 2))$.
function countingSort(arr: number[], opts?: CountingSortOptions): T[];
: Sortsarr
with counting-sort and returns a new sorted array (i.e.: doesn't mutatearr
). It takes the array to sort, and optional sorting options, and returns a sorted copy ofarr
.
Time complexity (best, average and worse): $O(n + k)$, where $k$ is the range of input (maximum element - minimum element + 1).
function bozoSort<T = unknown>(array: T[]): T[];
Sorts an array using the Bozo Sort algorithm.| Name | Description | | ------- | ----------------------- | |
array
| The array to be sorted. |function bozoSort<T = unknown>(array: T[], opts: SortingOptions<T>): T[];
Sorts an array using the Bozo Sort algorithm.| Name | Description | | ------- | ------------------------------------- | |
array
| The array to be sorted. | |opts
| An object containing sorting options. |
Usage
import { mergeSort, bozoSort } from '@santi100/sorting-lib'; // ESM
const { mergeSort, bozoSort } = require('@santi100/sorting-lib'); // CJS
const sorted = mergeSort([4, 2, 5, 1, 3]); // sorted = [1, 2, 3, 4, 5]
const descendingSorted = mergeSort([4, 2, 5, 1, 3], { order: 'descending' }); // descendingSorted = [5, 4, 3, 2, 1]
const objSorted = mergeSort(
[
{
age: 23
},
{
age: 12
},
{
age: 30
}
],
{ comparator: (a, b) => a.age - b.age }
); // returns [ { age: 12 }, { age: 23 }, { age: 30 }]
// You can do same for all algorithms, except for `radixSort`, which is limited to ints for now, so
// its only option is `order`.
const sortedArray = bozoSort(array);
console.log(sortedArray); // Output: [1, 2, 3]
Contribute
Wanna contribute? File an issue or pull request! Look at the contribution instructions and make sure you follow the contribution Code of Conduct.
*Hasn't been tested in an actual ES3 environment. Feel free to open an issue or pull request if you find any non-ES3 thing. See "Contribute" for instructions on how to do so.
^The source code is just a few kilobytes in size.