npm package: @santi100/sorting-lib
Description: Santi's Sorting Library: Many sorting algorithms in one package!
Author: santi100a
Latest version: 0.0.5

# Santi's Sorting Library

[![Build Status](https://github.com/santi100a/sorting-lib/actions/workflows/ci.yml/badge.svg)](https://github.com/santi100a/sorting-lib/actions)
[![npm homepage](https://img.shields.io/npm/v/@santi100/sorting-lib)](https://npmjs.org/package/@santi100/sorting-lib)
[![GitHub stars](https://img.shields.io/github/stars/santi100a/sorting-lib.svg)](https://github.com/santi100a/sorting-lib)
[![License](https://img.shields.io/github/license/santi100a/sorting-lib.svg)](https://github.com/santi100a/sorting-lib)
[![Bundlephobia stats](https://img.shields.io/bundlephobia/min/@santi100/sorting-lib)](https://bundlephobia.com/package/@santi100/sorting-lib@latest)

- 🚀 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](https://github.com/codediodeio) for the idea,
taken from [his video about sorting algorithms](https://www.youtube.com/watch?v=RfXt_qHDEPw)
and [its corresponding repo](https://github.com/fireship-io/sorting-algorithms).

## 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 for `radixSort`. It's fully compatible with `Array.prototype.sort`'s callback.
- `type SortOrder = 'ascending' | 'descending';` Sorting order string. Must be either `ascending` or `descending`.
- `interface SortOptions<T = unknown>;` Shape of the `opts` object passed to every sorting algorithm, except for `radixSort`.
  See `RadixSortOptions` for the options specific to it.
  - `comparator?: SortComparator<T>;` Comparator function for every sorting algorithm, except for `radixSort`.
    It's fully compatible with `Array.prototype.sort`'s callback. See `SortComparator`.
  - `order?: SortOrder;` Sorting order string. Must be either `ascending` or `descending`. See `SortOrder`.
- `interface RadixSortOptions;` Shape of the `opts` object exclusive to `radixSort`.
  - `order?: SortOrder;` Sorting order string. Must be either `ascending` or `descending`. See `SortOrder`.
- `type CountingSortOptions = RadixSortOptions;` (since 0.0.3) Shape of the `opts` object
  exclusive to `countingSort`.

- `function bubbleSort<T = unknown>(arr: T[], opts?: SortOptions<T>): T[];`
  Sorts `arr` with bubble-sort and returns a new sorted array (i.e.: doesn't mutate `arr`).
  It takes the array to sort, and optional sorting options, and returns a sorted copy of `arr`.

**Time complexity:** Quadratic ($O(n ^ 2)$).

- `function insertionSort<T = unknown>(arr: T[], opts?: SortOptions<T>): T[];`
  Sorts `arr` with insertion-sort and returns a new sorted array (i.e.: doesn't mutate `arr`).
  It takes the array to sort, and optional sorting options, and returns a sorted copy of `arr`.

**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[];`
  Sorts `arr` with selection-sort and returns a new sorted array (i.e.: doesn't mutate `arr`).
  It takes the array to sort, and optional sorting options, and returns a sorted copy of `arr`.

**Time complexity (average and worst-case):** Quadratic ($O(n ^ 2)$).

- `function mergeSort<T = unknown>(arr: T[], opts?: SortOptions<T>): T[];`
  Sorts `arr` with merge-sort and returns a new sorted array (i.e.: doesn't mutate `arr`).
  It takes the array to sort, and optional sorting options, and returns a sorted copy of `arr`.

**Time complexity (average and worst-case):** Quasi-linear ($O(n \log{n})$).

- `function quickSort<T = unknown>(arr: T[], opts?: SortOptions<T>): T[];`
  Sorts `arr` with quick-sort and returns a new sorted array (i.e.: doesn't mutate `arr`).
  It takes the array to sort, and optional sorting options, and returns a sorted copy of `arr`.

**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[];`
  Sorts `arr` with bogo-sort and returns a new sorted array (i.e.: doesn't mutate `arr`).
  It takes the array to sort, and optional sorting options, and returns a sorted copy of `arr`.

**Time complexity (average):** Linear-factorial ($O((n!)(n))$).

**Worst-case time complexity:** Infinity ($O(∞)$).

- `function radixSort<T = unknown>(arr: T[], opts?: SortOptions<T>): T[];`
  Sorts `arr` with radix-sort and returns a new sorted array (i.e.: doesn't mutate `arr`).
  It takes the array to sort, and optional sorting options, and returns a sorted copy of `arr`.

**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[];` Sorts `arr` with heap-sort and returns a new sorted array (i.e.: doesn't mutate `arr`).
  It takes the array to sort, and optional sorting options, and returns a sorted copy of `arr`.

**Time complexity (best, average and worst):** Quasi-linear ($O(n \log {n})$).

- `function shellSort<T = unknown>(arr: T[], opts?: SortOptions<T>): T[];`: Sorts `arr` with shell-sort and returns a new sorted array (i.e.: doesn't mutate `arr`).
  It takes the array to sort, and optional sorting options, and returns a sorted copy of `arr`.

**Time complexity:** Depends on the gap sequence used. Best known is $O(n (log2(n) ^ 2))$.

- `function countingSort(arr: number[], opts?: CountingSortOptions): T[];`: Sorts `arr` with counting-sort and returns a new sorted array (i.e.: doesn't mutate `arr`).
  It takes the array to sort, and optional sorting options, and returns a sorted copy of `arr`.

**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

```typescript
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](https://github.com/santi100a/sorting-lib/issues) or [pull request](https://github.com/santi100a/sorting-lib/pulls)!
Look at [the contribution instructions](CONTRIBUTING.md) and make sure you follow the [contribution Code of Conduct](CODE_OF_CONDUCT.md).

<sub>

_\*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._

</sub>