# toolbox/sort.js

``````/**
*  Sorting is one most common operation on a collection of data.
*  This modules provides the following algorithms:
*
*  - Insertion sort `O(n²)`
*  - Selection sort `O(n²)`
*  - Insertion sort `O(n²)`
*  - Merge sort `O(n log n)`
*  - Quicksort `O(n log n)`
*
*  ## Sorting properties
*
*  ### Stability
*  An algorithm is said to be stable if it uses a secondary criteria to ensure
*  some order for items that fall in the same group based on the primary
*  criteria.
*
*  For example, given
*  ```
*  const users = [
*    { name: 'Animesh', age: 26 },
*    { name: 'Nicoleta', age: 25 },
*    { name: 'Chris', age: 32 },
*    { name: 'Adam', age: 32 },
*  ];
*  ```
*  A stable sorting algorithm (ascending order by age) will **always** return
*  ```
*  const users = [
*    { name: 'Nicoleta', age: 25 },
*    { name: 'Animesh', age: 26 },
*    { name: 'Adam', age: 32 },
*    { name: 'Chris', age: 32 },
*  ];
*  ```
*  Notice that Adam and Chris were sorted alphabetically within their primary group
*  (age = 32).
*
*  An unstable algorithm may or may not return the same result. It will sort by age
*  alright, but may place Chris before Adam.
*
*  ### In-place
*  An in-place sorting algorithm has a space complexity of `O(1)`. It doesn't require
*  extra memory because it shuffles the item within the collection itself. Such algorithm
*  are extremely useful in memory contraint environments such as embedded devices.
*
*  ### Online
*  Online sorting algorithm don't need to resort the whole collection if a new item
*
*  doesn't. A simple example from manual arithmetic is methods for multiplying. Non-adaptive
*  means you multiply every digit no matter what, adaptive would, say, tack a 0 to the end
*  of a number when multiplying by 10 without ever carrying out the actual multiplication.
*
*  In the context of sorting, an non-adaptive algorithm takes the same(ish) amount of time
*  for a given number of values no matter what. An adaptive algorithm takes advantage of
*  properties of the data. This usually means taking advantage of any near sorted or already
*  sorted portions.
*
*  @module toolbox/sort
*/

/**
*  Bubble sort repeatedly steps through the collection to be sorted, compares each pair of
*  adjacent items and swaps them if they are in the wrong order. This continues until no
*  swaps are needed.
*
*  Returns the sorted collection as an array.
*
*  #### Properties
*  - ✅ Stable
*  - ✅ In-place
*  - ✅ Online
*  - Time complexity: `O(n²)`
*  - Space complexity: `O(1)`
*
*  @public
*  @param {Iterable} collection Collection items **must** support comparison operations <, >, ==
*  @returns {Array}
*/
function BubbleSort(collection) {
const array = Array.from(collection)

for (let i = 1; i < array.length; i++) {
let swapped = false

for (let current = 0; current < array.length - i; current++) {
if (array[current] > array[current + 1]) {
swap(array, current, current + 1)
swapped = true
}
}

if (!swapped) {
break
}
}

return array
}

/**
*  The "natural" way of sorting. Starts from the second element, and checks whether
*  it's smaller than values that come before it. If so, it's placed to its rightful
*  place. Otherwise, moves on the next element.
*
*  Returns the sorted collection as an array.
*
*  #### Properties
*  - ✅ Stable
*  - ✅ In-place
*  - ✅ Online
*  - Time complexity: `O(n²)`
*  - Space complexity: `O(1)`
*
*  @param {Iterable} collection Collection items **must** support comparison operations <, >, ==
*  @returns {array}
*/
function InsertionSort(collection) {
const array = Array.from(collection)

for (let right = 1; right < array.length; right++) {
for (let left = right; array[left - 1] > array[left]; left--) {
swap(array, left - 1, left)
}
}

return array
}

/**
*  Sorts an array by repeatedly finding the minimum element (considering ascending order) from
*  unsorted part and putting it at the beginning. The algorithm maintains two subarrays in a
*  given array.
*
*  1. The subarray which is already sorted.
*  2. Remaining subarray which is unsorted.
*
*  In every iteration of selection sort, the minimum element (considering ascending order) from
*  the unsorted subarray is picked and moved to the sorted subarray. **Selection sort minimises**
*  **the number of swaps.** Unlike insertion and bubble sort, it does only one swap in each
*  iteration of the whole collection.
*
*  ```
*  arr[] = 64 25 12 22 11
*
*  // Find the minimum element in arr[0...4]
*  // and place it at beginning
*  11 25 12 22 64
*
*  // Find the minimum element in arr[1...4]
*  // and place it at beginning of arr[1...4]
*  11 12 25 22 64
*
*  // Find the minimum element in arr[2...4]
*  // and place it at beginning of arr[2...4]
*  11 12 22 25 64
*
*  // Find the minimum element in arr[3...4]
*  // and place it at beginning of arr[3...4]
*  11 12 22 25 64
*  ```
*
*  Returns the sorted collection as an array.
*
*  #### Properties
*  - ❌ Stable
*  - ✅ In-place
*  - ❌ Online
*  - Time complexity: `O(n²)`
*  - Space complexity: `O(1)`
*
*  @param {Iterable} collection Collection items **must** support comparison operations <, >, ==
*  @returns {array}
*/
function SelectionSort(collection) {
const array = Array.from(collection)

for (let left = 0; left < array.length; left++) {
let selection = left

for (let right = left + 1; right < array.length; right++) {
if (array[selection] > array[right]) {
selection = right
}
}

if (selection !== left) {
swap(array, left, selection)
}
}

return array
}

/**
*  An efficient sorting algorithm that uses divide and conquer technique to
*
*  Splits the array into halves until 2 or fewer elements are left in each half.
*  It sorts these two elements and then merges back all halves until the whole
*  collection is sorted.
*
*  Returns the sorted collection as an array.
*
*  #### Properties
*  - ✅ Stable
*  - ❌ In-place
*  - ❌ Online
*  - Time complexity: `O(n log n)`
*  - Space complexity: `O(n)`
*
*  @param {Iterable} collection Collection items **must** support comparison operations <, >, ==
*  @returns {array}
*/
function MergeSort(collection) {
const array = Array.from(collection)
return split(array)
}

/** @private */
function split(array) {
const size = array.length

if (size < 2) {
return array
}

if (size == 2) {
return array < array ? array : [array, array]
}

const half = Math.ceil(size / 2)
return merge(
split(array.slice(0, half)),
split(array.slice(half))
)
}

/** @private */
function merge(firstHalf, secondHalf = []) {
const mergedSize = firstHalf.length + secondHalf.length
const mergedArray = Array(mergedSize)

for (let index = 0, j = 0, k = 0; index < mergedSize; index++) {
if (k >= secondHalf.length || (j < firstHalf.length && firstHalf[j] <= secondHalf[k])) {
mergedArray[index] = firstHalf[j]
j += 1
}
else {
mergedArray[index] = secondHalf[k]
k += 1
}
}

return mergedArray
}

/**
*  An efficient sorting algorithm that uses divide and conquer technique to
*  and doesn't require additional memory.
*
*  Quicksort works by picking a "pivot" element (preferably random) and move
*  all elements that are smaller than the pivot to the right. The ones that
*  are larger than the pivot are moved to the left of it. This is done recursively
*  until the collection is sorted.
*
*  Returns the sorted collection as an array.
*
*  #### Properties
*  - ❌ Stable
*  - ✅ In-place
*  - ❌ Online
*  - Time complexity: `O(n log n)`
*  - Space complexity: `O(1)`
*
*  Typically, an array sorted in descending order gives the worst-case performance
*  of quick sort `O(n²)`. To avoid this, the
*
*  @param {Iterable} collection Collection items **must** support comparison operations <, >, ==
*  @returns {array}
*/
function QuickSort(collection) {
const array = Array.from(collection)
shuffle(array)
return _quicksort(array)
}

/** @private */
function shuffle(array) {
for (let index = 0; index < array.length; index++) {
const newIndex = Math.floor(Math.random() * array.length)
swap(array, index, newIndex)
}
return array
}

/** @private */
function _quicksort(array, start = 0, end = array.length - 1) {
if (start < end) {
const pivotIndex = partition(array, start, end)
_quicksort(array, start, pivotIndex - 1)
_quicksort(array, pivotIndex + 1, end)
}
return array
}

/** @private */
function partition(array, start, end) {
let pivotIndex = start

for (let current = start + 1; current <= end; current++) {
if (array[current] < array[start]) {
pivotIndex += 1
swap(array, current, pivotIndex)
}
}

swap(array, start, pivotIndex)
return pivotIndex
}

/**
*  Swap array elements in place
*  Runtime: `O(1)`
*
*  @private
*  @param {array} array array to be modified
*  @param {integer} from index of the first element
*  @param {integer} to index of the second element
*/
function swap(array, from, to) {
[array[from], array[to]] = [array[to], array[from]]
}

module.exports = {
BubbleSort,
InsertionSort,
MergeSort,
QuickSort,
SelectionSort
}
``````